Finding whether a point lies inside a rectangle or not

Question

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

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

Please see here: http://mathforum.org/library/drmath/view/54386.html

Cheers.

Answer 2

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 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 need to build the line equaition 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 rectange might allow a simpler test... For example, in a rectangle (or in any other parallelogram) the values of A and B have the same maginitude but different signs for opposing (i.e. parallel) edges, which can be exploited to simplify the test.

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

If you can't solve the problem for the rectangle try dividing the problem in to easier problems. Divide the rectangle into 2 triangles an check if the point is inside any of them like they explain in here

Essentially, you cycle through the edges on every two pairs of lines from a point. Then using cross product to check if the point is between the two lines using the cross product. If it's verified for all 3 points, then the point is inside the triangle. The good thing about this method is that it does not create any float-point errors which happens if you check for angles.

Answer 5

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

0 <= dot(AB,AM) <= dot(AB,AB) &&
0 <= dot(AC,AM) <= dot(AC,AC)

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.