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.
This question is trivial if the rectangle is aligned to the x and y-axis:
if (xp is between x1 and x2) AND (yp is between y1 and y2)
then the point(xp,yp) is inside the rectangle.
http://martin-thoma.com/how-to-check-if-a-point-is-inside-a-rectangle/
Formulae
If you know the coordinates of the points, you can calculate the area of the rectangle like this:
Arectangle=12∣∣(yA−yC)⋅(xD−xB)+(yB−yD)⋅(xA−xC)∣∣
return (C.x*B.y-B.x*C.y)-(C.x*A.y-A.x*C.y)+(B.x*A.y-A.x*B.y);
}
http://geosoft.no/software/geometry/Geometry.java.html
Read full article from 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.
This question is trivial if the rectangle is aligned to the x and y-axis:
if (xp is between x1 and x2) AND (yp is between y1 and y2)
then the point(xp,yp) 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);
}
http://www.emanueleferonato.com/2012/03/09/algorithm-to-determine-if-a-point-is-inside-a-square-with-mathematics-no-hit-test-involved/http://martin-thoma.com/how-to-check-if-a-point-is-inside-a-rectangle/
Formulae
If you know the coordinates of the points, you can calculate the area of the rectangle like this:
The area of a triangle is: Atriangle=12(x1(y2−y3)+x2(y3−y1)+x3(y1−y2))
public function triangleArea(A:Point,B:Point,C:Point):Number {return (C.x*B.y-B.x*C.y)-(C.x*A.y-A.x*C.y)+(B.x*A.y-A.x*B.y);
}
http://geosoft.no/software/geometry/Geometry.java.html
Read full article from How to determine if a point is inside a rectangle? | LeetCode