Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ;)
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks. I'll look at this and do some testing. Need to try it out :) –  Zimzalabim Apr 10 '13 at 6:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.