Abstract-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. Incorporating an octree structure for organizing polyhedrons, our approach can run at a speed comparable with 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(log n), depending on the polyhedron shape and the constructed representation, and less than O(log;3 n) in most cases. The time complexity of preprocess is between O(n) and O(n;2), varying with polyhedrons, where n is the edge number of a polyhedron.
Layer-based representation of polyhedrons for point containment tests. Publishing Authors By Initials
