Finding whether a point is inside the rectangle or not

Question

I want to find if the point is inside the rectangle or not. The rectangle can be oriented in any way and should not be oriented along the axis.

One way I could think of is to rotate the rectangle and the coordinates of the points to align the axis of the rectangle, and then just check the coordinates of the point whether they are inside the rectangle or not.

The above method requires rotation and therefore floating point operations. Is there any other effective way to do this?

Answer 1

How is a rectangle represented? Three points? Four points? Point, side and angle? Two points and a side? Something other? Without knowing this, any attempt to answer your question will have purely academic significance.

In any case, for any convex polygon (including a rectangle) the test is very simple: check each edge of the polygon, assuming that each edge is oriented counterclockwise, and check whether the point is to the left of the edge (to the left is the airplane half-plane). If all edges pass the test, the point is inside. If at least one failure - the point is outside.

To check if the point (xp, yp) lies on the left side of the edge (x1, y1) - (x2, y2) , you just need to calculate

 D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1) 

If D > 0 , the point is on the left side. If D < 0 , the point is on the right side. If D = 0 , the point is on a straight line.

---

A previous version of this answer described a seemingly different version of the left test (see below). But it is easy to show that it calculates the same value.

... To check if the point (xp, yp) lies on the left side of the edge (x1, y1) - (x2, y2) , you need to build an equation for the line containing the edge. The equation looks as follows

 A * x + B * y + C = 0 

Where

 A = -(y2 - y1) B = x2 - x1 C = -(A * x1 + B * y1) 

Now all you have to do is calculate

 D = A * xp + B * yp + C 

If D > 0 , the point is on the left side. If D < 0 , the point is on the right side. If D = 0 , the point is on a straight line.

However, this test, again, works for any convex polygon, which means that it may be too general for a rectangle. A rectangle may allow a simpler test ... For example, in a rectangle (or in any other parallelogram), the values ​​of A and B have the same value, but different signs for opposite (i.e. parallel) edges, which can be used to simplify the test.

Answer 2

Assuming the rectangle is represented by three points A, B, C, with AB and BC perpendicular, you only need to check the projection of the query point M on AB and BC:

 0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

AB is the vector AB with coordinates (Bx-Ax, By-Ay), and dot(U,V) is the point product of the vectors U and V: Ux*Vx+Uy*Vy .

Update . An example illustrates this: A (5.0) B (0.2) C (1.5) and D (6.3). From the coordinate of the point we get AB = (- 5.2), BC = (1,3), dot (AB, AB) = 29, point (BC, BC) = 10.

For the query point M (4,2), we have AM = (- 1,2), BM = (4.0), dot (AB, AM) = 9, dot (BC, BM) = 4. M is inside the rectangle.

For the query point P (6,1), we have AP = (1,1), BP = (6, -1), point (AB, AP) = - 3, point (BC, BP) = 3, P is not inside the rectangle, since its projection on the side AB is not inside the segment AB.

Answer 3

 # Pseudo code # Corners in ax,ay,bx,by,dx,dy # Point in x, y bax = bx - ax bay = by - ay dax = dx - ax day = dy - ay if ((x - ax) * bax + (y - ay) * bay < 0.0) return false if ((x - bx) * bax + (y - by) * bay > 0.0) return false if ((x - ax) * dax + (y - ay) * day < 0.0) return false if ((x - dx) * dax + (y - dy) * day > 0.0) return false return true 

Answer 4

I borrowed the answer from Eric Bainville:

 0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

What in javascript looks like this:

 function pointInRectangle(m, r) { var AB = vector(rA, rB); var AM = vector(rA, m); var BC = vector(rB, rC); var BM = vector(rB, m); var dotABAM = dot(AB, AM); var dotABAB = dot(AB, AB); var dotBCBM = dot(BC, BM); var dotBCBC = dot(BC, BC); return 0 <= dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC; } function vector(p1, p2) { return { x: (p2.x - p1.x), y: (p2.y - p1.y) }; } function dot(u, v) { return ux * vx + uy * vy; } 

eg:

 var r = { A: {x: 50, y: 0}, B: {x: 0, y: 20}, C: {x: 10, y: 50}, D: {x: 60, y: 30} }; var m = {x: 40, y: 20}; 

then

 pointInRectangle(m, r); // returns true. 

Here is the code to make a conclusion as a visual test :) http://codepen.io/mattburns/pen/jrrprN

Answer 5

I understand that this is an old thread, but for those who are interested in looking at it from a purely mathematical point of view, there is an excellent thread on exchanging the mathematical stack, here:

https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle

Edit: Inspired by this thread, I put together a simple vector method to quickly determine where your point is.

Suppose you have a rectangle with points in p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3), and p4 = (x4, y4) that goes clockwise. If the point p = (x, y) lies inside the rectangle, then the point product (p - p1). (P2 - p1) will lie between 0 and | p2 - p1 | ^ 2 and (p - p1). (p4 - p1) will be between 0 and | p4 - p1 | ^ 2. This is equivalent to the projection of the vector p-p1 along the length and width of the rectangle, with p1 as the beginning.

