# Intersection of a polyhedron with a line

{{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} In computational geometry, the intersection of a polyhedron with a line is the problem of computing the intersection of a convex polyhedron and a ray in Euclidean space. This problem has important applications in computer graphics, optimization, and even in some Monte Carlo methods.

## Statement of the problem

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

${\displaystyle Ax\leq b.}$

The formal statement of our problem is to find the intersection of the set ${\displaystyle \{x\in {\mathbb {R} }^{n}|Ax\leq b\}}$ with the line defined by ${\displaystyle c+tv}$, where ${\displaystyle t\in \mathbb {R} }$ and ${\displaystyle c,v\in {\mathbb {R} }^{n}}$.

## General solution

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

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

Thus, we can bound ${\displaystyle t}$ as follows:

${\displaystyle t\leq {\frac {[b-Ac]_{i}}{[Av]_{i}}}\;\;\;{\rm {if}}\;[Av]_{i}>0}$
${\displaystyle t\geq {\frac {[b-Ac]_{i}}{[Av]_{i}}}\;\;\;{\rm {if}}\;[Av]_{i}<0}$
${\displaystyle t{\rm {\;unbounded}}\;\;\;{\rm {if}}\;[Av]_{i}=0,[b-Ac]_{i}>0}$
${\displaystyle t{\rm {\;infeasible}}\;\;\;{\rm {if}}\;[Av]_{i}=0,[b-Ac]_{i}<0}$

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

As such, we can find ${\displaystyle t}$ as all points in the region (so long as we do not have the fourth case from above)

${\displaystyle \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.