Intersection of a polyhedron with a line

In general, a convex polyhedron is defined as the intersection of a finite number of halfspaces. That is, a convex polyhedron is the set of solutions of a system of inequations of the form

:$Ax\; le\; b.$

There are many problems in which it is useful to find the intersection of a ray and a convex polyhedron; for example, in computer graphics, optimization, and even in some Monte Carlo methods. The formal statement of our problem is to find the intersection of the set $\{xinmathbb\{R\}^n|Ax\; le\; b\}$ with the line defined by $c+tv$, where $tinmathbb\{R\}$ and $c,\; vinmathbb\{R\}^n$.

To this end, we would like to find $t$ such that $A(c+tv)le\; b$, which is equivalent to finding a $t$ such that :$[Av]\; \_it\; leq\; [b-Ac]\; \_i$for $i=1,ldots,n$.

Thus, we can bound $t$ as follows::$t\; leq\; frac\{\; [b-Ac]\; \_i\}\{\; [Av]\; \_i\}\; ;;;\{\; m\; if\};\; [Av]\; \_i\; >\; 0$::$t\; \{\; m;\; unbounded\}\; ;;;\{\; m\; if\};\; [Av]\; \_i\; =\; 0,\; [b-Ac]\; \_i\; >\; 0$:

The last two lines follow from the cases when the direction vector $v$ is parallel to the halfplane defined by the $i^\{th\}$ row of $A$: $a\_i^Tx\; leq\; b\_i$. In the second to last case, the point $c$ is on the inside of the halfspace; in the last case, the point $c$ is on the outside of the halfspace, and so $t$ will always be infeasible.

As such, we can find $t$ as all points in the region (so long as we do not have the fourth case from above):$left\; [\; max\_\{i:\; [Av]\; \_ileq\; 0\}frac\{\; [b-Ac]\; \_i\}\{\; [Av]\; \_i\},\; min\_\{i:\; [Av]\; \_igeq\; 0\}frac\{\; [b-Ac]\; \_i\}\{\; [Av]\; \_i\}\; ight]\; ,$which will be empty if there is no intersection.

See also

* Polytope
* Polyhedron
* Hyperplane