Cfrgtkky

Having a rectangle where upper left corner, width and height is given. How can I find nearest line on that rectangle from any point?

To visualize. Having the rectangle (OK, here a square, but anyhow) ABCD. Green dots represents points and red lines intersections I want to find.

E.g. having point k I would like to find i. My current approach is as follows:

1. Calculate centre of rectangle (E).


2. 
   

   Normalize point, P against centre:

   
   
   

   P_x = k_x - E_x
   
   P_y = k_y - E_y
   

   
   


3. 
   

   Use atan2 on P to find which plane it belongs to.

   
   
   

   By plane I mean: I divide the rectangle in eight planes as with a quadrant - but divide those four in half as well. Atan2 is a
   special arctan variant that gives value {0, Π} for points below
   x-axis and {0, -Π} above x-axis.

   
   
   

     {-PI/2, -PI} y {-0, -PI/2}
   
   A +------------|-------------.+ B
   
     | .          |           .  |
   
     |   .    3   |   2     .    |
   
     |     .      |       .      |   
   
     |       .    |     .        |
   
     |  4      .  |   .      1   |
   
     |           .| .            |
   
     -------------E--------------- x
   
     |          . | .            |
   
     |  5      .  |   .          |
   
     |       .    |     .    8   |
   
     |      .     |       .      |  {PI/2, PI}  |   {0, PI/2}
   
     |    .       |         .    |
   
     |   .   6    |  7        .  |  
   
     | .          |             .|
   
   D +------------|----i---------+ C
   
                       |
   
                       |
   
                       |
   
                       k
   
   

   
   


4. 
   

   Then I do a check by:

   
   
   

   IF atan2 > PI / 4 * 3 THEN 
   
        Plane 5: use A.x for x, and points y-value.
   
   ELSE IF atan2 > PI / 4 * 2 THEN 
   
        Plane 6: use D.y for y, and points x-value.
   
   ...
   
   

   
   

By sample from picture that would give

atan2 < PI / 4 * 3

atan2 < PI / 4 * 2

atan2 > PI / 4       <-- OK at plane 7.

I would believe there is a more direct approach for this. Any help would be
greatly appreciated. My mathematics is very rusty, but working on it.

EDIT:

OK. Looking at my nice ASCII I realized I can combine planes:

• 1 + 8 Use x from C by check on absolute value of atan2 (0 to PI/4)


• 2 + 3 Use y from A


• 4 + 5 Use x from A by check on absolute value of atan2 (PI/4*3 to PI)


• 6 + 7 Use y from C

Eliminating quite a few steps. I have to look closer at Billy's nice
answer as well.

However I thought there might be a more direct approach. As in:

  f(x, y, ABCD) .... => point ;)

That sounds more or less sensible, but there are some difficult cases you've forgotten to check for. It also doesn't quite work when the rectangle isn't a square. I think the best solution is actually a little simpler.

For simplicity, let me give this rectangle some coordinates: call the bottom left point (0, 0), the bottom right point (a, 0), the top left point (0, b) and the top right point (a, b).

The embarrassingly garish image below shows that there are actually 8 regions you need to look at. The good news is: if k is outside the square, you can just read off the nearest point and calculate its distance directly. (For example, if k is in the light blue area above the square, with coordinates (x, y), the nearest point on the rectangle is (x, b). If it's in the yellow area to the left, with coordinates (x, y), the nearest point is (0, y). If it's in the pink area to the lower right, the nearest point is (a, 0).)

If k is inside the square, it's a little more annoying. But the basic recipe is the same. If k has coordinates (x, y), you need to work out which is smallest out of these four numbers: x, a-x, y, b-y. If x is the smallest, the nearest point is (0, y). If a-x is the smallest, the nearest point is (a, y). And so on.

There are also ambiguous points, like (a/2, b/2), which have more than one 'nearest point'.

I hope I haven't made a mistake here. My head is swimming with coordinates. Hopefully the idea is clear. :)

Having recently coded a simple physics engine for a course, I did this as a part of rectangle-circle collision. Being put into practice means that my method is verified to work, since bugs would otherwise occur.

For clarity, let's call P the point you wish to find the closest point to on the rectangle.

When P is outside of the rectangle the closest point on the rectangle is P clamped to the bounds of the rectangle.

If P is inside the rectangle you need to work out which side is the closest, then use that side's coordinate as the value on the corresponding axis for the closest point.

For example, if your point is the closest to the negative Y bound (Bottom) then the closest point is (P.x, Bottom), where P.x is the X coordinate of the point P and Bottom is the Y coordinate of the negative Y bound. And if P is the closest to the negative X bound (Left) then it's (Left, P.y), e.t.c..

There are ambiguous points in the exact middle between two sides, which have more than one closest point.

In pseudocode:

bool insideX = center.x-bounds.x < P.x && P.x < center.x+bounds.x;

bool insideY = center.y-bounds.y < P.y && P.y < center.y+bounds.y;

bool pointInsideRectangle = insideX && insideY;



if (!pointInsideRectangle){ //Outside

    closestPoint.x = Max(center.x-bounds.x, Min(P.x, center.x + bounds.x));

    closestPoint.y = Max(center.y-bounds.y, Min(P.y, center.y + bounds.y));

}

else { //Inside

    Vector2D distanceToPositiveBounds = center+bounds - P;

    Vector2D distanceToNegativeBounds = -(center-bounds - P);

    float smallestX = Min(distanceToPositiveBounds.x, distanceToNegativeBounds.x);

    float smallestY = Min(distanceToPositiveBounds.y, distanceToNegativeBounds.y);

    float smallestDistance = Min(smallestX, smallestY);



    if (smallestDistance == distanceToPositiveBounds.x)

        closestPoint = (center.x+bounds.x, P.y);

    else if (smallestDistance == distanceToNegativeBounds.x)

        closestPoint = (center.x-bounds.x, P.y);

    else if (smallestDistance == distanceToPositiveBounds.y)

        closestPoint = (P.x, center.y+bounds.y);

    else

        closestPoint = (P.x, center.y-bounds.y);

}

Where Max returns the largest of two values and Min returns the smallest.

The code assumes that rectangle data is stored as center and bounds; for example center.y+bounds.y is the Y coordinate of the higher bound (Top) of the rectangle.

Actual code used can be found here.