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

$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 $\{x\in\mathbb{R}^n|Ax \le b\}$ with the line defined by $c + t v$ , 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)\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 t h$ 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.

Category: Euclidean geometry

Intersection of a polyhedron with a line

From Wikipedia, the free encyclopedia

[edit] See also

Views

Navigation

interaction

Search