论文标题
使用空间细分的O（1）复杂性的coint-inconvex多边形和coint-inconvex多面体算法
Point-in-Convex Polygon and Point-in-Convex Polyhedron Algorithms with O(1) Complexity using Space Subdivision
论文作者
论文摘要
许多算法中使用了许多空间细分和空间分配技术来加快计算的速度。他们主要依靠正交空间细分，分别。使用分层数据结构，例如BSP树，四分之一，动孔，KD-Trees，边界量层次结构等。但是，在某些应用中，非正交空间细分可以为实际速度提供新的方式。在E3中的凸多边形的情况下，简单的点核测试是O（n）的复杂性，最佳算法是O（lg n）计算复杂性的。在E3情况下，即使对于未定义订单，即使对于凸多面体，复杂性也是O（n）。基于在预处理阶段的空间细分中，介绍了新的点符号多边形和符号多面体算法，从而导致O（1）运行时复杂性。提出的方法易于实现。由于二元性，双重问题的原则，例如线凸多边形，线剪辑，可以在类似的情况下求解。
There are many space subdivision and space partitioning techniques used in many algorithms to speed up computations. They mostly rely on orthogonal space subdivision, resp. using hierarchical data structures, e.g. BSP trees, quadtrees, octrees, kd-trees, bounding volume hierarchies, etc. However in some applications a non-orthogonal space subdivision can offer new ways for actual speed up. In the case of convex polygon in E3 a simple Point-in-Polygon test is of the O(N) complexity and the optimal algorithm is of O(lg N) computational complexity. In the E3 case, the complexity is O(N) even for the convex polyhedron as no ordering is defined. New Point-in-Convex Polygon and Point-in-Convex Polyhedron algorithms are presented based on space subdivision in the preprocessing stage resulting to O(1) run-time complexity. The presented approach is simple to implement. Due to the principle of duality, dual problems, e.g. line-convex polygon, line clipping, can be solved in a similarly.
