Intersection of a polyhedron with a line

In general, a polyhedron is defined as the intersection of a finite number of halfspaces $Ax\preceq b$. There are many problems in which it is useful to find the intersection of a ray and a 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 $\{x\in \mathbb {R} ^{n}|Ax\preceq b\}$ with the line defined by $c+tv$, where $t\in \mathbb {R}$ and $c,v\in \mathbb {R} ^{n}$.

To this end, we would like to find $t$ such that $A(c+tv)\preceq b$, which is equivalent to finding a $t$ such that

$[Av]_{i}t\leq [b-Ac]_{i}$

for $i=1,\ldots ,n$.

Thus, we can bound $t$ as follows:

$t\leq {\frac {[b-Ac]_{i}}{[Av]_{i}}}\;\;\;{\rm {if}}\;[Av]_{i}>0$

$t\geq {\frac {[b-Ac]_{i}}{[Av]_{i}}}\;\;\;{\rm {if}}\;[Av]_{i}<0$

$t{\rm {\;unbounded}}\;\;\;{\rm {if}}\;[Av]_{i}=0,[b-Ac]_{i}>0$

$t{\rm {\;infeasible}}\;\;\;{\rm {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}^{T}x\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]_{i}\leq 0}{\frac {[b-Ac]_{i}}{[Av]_{i}}},\min _{i:[Av]_{i}\geq 0}{\frac {[b-Ac]_{i}}{[Av]_{i}}}\right],$

which will be empty if there is no intersection.

See Also

• Polytope
• Polyhedron
• Hyperplane