How to check if a point is inside a rectangle?

Question

There is a point $(x,y)$, and a rectangle $a(x_1,y_1),b(x_2,y_2),c(x_3,y_3),d(x_4,y_4)$, how can one check if the point inside the rectangle?

Answer 1

$M$ of coordinates $(x,y)$ is inside the rectangle iff

$$(0<\textbf{AM}\cdot \textbf{AB}<\textbf{AB}\cdot \textbf{AB}) \land (0<\textbf{AM}\cdot \textbf{AD}<\textbf{AD}\cdot \textbf{AD})$$

(scalar products of vectors, $\land$ stands for logical AND).

Answer 2

Let $P(x,y)$, and rectangle $A(x_1,y_1),B(x_2,y_2),C(x_3,y_3),D(x_4,y_4)$

Calculate the sum of areas of $\triangle APD, \triangle DPC, \triangle CPB, \triangle PBA$.

1. If this sum is greater than the area of the rectangle, then $P(x,y)$ is outside the rectangle.

2. Else if this sum is equal to the area of the rectangle (observe that this sum cannot be less than the latter),

   1. if area of any of the triangles is $0$, then $P(x,y)$ is on the rectangle (in fact on that line corresponding to the triangle of area$=0$). Observe that the equality of the sum is necessary; it is not sufficient that area$=0$),

   2. else $P(x,y)$ is is inside the rectangle.

Acceptably this approach needs substantial amount of computation. This approach can be employed to any irregular polygon, too.

---

Another way is to calculate the perpendicular distances of $P(x,y)$ from all the 4 lines $AB,CD, AD,BC$

To be inside the rectangle, the perpendicular distances from $AB, P_{AB}$(say) and from $CD, P_{CD}$(say) must be less than $|AD|=|BC|$ and the perpendicular distances from $AD, P_{AD}$(say) and from $BC, P_{BC}$(say) must be less than $|CD|=|AB|$. Here , the areas of each of the four triangles < $\frac{1}{2}$the area of the rectangle.

1. If one of the perpendicular distances is greater than the respective length, then $P(x,y)$ is outside the rectangle.

   This essentially implies and is implied by the statement : the area of the respective triangle > $\frac{1}{2}$the area of the rectangle (as commented by Ben Voigt) as $\triangle APD=\frac{1}{2}AD\cdot P_{AD}$.

2. Else if $ P_{AB}=0$ and $P_{CD}=|AD|$ , then $P(x,y)$ is on AB . So, $\triangle PBA=0$ and $\triangle PCD=\frac{1}{2}$the area of the rectangle.

   Observe that in this case, the remaining two perpendicular distances $P_{AD}, P_{BC}$ must be ≤ $|AB|=|CD|$, $P_{BC}=|AB|\implies P(x,y)$ is lies on AD i.e, P coincides with A as it is already on AB .

Answer 3

I would use a "point-in-convex-polygon" function; this works by checking whether the point is "to the left of" each of the four lines.

Answer 4

For example, if all the triangles $ABP$, $BCP$, $CDP$, $DAP$ are positively oriented; for $ABP$ this can be tested by checking the sign of $(x-x_1)\cdot(y-y_2)-(y-y_1)\cdot(x-x_2)$. This method generalizes to convex polygons.

Alternatively, find a transformation that makes the rectangle parallel to the axes. Apply the same transformation to your point at the test is simple. This is especially helpful if you want to test many points against the same rectangle.

Answer 5

Given how much attention this post has gotten and how long ago it was asked, I'm surprised that no one here mentioned the following method.

A rectangle is the image of the unit square under an affine map. Simply apply the inverse of this affine map to the point in question, and then check if the result is in the unit square or not.

To make things clear, consider the following image,

where the vectors in the pictures are $\mathbf{u} = c - d$, $\mathbf{v} = a - d$, and $\mathbf{w} = d$.

Since the legs of a rectangle are perpendicular, the matrix $\begin{bmatrix}\mathbf{u} & \mathbf{v}\end{bmatrix}$ is orthogonal and so we even have a simple formula for the inverse: $$\begin{bmatrix}\mathbf{u} & \mathbf{v}\end{bmatrix}^{-1} = \begin{bmatrix}\mathbf{u}^T/||u||^2 \\ \mathbf{v}^T/||v||^2\end{bmatrix}.$$

