### 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**

Calculate 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,P

_{AB}(say) and from CD,P

_{CD}(say) must be less than |AD|=|BC| and the perpendicular distances from AD,P

_{AD}(say) and from BC,P

_{BC}(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⋅P
_{AD}. - Else if P
_{AB}=0 and P_{CD}=|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 P

_{AD},P

_{BC}must be ≤ |AB|=|CD|, P

_{BC}=|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