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

This is a problem that is related to Computer Graphics.

This question is trivial if the rectangle is not aligned to the x and y-axis:

Assume point P’s coordinate is (x_{p},y_{p}), and the rectangle’s upper left point is (x_{1},y_{1}) and lower right point is (x_{2},y_{2}):

if (x_{p} is between x_{1} and x_{2}) AND (y_{p} is between y_{1} and y_{2})

then the point(x_{p},y_{p}) is inside the rectangle.

But what if the rectangle is rotated?

Although the question becomes much harder now, it is not too difficult to think of another solution that utilizes the previous solution. If we could transform the point and the rectangle such that the rectangle become axis-aligned, we could solve the problem in the direct way mentioned above. In other words, 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 rectangle.

Assume that we have a pre-written Vector2d class π

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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); } |

could we use other condition check as:

return ( P1_P4.Dot(P1_P) > 0 && P1_P4.Dot(P1_P) < P1_P4.Dot(P1_4) && P1_P3.Dot(P1_P) > 0 && P1_P3.Dot(P1_P) < P1_P3.Dot(P1_3);

k = P1_P4.Dot(P1_P) / P1_P4.Dot(P1_P4) is coefficient of P1_P along vector P1_P4?

0Hi Wei! Thanks for your comment!

Yes, this is another way to look at it, and you are absolutely correct. I do think your solution is much easier to understand.

There is one minor correction I would like to point out. According to the above image of the rectangle, I would replace all occurrences of P3 in your condition check with P2, because you are projection the line P1_P onto the line P1_P2, not P1_P3. (But you may have define P3 differently).

I will update the article later by adding your solution. Thanks for the comment again π

+3Sure and you're right, that is a typo because I use different notations. In fact, I need to thank you to orgnize this blog for interviews. Very nice blog!

Btw, could you add some design pattern questions and answers as well?

0Hi, 1337:

Some questions about your dot solution.

1. Center of Rectangle C == 0.5 * (P1 + P3), so it looks TWO_P_C == 2 * (P – C), not 2*P – C.

2. What is the mathematical implication of the vector TWO_P_C – P3_P4? I understand that P3_P4 is the vector from P4 to P3, and TWO_P_C is 2 times of the vector from the center of the rectangle to the point which is to be determined inside or outside of the rectangle. But TWO_P_C – P3_P4, ……, really have no idea what it is.

Could you please shed more light on this?

0Hi Johny,

1. You are absolutely right. TWO_P_C is just a short form variable name I decided to use for holding the results temporarily. It does not mean anything. Sorry for the confusion.

2. In the post I did not give a lot of details in how I reach the step. You would need to manipulate some equation before you reach to that simplified inequality. First, you would need to obtain the vector which is the projection of point P to the side of the rectangle (P3_P4). Then simplify it. Refer to this if you are rusty on vectors: http://en.wikipedia.org/wiki/Vector_projection

0My idea is to calculate the area of four triangles. Assume four vertices of the rectangle are 1,2,3,4, and the point is p. The four triangles are Triangle(1,2,p), Triangle(1,3,p), Triangle(3,4,p), and Triangle(4,2,p). If p is out of the rectangle, the sum of the area of the four triangles is greater than the area of the rectangle. Otherwise, they are equivalent. Given three vertices of a triangle, it is easy to compute its area. How is the idea? Any suggestion is welcome.

+9great ideaοΌ

0superb π

0Hi, Can you please write the vector2D function… What does it actually do?? Please, it would be very helpful.. I am still trying to get the logic behind your algorithm….

Thanks..

0I have another thought about this problem. We know if P is inside the rectangular, then line P1—>P must cross line P2—P3 or line P3—P4, then if the joint P’ is in between P2–P3 or P3–P4 and P is in between P–P’, then the point P is inside.

0@codingC: I guess you meant,

“if the joint Pβ is in between P2βP3 or P3βP4 and P is in between P1βPβ, then the point P is inside.”

So

1. find P’ for P2-P3

2. if P’ not inside (P2-P3)find P’ for P3-P4

3. check if P inside P1-P’

right?

0I found this solution a little tough to follow. However, I feel the following link suggests a better way to do it.

0After trying this solution out, it didn’t work consistently, but the following solution worked like a champ and is much easier to follow.

http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

Here is the code, for reference. Excluding lines with only braces, there are only 7 lines of code.

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)

{

int i, j, c = 0;

for (i = 0, j = nvert-1; i testy) != (verty[j]>testy)) &&

(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )

c = !c;

}

return c;

}

Argument Meaning

nvert Number of vertices in the polygon. Whether to repeat the first vertex at the end is discussed below.

vertx, verty Arrays containing the x- and y-coordinates of the polygon's vertices.

testx, testy X- and y-coordinate of the test point.

0If you want an ‘easy’ method, you can just check that the following is satisfied:

I.e. i check that at least one point from all points is North, East, South and West.

Wont work for complex geometries.

0missed off the west criteria from the above:

IF(P1x or P2x or P3x or P4x)<xp:

0ahhh, oops, i cant type properly!!

0eh?? that code block doesnt format properly. maybe delete some of those comments, sorry for the spamming.

0ignore me – thats rubbish

0Pingback: Must read problems of LeetCode | What I learn, I blog !

maybe checking the area is another way. you don’t need transform the point. just check whether 4 triangles’ area are equal to the rectangle.

0Assume that we have equations of four lines of rectangle – Not hard to compute since we have all four points. Let’s call four line equations as L1, L2, L3, L4

– L1 & L3 are parallel

– L2 & L4 are parallel

1) Substitute the given point P in all four equations

2) If a point lies inside a rectangle, then product of L1 & L3 is negative

3) Product of L2 & L4 is negative

0Here is a simple method to determine if a point is inside a rectangle:

If the sum of the lines from the point to the 4 vertices of the rectangle is < the sum of the 4 edges of the rectangle, then it will be inside. if it is the same then the point is on one side of the rectangle.

-1the rectangle is (x1,y1), (x1,y2), οΌx2, y1), (x2,y2). Then test (x3,y3)

we knew if the point is in the rectangle x1<=x3<=x2; y1<=y3<=y2;

so, (x3-x1)*(x3-x2)<= 0; (y3-y1)*(y3-y2)<=0;

+1Can we use the approach where we compute the equations of the lines forming the sides of the rectangle. We solve all the equations for point P(The point to be tested). So it Equations of the lines are E1, E2, E3, E4 (where E1 and E3 are opposite sides) we can check if (E1(P) > 0 && E3(P) 0 && E1(P) < 0) and similarly for E2 and E4

0Nice post. I used to be checking constantly this weblog and I’m

inspired! Very useful information particularly the last

section π I take care of such info much. I used to be seeking this

particular info for a very lengthy time.

Thanks and good luck.

0In accordance to the report, Snapchat had been warned the two in August and as

soon as once more in late December in regards to the

actually good probability of a security breach and even supplied solutions to protect in opposition to a feasible hack.

0