If you want to check many points for the same rectangle, this matrix can be easily precomputed and stored, so that you perform the (typically more expensive) division operations only once at the start. Then you only need to do a few multiplications, additions, and subtractions for each point you are testing.

This method also applies more generally to checking whether a point is in a parallelogram, though in the parallelogram case the matrix inverse does not take such a simple form.

Answer 6

The point is inside the rectangle.

The point is outside the rectangle.

Let us define:
A: area of the rectangle
A_i: areas of the triangles shown in the pictures. (i = 1, 2, 3, 4)
a_i: lengths of the edges shown in the pictures. (i = 1, 2, 3, 4)
b_i: lengths of the line segments connecting the point and the corners. (i = 1, 2, 3, 4)

If the point is inside the rectangle, the following equation holds:
$ \mathbf{A = A_1 + A_2 + A_3 + A_4} $

If the point is outside the rectangle, the following inequality holds:
$ \mathbf{A > A_1 + A_2 + A_3 + A_4} $

How do we calculate A, A₁, A₂, A₃, A₄, a₁, a₂, a₃, a₄, b₁, b₂, b₃ and b₄?

First we calculate the edge lengths:

$ a_1 = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \\ a_2 = \sqrt{(x_2 - x_3)^2 + (y_2 - y_3)^2} \\ a_3 = \sqrt{(x_3 - x_4)^2 + (y_3 - y_4)^2} \\ a_4 = \sqrt{(x_4 - x_1)^2 + (y_4 - y_1)^2} $

Next we calculate the lengths of the line segments:

$ b_1 = \sqrt{(x_1 - x)^2 + (y_1 - y)^2} \\ b_2 = \sqrt{(x_2 - x)^2 + (y_2 - y)^2} \\ b_3 = \sqrt{(x_3 - x)^2 + (y_3 - y)^2} \\ b_4 = \sqrt{(x_4 - x)^2 + (y_4 - y)^2} $

Then we calculate the areas using Heron's Formula:

$ A \,\,\, = a_1a_2 = a_2a_3 = a_3a_4 = a_4a_1 \\ u_1 = \frac{a_1 + b_1 + b_2}{2} \\ u_2 = \frac{a_2 + b_2 + b_3}{2} \\ u_3 = \frac{a_3 + b_3 + b_4}{2} \\ u_4 = \frac{a_4 + b_4 + b_1}{2} \\ A_1 = \sqrt{u_1(u_1 - a_1)(u_1 - b_1)(u_1 - b_2)} \\ A_2 = \sqrt{u_2(u_2 - a_2)(u_2 - b_2)(u_2 - b_3)} \\ A_3 = \sqrt{u_3(u_3 - a_3)(u_3 - b_3)(u_3 - b_4)} \\ A_4 = \sqrt{u_4(u_4 - a_4)(u_4 - b_4)(u_4 - b_1)} $

Finally you can do the area test to check if the point is inside or outside the rectangle.

Answer 7

One of the simplest algorithms of coordinate plane geometry is a method of "Is the vector $\vec{w}$ clockwise or counterclockwise from the vector $\vec{v}$?"

The algorithm is to compute the cross product $\vec{v} \times \vec{w}$. If the sign is positive, then $\vec{w}$ is counter-clockwise from $\vec{v}$. If negative, it is clockwise.

This method gives an algorithm for answering the question "Which side of a line is a point on?"

e.g. consider the left line of your box, line $da$, directed from $d$ to $a$. The point $p=(x,y)$ is on the right side of this line if and only if the vector $dp$ is clockwise from $da$. So we can simply compute the cross product to learn if $p$ is on the correct side of $da$ or not.

Do this with all four lines, and you have your test.

---

If you're using the same four points a lot, we can get away with half as much work. We can use the dot product to compute "How long is one vector in the direction another is pointing?"

We can compute the dot product of $da$ with $dp$. If this number is greater than the dot product of $da$ with itself, then your point is too far up to be in the box. If this number is negative, the point is too far down to be in the box.

