Layer-based representation of polyhedrons for point containment tests.

Area of Science:

• Computational Geometry
• Computer Graphics
• Geometric Algorithms

Background:

• Point-in-polyhedron tests are fundamental in various computational fields.
• Conventional polyhedron representations often suffer from high storage requirements and computational complexity.
• Existing methods like Binary Space Partitioning (BSP) offer speed but can be storage-intensive.

Purpose of the Study:

• To propose a novel layer-based representation for polyhedrons.
• To develop an efficient and robust algorithm for point-in-polyhedron tests using this representation.
• To reduce storage and preprocessing time for large polyhedrons compared to existing methods.

Main Methods:

• A layer-based representation is developed, sequentially arranging facets and edges.
• Binary search algorithms are integrated for accelerated inclusion tests.
• An octree structure is incorporated to organize polyhedrons, optimizing performance.
• Singularities are minimized during representation construction for robustness.

Main Results:

• The layer-based representation achieves a storage complexity of O(n) while implicitly encoding significant information.
• Inclusion test time complexity ranges from O(n) to O(logn), often below O(log3n).
• Preprocessing time complexity varies between O(n) and O(n^2).
• Performance is comparable to BSP-based methods, with reduced storage and preprocessing demands.

Conclusions:

• The proposed layer-based representation offers a significant improvement in storage efficiency for polyhedrons.
• The method provides a robust and computationally efficient solution for point-in-polyhedron tests.
• Integration with octree structures enhances scalability for large-scale geometric applications.