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

李佳玮 等: 基于网格行创建条带结构的点在多边形内判断方法 4245

0.07 0.6 2.5 4.0
0.06 行元法 0.5 行元法 2.0 行元法 3.5 行元法
排序时间 (s) 0.04 排序时间 (s) 0.5 排序时间 (s) 1.5 排序时间 (s) 2.5
网元法
网元法
网元法
网元法
0.05
3.0
0.3
2.0
0.03
1.0
1.5
0.2
0.02
1.0
0.01
0 0.1 0 0.5 0 0.5 0
37×40 30×32 22×24 15×16 7×8 3×4 133×40 111×64 89×51 44×25 22×12 11×6 175×112 146×93 117×75 87×56 58×37 29×18 316×208 263×173 211×139 158×104 105×69 52×34
(a) pol62 (b) pol1248 (c) pol2171 (d) pol7288
图 3 行元法与网元法创建条带结构时用于排序的时间比较

3) 对于一个具有 N 条边的多边形, 假设网格划分分辨率为 r h ×r v , 则行元法进行条带结构创建所预期的空间复
杂度为 O(r v N), 以便在一个网格行中处理所有的边. 对此, 网元法的预期空间复杂度为 O(r h r v N), 以便在一个网元
中能处理所有的边. 因此, 处理规模较大的多边形时, 网元法难以在 GPU 上进行条带结构的创建, 只能在 CPU 上
创建后再迁移到 GPU 中以进行检测处理. 显然, 这不便处理动态多边形. 由于行元法很好地降低了空间需求, 因而
可在 GPU 上创建条带结构, 也节省了从 CPU 往 GPU 迁移条带结构的时间, 能大幅提高动态多边形的处理效率.

4 实验分析
本文提出的行元法, 相比于网元法, 可减少需生成的条带数量, 并降低预处理时的空间预期, 由此可在 GPU 上
进行条带结构的创建. 进行点在多边形内的检测时, 行元法与网元法一样, 先依据测试点的坐标, 定位其所在的网
元, 并进一步在该网元中定位其所在的条带, 然后在该条带结构内局部地执行射线法, 利用该条带中所包含的多边
形的边及条带上端位于多边形内/外属性, 即可得知测试点在多边形内/外的属性. 行元法与网元方在检测质量上是
一样的, 因此, 我们在实验中主要比较两者的预处理和检测测试点的效率. 鉴于基于预处理的方法有非层次化组织
方法 (如网格法) 和层次化组织方法, 我们也与层次化组织的四叉树、KD 树方法 [16] 进行了对比实验.
我们的实验安排按照文献 [8] 进行相关处理. 所用的 4 个多边形见图 4. 对各个多边形测试时, 所用的网格分
8
辨率, 及所用的随机而均匀采样的 1×10 个测试点, 均依文献 [5] 的处理. 实验所用的设备是一台服务器, 具有一
个 Intel Xeon Gold 6154 CPU, 以及一个 NVIDIA Tesla V100 GPU.

(a) pol62 (b) pol1249 (b) pol2171 (d) pol7288
图 4 实验中使用的多边形, 名称中的数据代表多边形边数

4.1 预处理

图 5 中给出了行元法与网元法创建条带结构的时间耗费及加速比 (方法时间耗费的比值), 其中网元法需要将
[8]
条带迁移到 GPU 中. 行元法在 CPU 或 GPU 上创建条带结构的时间开销, 相比网元法 (网元法标记为 R-GP ) 有
大幅的降低, 且网格分辨率越高、多边形的边数越多, 则加速效果更好, 甚至可加速 40 余倍. 网元法将 CPU 上创
建的条带结构迁移到 GPU 上的时间开销很大, 甚至超过了网元法在 CPU 上创建条带结构的时间. 因此, 行元发直
接在 GPU 上进行条带结构的创建, 更有利于动态情况的检测效率提升.
行元法在 CPU 上创建条带结构的时间, 相比其在 GPU 上的处理, 一般需要较多的时间. 但是, 当多边形的边
较少且网格分辨率较低时, 行元法在 CPU 上创建条带结构的时间可能少于其在 GPU 上的相关处理, 如较低网格
分辨率下处理 pol62 多边形的情况. 相关原因如下: 1) GPU 上对条件判断的分支处理比较麻烦, 相关时间开销较
大; 2) 较低网格分辨率时, 网元中含有较多的边, 需要较多的比较运算以进行分支处理; 3) 多边形的边较少时, 求
交计算的需求不大, 难以发挥 GPU 的并行性能.