Because this checks two boundaries at once, we only have to do this twice: once with $da$ to get the up-down location, and once with $dc$ to get the left-right location.

---

EDIT: One of the general ideas at play is to try and make as much use of the dot product and cross product as you can, as they are computationally efficient ways of computing geometric information related to things like length, angle, and area.

So a common strategy for a problem of computational geometry is to try and phrase the problem in terms of things that can be answered with dot and cross products. If that's not immediately obvious, phrase it in terms of (directed) lengths, angles, and areas, and try to rephrase those in terms of dot and cross products.

My approach to the question was to express "which side of a line?" as a directed angle, allowing use of cross product.

Also, I used the dot product to compute distance along a direction parallel to one of the sides of the rectangle. You could compute the same thing as "perpendicular distance" from an adjacent side, which would let you use the cross product.

Some of the other answers express things in terms of the areas of triangles -- these are naturally computed cross products. One answer summed their magnitudes and compared with the area of the rectangle. Another looked at the direction of the areas instead (i.e. whether the triangles were positively oriented).

Answer 8

You can use complex analysis to check (which is really overkill and probably not computationally efficient but still neat and generalizes to all polygons without any difficulty). Specifically, identify the point $(a,b)$ with the complex number $a+bi$. Let $\gamma$ parametrize the rectangle by going around once counterclockwise. By Cauchy integral formula we know that

$\displaystyle \frac{1}{2 \pi i}\int_\gamma \frac{1}{z-x-iy}dz = \left\{ \begin{array}{lr} 1 \mbox{ if (x,y) is in the rectangle} \\ 0 \mbox{ if (x,y) is outside the rectangle} \end{array} \right.$

and is not defined if (x,y) is on any of the four boundary segments.

The integral is over 4 strait line segments. On the strait line segment from $(x_2,y_2)$ to $(x_1,y_1)$, the integral is just

$\displaystyle \int_0^1 \frac{x_1-x_2+i(y_1-y_2)}{t(x_1-x_2+i(y_1-y_2))+x_2-x+i(y_2-y)} dt = \int_0^1 \frac{1}{t-w_1}$

where $w_1= \frac{x_2-x+i(y_2-y)}{x_2-x_1+i(y_2-y_1)}$. This integral can be done so long as $w_1 \not \in [0,1]$, which corresponds to (x,y) on the segment. The result is $\log(1-w_1)-\log(-w_1)$. Note that this is a holomorphic function of $w_1$ on $\mathbb{C} - [0,1]$, where we have adopted the branch cut for $\log$ as $\log(r e^i \theta)= \ln(r) + i \theta$ for $\theta \in (-\pi, \pi]$.

Summing over the four edges gives the left hand side above as $\frac{1}{2 \pi i}\displaystyle \sum_{j=1}^4 \log(1-w_j)- \log(w_j)$ where $w_2,w_3$, and $w_4$ are defined analogously to $w_1$. You only need compute this sum to sufficient precision to rule out it equaling either 0 or 1. As I said before this isn't usually a good way in practice, partially because logs are pretty computationally expensive, but it is a way to do this.

Answer 9

How can there be no vector math solutions to this yet?

Let $(x',y')=(x-x_1,y-y_1)$ so that the point $(x_1,y_1)$ is the origin.. Then get the height and width of the rectangle

$w = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$

$h = \sqrt{(x_4-x_1)^2 + (y_4-y_1)^2}$

And then see whether $(x',y')$ is within that rectangle

$0 \leq x'{(x_2-x_1) \over w} + y'{(y_2-y_1) \over h} \leq w$

$0 \leq x'{(x_4-x_1) \over w} + y'{(y_4-y_1) \over h} \leq h$

Done! Way easier than the triangle methods--those are for generic convex polygons and are awesome if you have a convex polygon, but are overkill for a rectangle.

(It's even shorter to use the vector forms. If your coordinates are $\vec{p},\dots,\vec{p_4}$ then subtract $\vec{p_1}$ from everyone to get $\vec{p'}, \vec{p_2'}, \vec{p_4'}$. Then you're in the rectangle iff $0 \leq \vec{p'}\cdot\hat{p_2'} \leq p_2'$ and $0 \leq \vec{p'}\cdot\hat{p_4'} \leq p_4'$.)

Answer 10

It is very easy.

Just divide Rectangle in 2 triangle i.e.

1) a(x1,y1),b(x2,y2),c(x3,y3)
2) a(x1,y1),d(x4,y4),c(x3,y3)

