[Math] Detect if point is within rotated rectangles bounds

collision detectiongeometry

I need to detect whether one of rectangles is within the other one.

The title says 'point' – because I wanted to approach it by checking if any of the corners (points) is inside the other rectangle, but it doesn't seem to work so when both rectangles are rotated (I was simply checking if $XY$ of the corner is between $XY$ of two other corners.

Mind you I'm not trying to detect if the objects will collide – I'm trying to detect if one is inside the other.

Here's an image explaining what I'm trying to get done:
The rectangles to the right work flawlessly, but the ones to the left not.

enter image description here

Best Answer

Basic vector algebra suffices here!

[Rewritten on 2016-06-01, using more general solution with the same "cost", number of multiplications, additions, etc.]

Let's assume the blue parallelogram is your bounding box, and the red one (on the right) is the test rectangle -- or, really, any set of points you might wish to test: Example diagram

You pick one corner of the parallelogram as its origin ($\vec{b}_0 = (x_0, y_0)$). We don't use the point diagonally opposite. We call one edge $\vec{n}_u = (x_u, y_u)$, and another $\vec{n}_v = (x_v, y_v)$; both start at the $\vec{b}_0 = (x_0, y_0)$ point.

Note that this means the other points on the parallelogram are $$\vec{b}_w = \vec{b}_0 + \vec{n}_u = (x_0 + x_u, \; y_0 + y_u) \\ \vec{b}_h = \vec{b}_0 + \vec{n}_v = (x_0 + x_v, \; y_0 + y_v)$$ and the unmarked fourth point is at $(x_0 + x_u + x_v, \; y_0 + y_u + y_v)$.

We can transform to a coordinate system that is rotated, translated, scaled, and skewed so that the original parallelogram is at coordinates $(0,0)$-$(1,0)$-$(1,1)$-$(0,1)$. Let's call these coordinates $(u,v)$.

To convert back to ordinary coordinates we use $$\begin{cases} x = x_0 + u x_u + v x_v \\ y = y_0 + u y_u + v y_v \end{cases}$$ Solving the above for $u$ and $v$ gives us the interesting conversion to the $(u,v)$ coordinates: $$\begin{cases} u = \frac{(x - x_0)y_v - (y - y_0)x_v}{x_u y_v - y_u x_v} \\ v = \frac{(y - y_0)x_u - (x - x_0)y_u}{x_u y_v - y_u x_v} \\ \end{cases}$$

Combining the conversion with the limits shown earlier, we can condense the test. Do note that the divisor (or limit), $$L = x_u y_v - y_u x_v$$ may be positive or negative. A point $(x,y)$ is inside our bounding parallelogram if and only if $$L \gt 0: \begin{cases} 0 \le (x - x_0)y_v - (y - y_0)x_v \le L \\ 0 \le (y - y_0)x_u - (x - x_0)y_u \le L \end{cases} \\ L \lt 0: \begin{cases} 0 \le (y - y_0)x_v - (x - x_0)y_v \le -L \\ 0 \le (x - x_0)y_u - (y - y_0)x_u \le -L \end{cases}$$ $L \ne 0$ unless one or both edges are zero length, or if they are parallel. In fact, $L$ is actually the area of the parallelogram; zero $L$ means the parallelogram has zero area (vanishes).

Now, I originally had a "simpler" test using direct projection (dot product, also known as projection product), but it only works if the edges are perpendicular to each other. This one works for squares, rectangles, and parallelograms -- and has exactly the same number of multiplications and additions; only the sign check is extra -- so this one is clearly better choice.

Let's look at OP's example bounding box, with corners at $(1,6)$, $(-6,-5)$, $(2,-9)$, and $(9,3)$. I'll choose, arbitrarily, $$\begin{cases} \vec{b}_0 = (-6, -5) \\ \vec{b}_w = (1, 6) \\ \vec{b}_h = (2, -9) \end{cases} \iff \left\lbrace\begin{array}{ll} x_0 = -6, & y_0 = -5 \\ x_u = 7, & y_u = 11 \\ x_v = 8, & y_v = -4 \end{array}\right.$$

This means that the fourth point is actually $(-6+7+8,-5+11-4) = (9,2)$, and not $(9,3)$; OP's bounding region is a quadrilateral, not a parallelogram. (Because $\vec{n}_u\cdot\vec{n}_v = 7\cdot8-11\cdot4 = 12 \ne 0$, the edges are not perpendicular; the box is not rectangular either way.)

So, assuming the fourth corner of the bounding parallelogram is at $(9,2)$, we can test for some points. We have $$L = 7(-4) - 8(11) = -116$$and therefore the inclusion tests are $$\begin{cases} 0 \; \le \; (y + 5)8 + (x + 6)4 \; \le \; 116\\ 0 \; \le \; (x + 6)11 - (y + 5)7 \; \le \; 116 \end{cases}$$

Let's check point $(x,y) = (12, 16)$ first. (We know it has to be outside.) $$\begin{cases} (y+5)8 + (x+6)4 = (16+5)8 + (12+6)4 = 240 \\ (x+6)11 - (y+5)7 = (12+6)11 - (16+5)7 = 51 \end{cases}$$ the first is greater than $116$, so the point is definitely outside.

Let's check point $(x,y) = (3,3)$. Remember, OP's diagram has a quadrilateral, which should be fixed to put the fourth corner at $(9,2)$, to make it a quadrilateral. $$\begin{cases} (y+5)8 + (x+6)4 = (3+5)8 + (3+6)4 = 100 \\ (x+6)11 - (y+5)7 = (3+6)11 - (3+5)7 = 43 \end{cases}$$ But yes, point $(3,3)$ is inside the fixed quadrilateral, too.

If you have an arbitrary quadrilateral, an arbitrary polygon (convex or concave), there are other methods one can do to determine whether a point is inside it or not. Many of these cases have been asked and answered before, and each of them have different efficient numerical solutions, so combining them all into a single answer is not sensible.

Here is some pseudocode to help with implementation.

Let's assume we have variables

x0,y0     # b0, the origin corner of the bounding parallelogram
xw,yw     # bw, another corner of the bounding parallelogram
xh,yh     # bh, the third corner of the bounding parallelogram

Each time the above change, I would precalculate five variables:

xu = xw - x0
yu = yw - y0
xv = xh - x0
yv = yh - y0
L = xu * yv - xv * yu
if L < 0:
    L = -L
    xu = -xu
    yv = -yv
else:
    xv = -xv
    yu = -yu
end if

The above negates the constants when necessary, so that only one case, one set of tests, is left: 0 <= (x-x0)*yv + (y-y0)*xv <= L and 0 <= (x-x0)*yu + (y-y0)*xu <= L. This means the test for each point (x,y) is

u = (x - x0)*yv + (y - y0)*xv
if (u < 0 || u > L):
    return OUTSIDE
else:
    v = (x - x0)*yu + (y - y0)*xu
    if (v < 0 || v > L):
        return OUTSIDE
    else:
        return INSIDE
    end if
end if

which boils down to four multiplications, four additions and two subtractions, and four comparisons, maximum, to determine point inclusion in the parallelogram.

Related Question