Layer-based representation of polyhedrons for point containment tests.

This paper presents the layer-based representation of polyhedrons and its use for point-in-polyhedron tests. In the representation, the facets and edges of a polyhedron are sequentially arranged, and so, the binary search algorithm is efficiently used to speed up inclusion tests. In comparison with conventional representation for polyhedrons, the layer-based representation we propose greatly reduces the storage requirement because it represents much information implicitly, though it still has a storage complexity O(n). It is simple to implement, and robust for inclusion tests because many singularities are erased in constructing the layer-based representation. By incorporating an octree structure for organizing polyhedrons, our approach can run at a speed comparable with Binary Space Partitioning (BSP)-based inclusion tests, and at the same time greatly reduce storage and preprocessing time in treating large polyhedrons. We have developed an efficient solution for point-in-polyhedron tests with the time complexity varying between O(n) and O(logn), depending on the polyhedron shape and the constructed representation, and less than O(log3n) in most cases. The time complexity of preprocess is between O(n) and O(n2), varying with polyhedrons, where n is the edge number of a polyhedron.