Then, point is in Rectangle, if and only if point is in at least 1 triangle.

Following is code for checking point in triangle :

float sign(fPoint p1, fPoint p2, fPoint p3)
{
  return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle(fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
  bool b1, b2, b3;

  b1 = sign(pt, v1, v2) < 0.0f;
  b2 = sign(pt, v2, v3) < 0.0f;
  b3 = sign(pt, v3, v1) < 0.0f;

  return ((b1 == b2) && (b2 == b3));
}

Answer 11

For me, the basic tool to use answers the question "are two points on the same side of a line?"

If the equation of the line is $ax+by+c = 0$ and the points are $(x_i, y_i)$ for $i = 1, 2$, compute $d_i = a x_i + b y_i + c$ for each $i$. If the two $d_i$ have the same sign (both $> 0$ or $< 0$ to avoid problems about being on the line), they are on the same side of the line.

We now use this. Compute the point that is the average of the four vertices. We know that this is inside the rectangle - this will work for a triangle also, where this problem more commonly occurs.

For each line making up the rectangle, do the "two points on the same side of a line" test using the average point and your test point. If the average point and your test are on the same side for each line (though they may be on different sides for different lines), the point is inside the rectangle.

Doing it this way, there are no worries about orientation or traversing the vertices of the rectangle in a certain order.

Answer 12

Consider the rectangle as defining a coordinate system with origin $A$ and basis vectors $v_1 = B-A$ and $v_2 = D-A$. We can find the point $p = (x,y)$ in terms of this coordinate system as $\left(\frac{(p - A)·v_1}{v_1·v_1}, \frac{(p - A)·v_2}{v_2·v_2}\right)$. The coordinates of this transformed point are within the range 0 to 1 if and only if the point is within the rectangle.

This is equivalent to Raymond Manzoni's answer, but I thought it worth deriving in this fashion.

Answer 13

This is intutition at work, but what if you found the distances from the vertices to the point and added them all up?

Your min would be the distances to the center of the rectangle and your max is the distances if your point was on one of the vertices.

For example, for a 3x4 triangle, you min would be 10 (two times your diagonal) and your max would be 12 (if your point was on a vertex). This is your range: the point is inside the rectangle, if your distances from the vertices to the point are within the range 10 to 12 (for a 3x4 rectangle).

Answer 14

I had this observation and it may be useful (but may be wrong too, as I have not proved it formally, so this text is proposed as a comment rather than a formal answer).

A rectangle can be divided into four inner rectangles with no gaps and as a result, there would be $1$ point that is common to all resulting 4 inner rectangles. Let that point be $p1$ in the picture below.

$p1$, has the following property: We could draw 2 lines intersecting at $p1$ such that each of the lines going through p1 is perpendicular on 1 of the rectangle sides. For example, Line $DC$ is perpendicular on line segment $v1v2$ and Line $AB$ is perpendicular on line segment $v4v1$.

The above property of $p1$ can't be satisfied by any point outside the rectangle.

Now, given a point $p1$, and 4 points that represent the rectangle corners, we may apply the above property to determine if p1 lies within the rectangle or not.

Answer 15

Check if your point is inside triangle a,b,c or inside triangle a,c,d. There are several methods for doing this. See e.g. http://www.blackpawn.com/texts/pointinpoly/default.html or https://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle

Answer 16

My first thought was to divide rectangle to two triangles and apply some optimized method twice. It seemed to be more effective than @lab bhattacharjee's answer to me.

http://www.blackpawn.com/texts/pointinpoly/default.html

Answer 17

Rotate the rectangle 4 boundary points and detection point so that the bottom left corner of the rectangle becomes the origin. Change the coordinates of the point relative to the bottom left of the rectangle. Do simple boundary check for x and y axes. Done.

Answer 18

First of all, we have to choose 2 adjacent sides of the rectangle and then form the equations that contains them. The second step is to create 2 equations that contains the 2 slopes of the equations of the 2 adjacent sides and the critical point. Now we'll equate the equation that contains a side of a rectangle with slope m to one equation that contains the critical point and the slope -1/m, and then will equate the left equations. We'll also take into account that each solution has to respect the inequalities that can be easily deduced by checking the coordinates of the 2 adjacent sides. If we get 2 intersection points that respect the inequalities, then the critical point is inside the rectangle.

Q.E.D.

Answer 19

You could use a different coordinate system, and reduce the problem to the case when one of the rectangle's legs is on the x axis and the others parallel to the y. In this case, you just see if the x and y inequalities for the rectangle are satisfied by your point. By a change of coordinate system, I mean simply choosing one of the vertices of the rectangle to be the origin, and using two perpendicular unit vectors for each of the adjacent sides (to the corner). Then, since you know the length of the sides of the rectangle, you can easily deduce the necessary rectangle inequalities.

NB by rectangle inequalities I mean the necessary and sufficient inequalities that must be satisfied in order for a point to lie in a rectangle in the first case.

Answer 20

Calculate $\perp$ distances of point $P$ from all sides of rectangle and check if any of the distances of point from opposite sides is greater than the distance between them (one of the side length of rectangle). If it is greater than it is outside otherwise inside.

Answer 21

let pi, xi, yi be the coordinate of p, x and y in the ith dimension

for i=1 to n
    if polarity(pi-xi, pi-yi) != -1 return false;
return true;

bool polarity(z){
    // z == 0 needs to be filtered out
    if (z > 0) return 1;
    if (z < 0) return -1;
}

bool polarity(px, py) {
    if (px == py) return -1;    // only happens when x = p = y
    if (px == 0) return -1;
    if (py == 0) return -1;
    return polarity(px) * polarity(py);
}

Possible to replace multiplication with bool function.

Answer 22

Let $(1,2,3,4)$ be the numbering of vertices in common Cartesian coordinates $(x,y)$. For a triangle we define local (so-called isoparametric) coordinates $(\xi,\eta)$ as: $$ \Delta = (x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1) \\ \xi = [(y_3-y_1)(x-x_1)-(x_3-x_1)(y-y_1)]/\Delta \\ \eta = [(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1)]/\Delta $$ And the Inside-Outside function as: $$ \operatorname{IO}(x,y) = \min(\xi,\eta,1-\xi-\eta) $$ Then we have that a pont $(x,y)$ is inside the triangle if $\,\operatorname{IO}(x,y)\gt 0\,$, it is outside the triangle if $\,\operatorname{IO}(x,y)\lt 0\,$ and it is on the boundary if $\,\operatorname{IO}(x,y) = 0\,$.
More information and a useful application is found at:

• 2-D and 3-D Point Probes

From the following reference we have the details below.

• Quadrilateral Interpolation

Analogously to a triangle we have for the quadrilateral, in local / isoparametric coordinates $(\xi,\eta)$: $$ N_1(\xi,\eta) = \frac{1}{4}(1-\xi)(1-\eta) = \frac{1}{4}(1-\xi-\eta+\xi\eta)\\ N_2(\xi,\eta) = \frac{1}{4}(1+\xi)(1-\eta) = \frac{1}{4}(1+\xi-\eta-\xi\eta)\\ N_3(\xi,\eta) = \frac{1}{4}(1-\xi)(1+\eta) = \frac{1}{4}(1-\xi+\eta-\xi\eta)\\ N_4(\xi,\eta) = \frac{1}{4}(1+\xi)(1+\eta) = \frac{1}{4}(1+\xi+\eta+\xi\eta) $$ The global (common Cartesian) coordinates $(x,y)$ are calculated herefrom: $$ \begin{cases} x = N_1(\xi,\eta)x_1 + N_2(\xi,\eta)x_2 + N_3(\xi,\eta)x_3 + N_4(\xi,\eta)x_4 \\ y = N_1(\xi,\eta)y_1 + N_2(\xi,\eta)y_2 + N_3(\xi,\eta)y_3 + N_4(\xi,\eta)y_4 \end{cases} $$ It is trivial that the vertices are given by: $$ (\xi,\eta)=(-1,-1) \;\rightarrow\; (x,y)=(x_1,y_1) \\ (\xi,\eta)=(+1,-1) \;\rightarrow\; (x,y)=(x_2,y_2) \\ (\xi,\eta)=(-1,+1) \;\rightarrow\; (x,y)=(x_3,y_3) \\ (\xi,\eta)=(+1,+1) \;\rightarrow\; (x,y)=(x_4,y_4) $$ Using abbreviations $(A,B,C,D)$ may be helpful. $$ \begin{cases} x = A_x + B_x\xi + C_x\eta + D_x\xi\eta \\ y = A_y + B_y\xi + C_y\eta + D_y\xi\eta \end{cases} $$ It's easy to see that the constants are given by: $$ A_x = \frac{1}{4}(+x_1+x_2+x_3+x_4) \quad ; \quad A_y = \frac{1}{4}(+y_1+y_2+y_3+y_4) \\ B_x = \frac{1}{4}(-x_1+x_2-x_3+x_4) \quad ; \quad B_y = \frac{1}{4}(-y_1+y_2-y_3+y_4) \\ C_x = \frac{1}{4}(-x_1-x_2+x_3+x_4) \quad ; \quad C_y = \frac{1}{4}(-y_1-y_2+y_3+y_4) \\ D_x = \frac{1}{4}(+x_1-x_2-x_3+x_4) \quad ; \quad D_y = \frac{1}{4}(+y_1-y_2-y_3+y_4) $$ In general, calculating the local coordinates from the global ones is a highly non-trivial exercise. But it seems that we are lucky: the rectangle in the question is a parallelogram. In that case, Wikipedia teaches us that The diagonals bisect each other: $$ \frac{1}{2} \left(\begin{bmatrix} x_1 \\ y_1 \end{bmatrix} + \begin{bmatrix} x_4 \\ y_4 \end{bmatrix}\right) = \frac{1}{2} \left(\begin{bmatrix} x_2 \\ y_3 \end{bmatrix} + \begin{bmatrix} x_2 \\ y_3 \end{bmatrix}\right) $$ Consequently, for a parallelogram, the non-linear $\,\xi\eta\,$ factors drop out. So our equations become: $$ \begin{cases} B_x\xi + C_x\eta = x-A_x \\ B_y\xi + C_y\eta = y-A_y \end{cases} $$ Two linear equations in two unknowns which can be easily solved with Cramer's rule: $$ \xi = \frac{B_x(y-A_y)-B_y(x-A_x)}{B_xC_y-B_yC_x} \\ \eta = \frac{C_y(x-A_x)-C_x(y-A_y)}{C_yB_x-C_xB_y} $$ Now the Inside-Outside function for a general quadrilateral may be defined as: $$ \operatorname{IO}(x,y) = \min\left[N_1(\xi,\eta),N_2(\xi,\eta),N_3(\xi,\eta),N_4(\xi,\eta)\right] $$ Then we have that a point $(x,y)$ is inside the quadrilateral if $\,\operatorname{IO}(x,y)\gt 0\,$, it is outside the quadrilateral if $\,\operatorname{IO}(x,y)\lt 0\,$ and it is on the boundary if $\,\operatorname{IO}(x,y) = 0\,$. The calculations are quite feasible only for parallelograms. Summarizing the recipe:

1. Calculate $(A_x,B_x,C_x)$ and $(A_y,B_y,C_y)$ from the vertex coordinates
2. Calculate $(\xi,\eta)$ from $(x,y)$ with the above Cramer's solution
3. Calculate the four shape functions $N_k(\xi,\eta) = (1\pm\xi)(1\pm\eta)/4$
4. Calculate the Inside-Outside function as the minimum of them

Answer 23

find the equations of the lines and equate the distance from the point P TO THE GIVEN TWO Pairs of lines .if the point is inside the rectangle,the distances to the pairs will be less than the distances between the line in the pair