How to determine if a point is inside a rectangle? | LeetCode

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

we are transforming the rectangle’s coordinate space to the x-y coordinate space.

First, the rectangle’s center is translated to the origin, then the rectangle is rotated such that it is axis-aligned with the major axes. The rotation equation can be written as x’ = ux*x + uy*y and y’ = vx*x + vy*y, where (x,y) is the original point, (x’,y’) is the rotated point, (ux,uy) and (vx,vy) are both the normalized orthogonal vector of the axes of the rectangle (see figure above). To understand why this is so, you need to understand the change of basis in linear algebra.

Translating and rotating points involve lots of multiplications. Can we do better than this?

The answer is yes, we can utilize dot 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 rectan

bool is_point_in_rectangle(const Rect& rect, const Point& p) {

  Vector2d P1(rect.p1.x, rect.p1.y);

  Vector2d P2(rect.p2.x, rect.p2.y);

  Vector2d P3(rect.p3.x, rect.p3.y);

  Vector2d P4(rect.p4.x, rect.p4.y);

  Vector2d P(p.x, p.y);

 

  Vector2d P1_P4 = P1 - P4;

  Vector2d P3_P4 = P3 - P4;

  Vector2d TWO_P_C = 2.0*P - P1 - P3;    // TWO_P_C=2P-C, C=Center of rectangle

 

  return (P3_P4.Dot(TWO_P_C - P3_P4) <= 0 && P3_P4.Dot(TWO_P_C + P3_P4) >= 0) &&

         (P1_P4.Dot(TWO_P_C - P1_P4) <= 0 && P1_P4.Dot(TWO_P_C + P1_P4) >= 0);

}

Read full article from How to determine if a point is inside a rectangle? | LeetCode