Intersection of a polyhedron with a line
|This article does not cite any references or sources. (February 2007)|
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
The formal statement of our problem is to find the intersection of the set with the line defined by , where and .
To this end, we would like to find such that , which is equivalent to finding a such that
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.