How to determine if a point is inside a rectangle?

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 (xp,yp), and the rectangle’s upper left point is (x1,y1) and lower right point is (x2,y2):

if (xp is between x1 and x2) AND (yp is between y1 and y2)
then the point(xp,yp) 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 πŸ™‚

VN:F [1.9.22_1171]
Rating: 2.6/5 (24 votes cast)
How to determine if a point is inside a rectangle?, 2.6 out of 5 based on 24 ratings

26 thoughts on “How to determine if a point is inside a rectangle?

  1. Wei

    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?

    VA:F [1.9.22_1171]
    0
  2. 1337c0d3r

    Hi 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 πŸ™‚

    VA:F [1.9.22_1171]
    +3
  3. Test

    Sure 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?

    VA:F [1.9.22_1171]
    0
  4. johny

    Hi, 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?

    VA:F [1.9.22_1171]
    0
    1. 1337c0d3r Post author

      Hi 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

      VN:F [1.9.22_1171]
      0
  5. lijie

    My 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.

    VA:F [1.9.22_1171]
    +9
  6. algorist

    Hi, 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..

    VA:F [1.9.22_1171]
    0
  7. codingC

    I 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.

    VA:F [1.9.22_1171]
    0
    1. aimless

      @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?

      VA:F [1.9.22_1171]
      0
  8. Eric Nelson

    After 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.

    VA:F [1.9.22_1171]
    0
  9. laurence

    If 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.

    VA:F [1.9.22_1171]
    0
  10. laurence

    ahhh, oops, i cant type properly!!

    VA:F [1.9.22_1171]
    0
  11. laurence

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

    VA:F [1.9.22_1171]
    0
  12. Pingback: Must read problems of LeetCode | What I learn, I blog !

  13. zyfo2

    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.

    VA:F [1.9.22_1171]
    0
  14. IsAs

    Assume 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

    VA:F [1.9.22_1171]
    0
  15. munir

    Here 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.

    VA:F [1.9.22_1171]
    -1
  16. liwzhi

    the 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;

    VN:F [1.9.22_1171]
    +1
  17. HelloWorld

    Can 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

    VA:F [1.9.22_1171]
    0
  18. reklama na witryny

    Nice 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.

    VA:F [1.9.22_1171]
    0
  19. Lemuel

    In 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.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*