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 pointCalculate the sum of areas of
- If this sum is greater than the area of the rectangle, then P(x,y) is outside the rectangle.
- Else if this sum is equal to the area of the rectangle (observe that this sum can not be less than the later),
- 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),
- 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.
- If one of the perpendicular distances is greater than the respective length, then P(x,y) is outside the rectangle.
- 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.
- 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