How to check if a cuboid of known vertices and a plane of equation $ax + by + cz + d = 0$ intersects?

# Check if plane intersects cuboid

geometry

#### Related Solutions

Let's start with the 2D case. Consider an $A \times B$ rectangle with a line through $(0, A)$ and $(B, 0)$. The line contains all points $(x,y)$ satisfying $Ax+By = AB$. We will say that points $(x,y)$ such that $Ax + By < AB$ are *below* the line. Notice that there is a one-to-one correspondence between squares intersected by the line, and lattice points on the boundary of the rectangle below the line!

This approach generalizes to $n$ dimensions. For the $A \times B \times C$ cuboid, the answer is:

$(AB+BC+AC-1)/2$

This can be formulated as a linear programming problem. Break the problem up by coordinates.

\begin{align*} 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{1} \leq 1 \\ 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{2} \leq 1 \\ & \phantom{(r_0+s u+)}\vdots \\ 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{N} \leq 1 \\ \end{align*}

Let $\mathbf{x} = (s,t)^{\text{T}} \in \Bbb{R}^2$. You only want to know if there is a feasible point satisfying these inequalities; you aren't trying to maximize or minimize anything. So pick your favorite or a random objective function "to maximize". Then convert each inequality, for $i=1\dots N$, above into the pair of feasibility constraints \begin{align*} 0 &\leq (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{i} \\ -(\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{i} &\leq 0 \\ -\mathbf{r}_0^i - s \mathbf{u}^i - t \mathbf{v}^{i} &\leq 0 \\ - s \mathbf{u}^i - t \mathbf{v}^{i} &\leq \mathbf{r}_0^i \end{align*} and \begin{align*} (\mathbf{r}_0 + s \mathbf{u} + t \mathbf{v})^{i} &\leq 1 \\ \mathbf{r}_0^i + s \mathbf{u}^i + t \mathbf{v}^{i} &\leq 1 \\ s \mathbf{u}^i + t \mathbf{v}^{i} &\leq 1 -\mathbf{r}_0^i \text{.} \end{align*} So the coefficient matrix, $A$, has $2N$ rows in the pairs \begin{pmatrix} &\vdots \\ -\mathbf{u}^i & &-\mathbf{v}^i \\ \mathbf{u}^i & & \mathbf{v}^i \\ &\vdots \end{pmatrix} and the corresponding rows of $\mathbf{b}$ are \begin{pmatrix} \vdots \\ \mathbf{r}_0^i \\ 1 - \mathbf{r}_0^i \\ \vdots \end{pmatrix} This makes the constraints equation $A \mathbf{x} \leq \mathbf{b}$.

Linear programming makes the additional constraints $\mathbf{x} \geq 0$, which corresponds to finding an intersection in one quadrant of the given plane. Since we want to check all four quadrants (but are free to stop once we find any point at all), we run an LP solver up to four times. The first, as described above. The second, with $\mathbf{u}$ replaced with $-\mathbf{u}$; this is to implement the replacement $s \mapsto -s$ to search for solutions with $s \leq 0$ coordinate. Then with $\mathbf{v}$ replaced with $-\mathbf{v}$, to search for solutions with $t \leq 0$. Then a fourth time with both $\mathbf{u}$ and $\mathbf{v}$ replaced with their negatives to search the remaining quadrant.

If any run finds a feasible point, there is an intersection. As soon as a run finds a feasible point, you need no further runs. If all four runs find no feasible points, then there is no intersection.

It turns out that finding a feasible point is about as hard (equivalent computational complexity) as solving the LP instance. Some LP solvers will let you stop between various phases of their computation. If you use a solver that will let you stop as soon as it finds a feasible point (any point in the intersection of the cube and (quadrant of the) plane), you can save some run time.

(I spent a little while trying to leverage the $x \leq 0$ constraints to be half of the constraints for the cube, so we would not need up to four LP runs. This would have $\mathbf{x} \in \Bbb{R}^N$. The obstruction is that there does not appear to me to be a linear inequalities way to determine whether a particular choice of $\mathbf{x}$ is on the plane.)

## Best Answer

The simplest is probably to check whether all vertices are on the same side of the plane or not.

The two half-spaces formed by the plane are respectively such that $ax+by+cz+d > 0$ and $<0$. So calculating $ax+by+cz+d$ for each vertex gives you the answer.