Finding whether a point lies inside a rectangle or not

Question

I want to find whether a point lies inside a rectangle or not. The rectangle can be oriented in any way, and need not be axis aligned.

One method I could think of was to rotate the rectangle and point coordinates to make the rectangle axis aligned and then by simply testing the coordinates of point whether they lies within that of rectangle's or not.

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

Answer 1

How is the rectangle represented? Three points? Four points? Point, sides and angle? Two points and a side? Something else? Without knowing that, any attempts to answer your question will have only purely academic value.

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

In order to test whether the point (xp, yp) lies on the left-hand 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-hand side. If D < 0, the point is on the right-hand side. If D = 0, the point is on the line.

---

The previous version of this answer described a seemingly different version of left-hand side test (see below). But it can be easily shown that it calculates the same value.

... In order to test whether the point (xp, yp) lies on the left-hand side of the edge (x1, y1) - (x2, y2), you need to build the line equation for the line containing the edge. The equation is as follows

A * x + B * y + C = 0 

where

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

Now all you need to do is to calculate

D = A * xp + B * yp + C 

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

However, this test, again, works for any convex polygon, meaning that it might be too generic for a rectangle. A rectangle might allow a simpler test... For example, in a rectangle (or in any other parallelogram) the values of A and B have the same magnitude but different signs for opposing (i.e. parallel) edges, which can be exploited 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 projections 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 vector AB, with coordinates (Bx-Ax,By-Ay), and dot(U,V) is the dot product of vectors U and V: Ux*Vx+Uy*Vy.

Update. Let's take an example to illustrate this: A(5,0) B(0,2) C(1,5) and D(6,3). From the point coordinates, we get AB=(-5,2), BC=(1,3), dot(AB,AB)=29, dot(BC,BC)=10.

For 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 query point P(6,1), we have AP=(1,1), BP=(6,-1), dot(AB,AP)=-3, dot(BC,BP)=3. P is not inside the rectangle, because its projection on side AB is not inside segment AB.