Finding whether a point lies inside a rectangle or

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

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.

Answer 2

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.

Answer 3

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 l_AB, l_BC, l_CD, l_DA, or, for shortness, l₁, l₂, l₃, l₄.

• Make an equation for every l_i. The equation sort of:

  f_i(P)=0.

P is a point. For points, belonging to l_i, the equation is true.

• We need the functions on the left sides of the equations. They are f₁, f₂, f₃, f₄.
• Notice, that for every point from one side of l_i the function f_i is greater than 0, for points from the other side f_i 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:

  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

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:

  f_AB(P)   ≡   (x_A-x_B) (y_P-y_B) - (y_A-y_B) (x_P-x_B)

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:

f_AB(P) >= 0

f_BC(P) >= 0

f_CD(P) >= 0

f_DA(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:

f_AB(P) <= 0

f_BC(P) <= 0

f_CD(P) <= 0

f_DA(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.

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

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

Answer 6

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.