Intersection of a polyhedron with a line
In computational geometry, the problem of computing the intersection of a polyhedron with a line has important applications in computer graphics, optimization, and even in some Monte Carlo methods. It can be viewed as a three-dimensional version of the line clipping problem.[1]
If the polyhedron is given as the intersection of a finite number of halfspaces, then one may partition the halfspaces into three subsets: the ones that include only one infinite end of the line, the ones that include the other end, and the ones that include both ends. The halfspaces that include both ends must be parallel to the given line, and do not contribute to the solution. Each of the other two subsets (if it is non-empty) contributes a single endpoint to the intersection, which may be found by intersecting the line with each of the halfplane boundary planes and choosing the intersection point that is closest to the end of the line contained by the halfspaces in the subset. This method, a variant of the Cyrus–Beck algorithm, takes time linear in the number of face planes of the input polyhedron. Alternatively, by testing the line against each of the polygonal facets of the given polyhedron, it is possible to stop the search early when a facet pierced by the line is found.[1]
If a single polyhedron is to be intersected with many lines, it is possible to preprocess the polyhedron into a hierarchical data structure in such a way that intersections with each query line can be determined in logarithmic time per query.[2]
References
- 1 2 Kolingerová, Ivana (1994), "3D-line clipping algorithms – a comparative study", The Visual Computer 11 (2): 96–104, doi:10.1007/BF01889980.
- ↑ Dobkin, David P.; Kirkpatrick, David G. (1983), "Fast detection of polyhedral intersection", Theoretical Computer Science 27 (3): 241–253, doi:10.1016/0304-3975(82)90120-7, MR 731064.