CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

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. 303-334 : ill. includes bibliography. See also criticism and improvements in Orlowski, Marian
summary Determining the inclusion of a point in volume-enclosing polyhedra (shapes) in 3D space is, in principle, the extension of the well-known problem of determining the inclusion of a point in a polygon in 2D space. However, the extra degree of freedom makes 3D point-polyhedron 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 parity-counter 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 parity-count is odd. Special cases (coincidence of the halfline with edges or vertices of the shape) are resolved by eliminating the coincidental elements and re-projecting the merged faces. The second algorithm, denoted 'the intersection method,' is applicable to any well- formed shape, including curved-surfaced 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 point-in-polygon 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 point-polyhedron relationship determination in general, and comparative analysis of the two particular algorithms presented
keywords geometric modeling, point inclusion, polygons, polyhedra, computational geometry, algorithms, search, B-rep
series CADline
email kalay@socrates.berkeley.edu
references Content-type: text/plain
last changed 2003/06/02 08:24
HOMELOGIN (you are user _anon_825087 from group guest) Works Powered by SciX Open Publishing Services 1.002