In
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, the problem of computing the intersection of a polyhedron with a line has important applications in
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
,
optimization, and even in some
Monte Carlo methods
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determini ...
. It can be viewed as a three-dimensional version of the
line clipping problem.
[.]
If the polyhedron is given as the intersection of a finite number of
halfspace Half-space may refer to:
* Half-space (geometry), either of the two parts into which a plane divides Euclidean space
* Half-space (punctuation), a spacing character half the width of a regular space
* (Poincaré) Half-space model, a model of 3-di ...
s, 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.
If a single polyhedron is to be intersected with many lines, it is possible to preprocess the polyhedron into a hierarchical
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
in such a way that intersections with each query line can be determined in logarithmic time per query.
[.]
References
External links
Intersection of convex hull with a line with pseudo code
{{DEFAULTSORT:Intersection Of A Polyhedron With A Line
Euclidean geometry