Page 337 - 《软件学报》2025年第9期

4248 软件学报 2025 年第 36 卷第 9 期

多边形, 因为它们都是在各个条带结构内局部地实施射线法, 而射线法只需考虑从测试点发出的射线与多边形边的
相交次数, 因而可有效处理各种形态的多边形, 甚至是非流形情况. 图 8 中给出了该动态例子中几个时刻的多边形情
况, 位于内部的测试点, 着色为蓝色; 反之, 位于外部的测试点着色为红色. 实验表明, 行元法均能得到正确的结果.

图 8 行元法处理动态多边形几个时刻的情况及多相关测试点检测的情况

4.4 与层次化检测方法的比较
我们在此检测了行元法与四叉树、KD 树方法 [16] 的对比情况. 四叉树、KD 树方法是在叶节点中存储少量的
多边形边, 然后在测试时, 先找到测试点所在的叶子节点, 再在该叶子节点中找到距离测试点最近的点, 以进行相
关检测. 参考文献 [8], 我们进行了相关实验设置, 见表 2. 从图 9 的实验情况可知, 行元法的预处理时间介于四叉
树与 KD 树之间, 这是因为四叉树自适应生成的层级较浅; 由于行元法要存储较复杂的条带结构, 空间需求较大;
但行元法的检测效率明显优于四叉树、KD 树方法.

表 2 对比算法的实验设置

方法 设置项目 pol62 pol1248 pol2171 pol7288
四叉树 5 7 7 8
树结构层级
KD树 7 10 11 12
行元法 网格分辨率 3×4 11×6 29×18 52×34
四叉树 四叉树 70 000 四叉树
预处理时间 (μs) 8 000 行元法 空间开销 (kB) 40 000 行元法 预测时间 (μs) 50 000 行元法
KD 树
KD 树
KD 树
60 000
6 000
30 000
40 000
4 000
20 000
30 000
20 000
2 000
0 10 000 0 10 000 0
pol62 pol1248 pol2171 pol7288 pol62 pol1248 pol2171 pol7288 pol62 pol1248 pol2171 pol7288
(a) 预处理时间 (b) 空间开销 (c) 测试时间
图 9 行元法与四叉树、KD 树的对比实验情况

5 总 结
网元法是近年提出的一种高效检测点是否位于多边形内的方法, 其对网元内的多边形的边片段进行条带结构
的组织, 很好地加强了局部化计算, 提高了检测效率. 但网元法基于网元创建条带结构, 会产生冗余条带, 计算开销
较大, 且相关空间需求大, 不便在 GPU 上进行条带结构的创建处理. 本文提出行元法, 基于网格行创建条带结构,
可消除大量冗余条带, 大幅减少计算开销和空间需求, 由此便于在 GPU 上创建条带结构, 能更好地提高点在多边
形内的检测效率, 特别是有利于处理动态多边形.
对于动态多边形的处理, 我们目前是对每个时刻的多边形进行各自条带结构的创建, 以普适地处理各种动态情
况, 如多边形形态的剧烈变化. 当多边形的形态变化不大时, 有些已创建的条带结构可重用以节省创建开销, 但检测
可重用的条带结构需要一些开销. 如何优化处理, 需要进一步研究. 另外, 与许多点在多边形内判断的方法一样, 本文
提出的行元法也可推广以处理点在多面体内的判断, 比如对多面体的包围盒进行均匀网格划分, 再对网格内的多面
体面片构建与条带结构类似的规整组织, 以局部实施射线法进行检测. 我们将在未来对这些作进一步的探讨.