This might make sense if I show the equivalent code:

 p21 = (x2 - x1, y2 - y1) p41 = (x4 - x1, y4 - y1) p21magnitude_squared = p21[0]^2 + p21[1]^2 p41magnitude_squared = p41[0]^2 + p41[1]^2 for x, y in list_of_points_to_test: p = (x - x1, y - y1) if 0 <= p[0] * p21[0] + p[1] * p21[1] <= p21magnitude_squared: if 0 <= p[0] * p41[0] + p[1] * p41[1]) <= p41magnitude_squared: return "Inside" else: return "Outside" else: return "Outside" 

What is it. It will also work for parallelograms.

Answer 6

If you cannot solve the problem for the rectangle, try dividing the problem into simpler tasks. Divide the rectangle into 2 triangles, check if the point is inside any of them, as they explain in here

Essentially, you cycle through the edges on each of two pairs of lines from a point. Then use the cross product to check if the point is between the two lines using the cross product. If it is checked for all three points, then the point is inside the triangle. The good thing about this method is that it does not create floating point errors that occur if you check the angles.

Answer 7

 bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) { Point AB = vect2d(A, B); float C1 = -1 * (AB.y*Ax + AB.x*Ay); float D1 = (AB.y*mx + AB.x*my) + C1; Point AD = vect2d(A, D); float C2 = -1 * (AD.y*Ax + AD.x*Ay); float D2 = (AD.y*mx + AD.x*my) + C2; Point BC = vect2d(B, C); float C3 = -1 * (BC.y*Bx + BC.x*By); float D3 = (BC.y*mx + BC.x*my) + C3; Point CD = vect2d(C, D); float C4 = -1 * (CD.y*Cx + CD.x*Cy); float D4 = (CD.y*mx + CD.x*my) + C4; return 0 >= D1 && 0 >= D4 && 0 <= D2 && 0 >= D3;} Point vect2d(Point p1, Point p2) { Point temp; temp.x = (p2.x - p1.x); temp.y = -1 * (p2.y - p1.y); return temp;} 

I just implemented AnT Answer using c ++. I used this code to check if the coordination of pixels (X, Y) is inside the shape or not.

Answer 8

If the point is inside the rectangle. On surface. For math or geodesy coordinates (GPS)

• Let the rectangle be given by the vertices A, B, C, D. Point P. The coordinates are rectangular: x, y.
• Extend the sides of the rectangle. Thus, we have 4 straight lines l _AB , l _BC , l _CD , l _DA or, for short, l ₁ , l ₂ , l ₃ , l ₄ .

• Make an equation for each l _i . An equation like:

  f _i (P) = 0.

P is the point. For points belonging to l _i , the equation is true.

• We need functions on the left side of the equations. This is f ₁ , f ₂ , f ₃ , f ₄ .
• Note that for each point on the one side of l _{i the} function f _{i is} greater than 0, and for points on the other side f _{i is} less than 0.
• Thus, if we check that P is in a rectangle, we only need p to be on the right sides of all four lines. So, we have to check four functions for their signs.
• But which side of the line is the correct one to which the rectangle belongs? This is the side where the vertices of the rectangle that do not belong to the line lie. For verification, we can choose any of two non-belonging vertices.

• So, we have to check this:

  f _AB (P) f _AB (C)> = 0

  f _BC (P) f _BC (D)> = 0

  f _CD (P) f _CD (A)> = 0

  f _DA (P) f _DA (B)> = 0

Evasions are not strict, because if the point is on the border, it also belongs to the rectangle. If you do not need points on the border, you can change the inequalities to strict ones. But while you are working in floating point operations, the choice does not matter.

• For a point that is in a rectangle, all four inequalities are true. Please note that this also works for each convex polygon, only the number of lines / equations will be different.

• It remains only to obtain the equation for the line passing through two points. This is a well-known linear equation. Let's write this for line AB and point P:

  f _AB (P) ≡ (x _A -x _B ) (y _P -y _B ) - (y _A -y _B ) (x _P -x _B )

The check can be simplified - release the rectangle clockwise - A, B, C, D, A. Then all the right sides will be to the right of the lines. Thus, we do not need to compare with the side where the other vertex is. And we need to check a set of shorter inequalities:

f _AB (P)> = 0

f _BC (P)> = 0

f _CD (P)> = 0

f _DA (P)> = 0

But this is true for a normal, mathematical (from school mathematics) coordinate set, where X is on the right and Y is at the top. And for the geodesy coordinates that are used in GPS, where X is at the top and Y to the right, we must turn the inequalities:

f _AB (P) <= 0

f _BC (P) <= 0

f _CD (P) <= 0

f _DA (P) <= 0

If you are not sure about the directions of the axes, be careful with this simplified check - check one point with a known location if you have chosen the correct equations.

Answer 9

The easiest way I thought was to simply project the point onto the axis of the rectangle. Let me explain:

If you can get a vector from the center of the rectangle to the top or bottom edge and the left or right edge. And you also have a vector from the center of the rectangle to your point, you can project this point onto your width and height vectors.

P = point vector, H = height vector, W = width vector

Get the unit vector W ', H' by dividing the vectors by their magnitude

proj_P, H = P - (PH ') H' proj_P, W = P - (PW ') W'

If I’m not mistaken, I don’t think that I ... (Correct me if I am wrong), but if the projection of your point by the height vector is less, then the height vector (which is half the height of the rectangle), and the projection value Since your point is equal to the width vector, then you have a point inside your rectangle.

If you have a universal coordinate system, you may have to calculate the height / width / point vectors using vector subtraction. The vector predictions are awesome! remember that.