Intersection of a polyhedron with a line

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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.

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

General solution[edit]

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} \;\;\;{\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^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]_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.

External links[edit]