Intersection of a polyhedron with a line
From Wikipedia, the free encyclopedia
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 an system of inequations of the form
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 
with the line defined by c + tv, where 
and 
.
To this end, we would like to find t such that 
, which is equivalent to finding a t such that
![[Av]_it \leq [b-Ac]_i](../../../math/c/2/9/c2965c4f768ef3c79e2b389943867094.png)
for 
.
Thus, we can bound t as follows:
![t \leq \frac{[b-Ac]_i}{[Av]_i} \;\;\;{\rm if}\;[Av]_i > 0](../../../math/8/a/d/8add3cb29508c98aa0819c42eb18082f.png)
![t \geq \frac{[b-Ac]_i}{[Av]_i} \;\;\;{\rm if}\;[Av]_i < 0](../../../math/8/d/3/8d3910d172d70186555e407ce521577c.png)
![t {\rm\; unbounded} \;\;\;{\rm if}\;[Av]_i = 0, [b-Ac]_i > 0](../../../math/6/1/d/61d85db02557aec4d1590959fddfbb1d.png)
![t {\rm\; infeasible} \;\;\;{\rm if}\;[Av]_i = 0, [b-Ac]_i < 0](../../../math/d/3/a/d3a1bcb90c2f62172ca8458e17bddcb3.png)
The last two lines follow from the cases when the direction vector v is parallel to the halfplane defined by the ith row of A: 
. 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],](../../../math/0/9/1/091483ec9b3edadf83f3658a9de3f6ea.png)
which will be empty if there is no intersection.
