In
computational geometry, the problem of computing the intersection of a polyhedron with a line has important applications in
computer graphics
Computer graphics deals with generating images and art with the aid of computers. Computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. ...
,
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, and even in some
Monte Carlo methods
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on Resampling (statistics), repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve pr ...
. It can be viewed as a three-dimensional version of the
line clipping
In computer graphics, line clipping is the process of removing ( clipping) lines or portions of lines outside an area of interest (a viewport or view volume). Typically, any part of a line which is outside of the viewing area is removed.
There ...
problem.
[.]
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.
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 and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
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