How to check if a point is inside a rectangle?

Solution 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 product of vectors)

Solution 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 .

Solution 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.

Solution 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.

Solution 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.