authors 
Kalay, Yehuda E. 
year 
1982 
title 
Determining the Spatial Containment of a Point in General Polyhedra 
source 
Computer graphics and Image Processing. 1982. vol. 19: pp. 303334 : ill. includes bibliography. See also criticism and improvements in Orlowski, Marian 
summary 
Determining the inclusion of a point in volumeenclosing polyhedra (shapes) in 3D space is, in principle, the extension of the wellknown problem of determining the inclusion of a point in a polygon in 2D space. However, the extra degree of freedom makes 3D pointpolyhedron containment analysis much more difficult to solve than the 2D point polygon problem, mainly because of the nonsequential ordering of the shape elements, which requires global shape data to be applied for resolving special cases. Two general O(n) algorithms for solving the problem by reducing the 3D case into the solvable 2D case are presented. The first algorithm, denoted 'the projection method,' is applicable to any planar faced polyhedron, reducing the dimensionality by employing parallel projection to generate planar images of the shape faces, together with an image of the point being tested for inclusion. The containment relationship of these images is used to increment a global paritycounter when appropriate, representing an abstraction for counting the intersections between the surface of the shape and a halfline extending from the point to infinity. An 'inside' relationship is established when the paritycount is odd. Special cases (coincidence of the halfline with edges or vertices of the shape) are resolved by eliminating the coincidental elements and reprojecting the merged faces. The second algorithm, denoted 'the intersection method,' is applicable to any well formed shape, including curvedsurfaced ones. It reduces the dimensionality by intersecting the polygonal trace of the shape surface at the plane of intersection, which is tested for containing the trace of the point in the plane, directly establishing the overall 3D containment relationship. A particular O(n) implementation of the 2D pointinpolygon inclusion algorithm, which is used for solving the problem once reduced in dimensionality, is also presented. The presentation is complemented by discussions of the problems associated with pointpolyhedron relationship determination in general, and comparative analysis of the two particular algorithms presented 
keywords 
geometric modeling, point inclusion, polygons, polyhedra, computational geometry, algorithms, search, Brep 
series 
CADline 
email 
kalay@socrates.berkeley.edu 
references 
Contenttype: text/plain

last changed 
2003/06/02 08:24 
