[Math] How to find nearest point on line of rectangle from anywhere

geometry

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:

  1. Calculate centre of rectangle (E).

  2. Normalize point, P against centre:

    Px = kx – Ex
    Py = ky – Ey

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

Best Answer

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. :)

Related Question