Tuesday, May 6, 2014

Point inside a rectangle or not

Problem

Given a 2D point and a rectangle, determine if the point is inside the rectangle.


Solution

Method 1 - Calculate the area of triangles with 2 vertices of rectangle and point
P(x,y), and rectangle A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4)
Calculate the sum of areas of APD,DPC,CPB,PBA.

  1. If this sum is greater than the area of the rectangle, then P(x,y) is outside the rectangle.
  2. Else if this sum is equal to the area of the rectangle (observe that this sum can not be less than the later),
    1. if area of any of the triangle is 0, then P(x,y) is on the rectangle (in fact on that line corresponding to the triangle of area=0). Observe that the equality of the sum is necessary, only area=0 is not sufficient),
    2. else P(x,y) is is inside the rectangle.

Acceptably this approach needs substantial amount of computation. This approach can be employed to any irregular polygon, too.



Method 2 - Perpendicular distance of point P to the sides
Another way is to calculate the perpendicular distances of P(x,y) from all the 4 lines AB,CD,AD,BC

To be inside the rectangle, the perpendicular distances from AB,PAB(say) and from CD,PCD(say) must be less than |AD|=|BC| and the perpendicular distances from AD,PAD(say) and from BC,PBC(say) must be less than |CD|=|AB|. Here , the areas of each of the four triangles < 1/2the area of the rectangle.

  1. If one of the perpendicular distances is greater than the respective length, then P(x,y) is outside the rectangle.
  2. This essentially implies and is implied by the statement : the area of the respective triangle > 12the area of the rectangle (as commented by Ben Voigt) as △APD=1/2*AD⋅PAD.
  3.     Else if PAB=0 and PCD=|AD| , then P(x,y) is on AB . So, △PBA=0 and △PCD=12the area of the rectangle.

    Observe that in this case, the rest two perpendicular distances PAD,PBC must be ≤ |AB|=|CD|, PBC=|AB|⟹P(x,y) is lies on AD i.e, P coincides with A as it is already on AB .

Method 3  - Scalar product
The trick is to use dot product to find the projected line from point P onto the rectangle sides, and if its length is shorter than the sides, then the point must be inside the rectangle.
Let P be the point we have to check, then it is inside rectangle iff:

(0<AP⋅AB<AB⋅AB)∧(0<AP⋅AD<AD⋅AD)

References

0 comments:

Post a Comment