Design and Analysis of a New Point-in-Polyhedron Algorithm

Abstract
The need for an efficient algorithm that determines if an arbitrary point lies within a polyhedron boundary arises frequently in many applications concerned with spatial information (e.g. geoscience and mining applications) as well as in three-dimensional CAD/CAM and solid modelling. Such an algorithm has therefore been studied extensively (e.g. Kalay, 1982; Lane et al., 1984; Horn & Taylor, 1989; Linhart, 1990).

Determining whether a point in a three-dimensional space is inside or outside a volume enclosing shape is in principle an extension to testing a point in two-dimensional space for inclusion in a planar polygon (Kalay, 1982). Several techniques may be used to determine the position of a point relative to a three-dimensional object in a three-dimensional space. The simplest technique that is used to achieve this might be the use of the parity of the number of intersections of a ray radiated from that point with the boundary of the polyhedron. Some difficulties arise when the ray passes through a vertex or if the ray coincides with one of the edges of the polyhedron (singularity cases).

This paper describes a new technique to solve the point-in-polyhedron problem in an easy and less time consuming way and also treating the singularity cases. The algorithm uses simple mathematical forms such as point-vector from and point-plane form. The algorithm has three main stages:

1. Reducing the dimensionality of the problem to the solvable two-dimensional case (point-in-polygon) using parallel projection.
2. Applying the point-in-polygon test to determine whether the image of a projected test point lies inside the image of a projected face or not.
3. Comparing the test point against the plane of a face to determine whether it is infront or behind that particular face.

The algorithm which is used to solve the containment relationship in two-dimensional space has been presented by Saalfield (l987) and modified by Taylor (1989). This algorithm is based on Point-vector method for representing a line segment. The Point-vector method offers several advantages over the other methods in that with it, line segments intersection routines and related cartographic computations such as point-in-polygon routines and detection of near intersections can be simplified and more easily understood geometrically (Saalfield, 1987). By choosing the ray judiciously, any kind of singularity cases will be avoided. The full paper will contain the detail of the procedures of this algorithm.

Determining whether a test point is infront of or behind a face or on any of its components depends on the interaction between the point and each face of the polyhedron. The method used to determine this interaction is based on the Point-Plane algorithm described by (Bowyer, 1983). The term Infront is used to designate the position of the test point on the side that looks in the same direction as the normal vector of the plane face points, and term Behind will be used to describe the position of the test point on the other direction. The vertices of each face are ordered counter-clockwise to let the normal vector of all faces which generate face images after the projection pointing to the same direction.

By counting the number of infronts and the number of behinds, the position of the test point can be determined. If the number of infronts or the number of behinds is odd, then the test point lies inside the polyhedron, otherwise it lies outside. The singularity cases (on a vertex, on an edge) will be detected first in the second stage (point-in-polygon) and will be checked in the third stage to see if it is a true singularity case occurred or not.

The algorithm was written in C++ code and implemented in a PC and UNIX systems. Several 3-D objects designed within a CAD system are used to test the point-in-polyhedron algorithm. These objects differ from each other in the number of components that construct each object. The range of objects were chosen to check the effect of the object complexity on the algorithm performance (CPU time). Five points covering all cases (inside, outside, on a vertex, on an edge and on a face) are tested against each object. The timing analysis will be presented in the full paper.

A test was carried out to check the algorithm efficiency; the CPU time recorded is reasonably fast compared with the time recorded by the other algorithms (Kalay, 1982; Lane et al., 1984). The algorithm proved largely, but not totally, successful in detecting singularity cases.

References
Bowyer, A. and Woodwark, J. 1983 A Programmer's Geometry. London: Butterworths.

Horn, W. P. and Taylor, D. L. 1989. "A theorem to determine the spatial containment of a point in a planar polyhedron", Computer Vision, Graphics and Image Processing, 45, 106-116.

Kalay, Y. E. 1982. "Determining the spatial containment of a point in general polyhedra", Computer Vision, Graphics and Image Processing, 19, 303-34.

Lane, J., Magedson, B. and Rarick, M. 1984, "An efficient point in polyhedron algorithm", Computer Vision, Graphics and Image Processing, 6, 118- 15.

Linhart, J. 1990. "A Quick point in Polyhedron Test", Computer Graphics, 14(3/4), 445 - 447.

Saalfield, A. 1987. "It doesn't make me nearly so CROSS. Some advantages of the point vector representation of line segments in automated cartography", International Journal of Geographical Information Systems, 1(4), 79 - 386.

Taylor, G. E. 1989. "Addendum to Saalfield", International Journal of Geographical Information Systems, 3(2), 192 - 193.