Finding whether a point lies inside a rectangle or not
AlgorithmGeometryAlgorithm Problem Overview
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?
Algorithm Solutions
Solution 1 - Algorithm
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.
Solution 2 - Algorithm
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.
Solution 3 - Algorithm
I've borrowed from Eric Bainville's answer:
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC)
Which in javascript looks like this:
function pointInRectangle(m, r) {
var AB = vector(r.A, r.B);
var AM = vector(r.A, m);
var BC = vector(r.B, r.C);
var BM = vector(r.B, 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 u.x * v.x + u.y * v.y;
}
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's a codepen to draw the output as a visual test :) http://codepen.io/mattburns/pen/jrrprN
Solution 4 - Algorithm
# 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
Solution 5 - Algorithm
I realise this is an old thread, but for anyone who's interested in looking at this from a purely mathematical perspective, there's an excellent thread on the maths stack exchange, here:
https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle
Edit: Inspired by this thread, I've put together a simple vector method for quickly determining where your point lies.
Suppose you have a rectangle with points at p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) and p4 = (x4, y4), going clockwise. If a point p = (x, y) lies inside the rectangle, then the dot product (p - p1).(p2 - p1) will lie between 0 and |p2 - p1|^2, and (p - p1).(p4 - p1) will lie between 0 and |p4 - p1|^2. This is equivalent to taking the projection of the vector p - p1 along the length and width of the rectangle, with p1 as the origin.
This may make more sense if I show an 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"
And that's it. It will also work for parallelograms.
Solution 6 - Algorithm
bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) {
Point AB = vect2d(A, B); float C1 = -1 * (AB.y*A.x + AB.x*A.y); float D1 = (AB.y*m.x + AB.x*m.y) + C1;
Point AD = vect2d(A, D); float C2 = -1 * (AD.y*A.x + AD.x*A.y); float D2 = (AD.y*m.x + AD.x*m.y) + C2;
Point BC = vect2d(B, C); float C3 = -1 * (BC.y*B.x + BC.x*B.y); float D3 = (BC.y*m.x + BC.x*m.y) + C3;
Point CD = vect2d(C, D); float C4 = -1 * (CD.y*C.x + CD.x*C.y); float D4 = (CD.y*m.x + CD.x*m.y) + 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's Answer using c++. I used this code to check whether the pixel's coordination(X,Y) lies inside the shape or not.
Solution 7 - Algorithm
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.
Solution 8 - Algorithm
If a point is inside a rectangle. On a plane. For mathematician or geodesy (GPS) coordinates
-
Let the rectangle be set by vertices A, B, C, D. The point is P. Coordinates are rectangular: x, y.
-
Lets prolong the sides of the rectangle. So we have 4 straight lines lAB, lBC, lCD, lDA, or, for shortness, l1, l2, l3, l4.
-
Make an equation for every li. The equation sort of:
fi(P)=0.
P is a point. For points, belonging to li, the equation is true.
-
We need the functions on the left sides of the equations. They are f1, f2, f3, f4.
-
Notice, that for every point from one side of li the function fi is greater than 0, for points from the other side fi is lesser than 0.
-
So, if we are checking for P being in rectangle, we only need for the p to be on correct sides of all four lines. So, we have to check four functions for their signs.
-
But what side of the line is the correct one, to which the rectangle belongs? It is the side, where lie the vertices of rectangle that don't belong to the line. For checking we can choose anyone of two not belonging vertices.
-
So, we have to check this:
fAB(P) fAB(C) >= 0
fBC(P) fBC(D) >= 0
fCD(P) fCD(A) >= 0
fDA(P) fDA(B) >= 0
The unequations are not strict, for if a point is on the border, it belongs to the rectangle, too. If you don't need points on the border, you can change inequations for strict ones. But while you work in floating point operations, the choice is irrelevant.
-
For a point, that is in the rectangle, all four inequations are true. Notice, that it works also for every convex polygon, only the number of lines/equations will differ.
-
The only thing left is to get an equation for a line going through two points. It is a well-known linear equation. Let's write it for a line AB and point P:
fAB(P) ≡ (xA-xB) (yP-yB) - (yA-yB) (xP-xB)
The check could be simplified - let's go along the rectangle clockwise - A, B, C, D, A. Then all correct sides will be to the right of the lines. So, we needn't compare with the side where another vertice is. And we need check a set of shorter inequations:
fAB(P) >= 0
fBC(P) >= 0
fCD(P) >= 0
fDA(P) >= 0
But this is correct for the normal, mathematician (from the school mathematics) set of coordinates, where X is to the right and Y to the top. And for the geodesy coordinates, as are used in GPS, where X is to the top, and Y is to the right, we have to turn the inequations:
fAB(P) <= 0
fBC(P) <= 0
fCD(P) <= 0
fDA(P) <= 0
If you are not sure with the directions of axes, be careful with this simplified check - check for one point with the known placement, if you have chosen the correct inequations.
Solution 9 - Algorithm
The easiest way I thought of was to just project the point onto the axis of the rectangle. Let me explain:
If you can get the 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 that point onto your width and height vectors.
P = point vector, H = height vector, W = width vector
Get Unit vector W', H' by dividing the vectors by their magnitude
proj_P,H = P - (P.H')H' proj_P,W = P - (P.W')W'
Unless im mistaken, which I don't think I am... (Correct me if I'm wrong) but if the magnitude of the projection of your point on the height vector is less then the magnitude of the height vector (which is half of the height of the rectangle) and the magnitude of the projection of your point on the width vector is, then you have a point inside of your rectangle.
If you have a universal coordinate system, you might have to figure out the height/width/point vectors using vector subtraction. Vector projections are amazing! remember that.
Solution 10 - Algorithm
In continuation matts answer. we need to use https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle/190373#190373 solution to make it work
Below does not work
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC)
Below works
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(AM,AC) <= dot(AC,AC)
you check by pasting below in javascript console //Javascript solution for same
var screenWidth = 320;
var screenHeight = 568;
var appHeaderWidth = 320;
var AppHeaderHeight = 65;
var regionWidth = 200;
var regionHeight = 200;
this.topLeftBoundary = {
A: {x: 0, y: AppHeaderHeight},
B: {x: regionWidth, y: AppHeaderHeight},
C: {x: 0, y: regionHeight + AppHeaderHeight},
D: {x: regionWidth, y: regionHeight + AppHeaderHeight}
}
this.topRightBoundary = {
A: {x: screenWidth, y: AppHeaderHeight},
B: {x: screenWidth - regionWidth, y: AppHeaderHeight},
C: {x: screenWidth, y: regionHeight + AppHeaderHeight},
D: {x: screenWidth - regionWidth, y: regionHeight + AppHeaderHeight}
}
this.bottomRightBoundary = {
A: {x: screenWidth, y: screenHeight},
B: {x: screenWidth - regionWidth, y: screenHeight},
C: {x: screenWidth, y: screenHeight - regionHeight},
D: {x: screenWidth - regionWidth, y: screenHeight - regionHeight}
}
this.bottomLeftBoundary = {
A: {x: 0, y: screenHeight},
B: {x: regionWidth, y: screenHeight},
C: {x: 0, y: screenHeight - regionHeight},
D: {x: regionWidth, y: screenHeight - regionHeight}
}
console.log(this.topLeftBoundary);
console.log(this.topRightBoundary);
console.log(this.bottomRightBoundary);
console.log(this.bottomLeftBoundary);
checkIfTapFallsInBoundary = function (region, point) {
console.log("region " + JSON.stringify(region));
console.log("point" + JSON.stringify(point));
var r = region;
var m = point;
function vector(p1, p2) {
return {
x: (p2.x - p1.x),
y: (p2.y - p1.y)
};
}
function dot(u, v) {
console.log("DOT " + (u.x * v.x + u.y * v.y));
return u.x * v.x + u.y * v.y;
}
function pointInRectangle(m, r) {
var AB = vector(r.A, r.B);
var AM = vector(r.A, m);
var AC = vector(r.A, r.C);
var BC = vector(r.B, r.C);
var BM = vector(r.B, m);
console.log("AB " + JSON.stringify(AB));
console.log("AM " + JSON.stringify(AM));
console.log("AM " + JSON.stringify(AC));
console.log("BC " + JSON.stringify(BC));
console.log("BM " + JSON.stringify(BM));
var dotABAM = dot(AB, AM);
var dotABAB = dot(AB, AB);
var dotBCBM = dot(BC, BM);
var dotBCBC = dot(BC, BC);
var dotAMAC = dot(AM, AC);
var dotACAC = dot(AC, AC);
console.log("ABAM " + JSON.stringify(dotABAM));
console.log("ABAB " + JSON.stringify(dotABAB));
console.log("BCBM " + JSON.stringify(dotBCBM));
console.log("BCBC " + JSON.stringify(dotBCBC));
console.log("AMAC " + JSON.stringify(dotAMAC));
console.log("ACAC" + JSON.stringify(dotACAC));
var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotBCBM && dotBCBM <= dotBCBC));
console.log(" first check" + check);
var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotAMAC && dotAMAC <= dotACAC));
console.log("second check" + check);
return check;
}
return pointInRectangle(m, r);
}
//var point = {x: 136, y: 342};
checkIfTapFallsInBoundary(topLeftBoundary, {x: 136, y: 342});
checkIfTapFallsInBoundary(topRightBoundary, {x: 136, y: 274});
checkIfTapFallsInBoundary(bottomRightBoundary, {x: 141, y: 475});
checkIfTapFallsInBoundary(bottomRightBoundary, {x: 131, y: 272});
checkIfTapFallsInBoundary(bottomLeftBoundary, {x: 131, y: 272});