How to find nearest point on line of rectangle from anywhere?

Question

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.

Sample rectangle

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

Calculate centre of rectangle (E).
Normalize point, P against centre:

P_x = k_x - E_x
P_y = k_y - E_y

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

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 ;)

score 9 · Accepted Answer · answered Apr 10 '13 at 05:53

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'.

enter image description here

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

Thanks. I'll look at this and do some testing. Need to try it out :) — Zimzalabim, Apr 10 '13 at 06:05

score 2 · Answer 2 · answered Nov 26 '18 at 20:13

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.

I am having troubles with the logic of "Being put into practice means that my method is verified to work". With this logic any program that is used in practice is verified to work. There are libraries that are successfully used by thousands of ppl and still bugs are found that occure in some edge cases. — H. Hess, Jul 22 '21 at 14:28
If you've found any actual errors in the method or code then please point these out. Generic nitpicking attempts are quite pointless. — Karl Ramstedt, Jul 24 '21 at 11:14

How to find nearest point on line of rectangle from anywhere?

2 Answers2

In pseudocode: