Intersection of a polyhedron with a line

From formulasearchengine
Jump to navigation Jump to search

{{ 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

The formal statement of our problem is to find the intersection of the set with the line defined by , where and .

General solution

To this end, we would like to find such that , which is equivalent to finding a such that

for .

Thus, we can bound as follows:

The last two lines follow from the cases when the direction vector is parallel to the halfplane defined by the row of : . In the second to last case, the point is on the inside of the halfspace; in the last case, the point is on the outside of the halfspace, and so will always be infeasible.

As such, we can find as all points in the region (so long as we do not have the fourth case from above)

which will be empty if there is no intersection.

External links