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

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

4.2 测试效率
8
按照文献 [8] 中的方式, 我们检测了行元法与网元法测试 1×10 个测试点的效率. 相关时间开销的统计数据见
图 6. 从这些统计数据可知, 行元法相比网元法在 CPU 和 GPU 上均有相当的检测效率, 且大多数情况下略快. 相
关分析见下.

22 000 80 000
网元法-CPU 11 000 网元法-CPU 网元法-CPU 网元法-CPU
20 000 行元法-CPU 10 000 行元法-CPU 75 000 行元法-CPU 45 000 行元法-CPU
测试时间耗费 (μs) 14 000 测试时间耗费 (μs) 7 000 测试时间耗费 (μs) 60 000 测试时间耗费 (μs) 35 000
70 000
18 000
8 000
CPU 16 000 9 000 65 000 40 000
55 000
6 000
12 000
10 000 5 000 50 000 30 000
45 000
4 000
8 000
37×40 30×32 22×24 15×16 7×8 3×4 133×76 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
网元法-GPU 50 网元法-GPU 260 网元法-GPU 260 网元法-GPU
60
行元法-GPU
行元法-GPU
行元法-GPU
行元法-GPU
240
GPU 测试时间耗费 (μs) 55 测试时间耗费 (μs) 40 测试时间耗费 (μs) 240 测试时间耗费 (μs) 220
220
50
200
30
200
45
20
160
180 180
37×40 30×32 22×24 15×16 7×8 3×4 133×76 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) pol248 (c) pol2171 (d) pol7288
图 6 行元法与网元法在 CPU 和 GPU 上的测试效率比对

行元法与网元法在判断一个测试点位于多边形内/外属性的计算步骤是一致的, 相关计算开销相当. 但是, 行
元法对于条带结构的组织管理更紧凑, 使得编译器能够优化出效率更高的寻址操作来找到对应条带. 在我们的实
验中, 寻找测试点所在的网元地址, 行元法仅需 1 条指令, 而网元法需要 2 条指令. 因此, 行元法相比网元法可提升
一定的检测速度.

4.3 动态多边形的处理
按照文献 [8] 的例子, 我们测试行元法处理动态多边形的效率. 实验模拟海水上涨逐渐淹没一个小岛的过程,
该岛位置为北纬 39°15.17', 东经 122°59.46'. 该过程按时间序列分成 575 帧处理, 每一帧用一组多边形来描述小岛
未被淹没部分. 实验中, 网元法和行元法均需对每一帧的多边形进行条带结构的创建, 然后检测随机挑选的 1×10 4
个位置是否被淹没. 图 7 中给出了一帧的对比情况.

FPS: 62.5 kHz FPS: 1.7 kHz

(a) Ours (b) R-GP (128×)
图 7 行元法和网元法处理动态多边形的帧速对比示例

行元法将不同帧的多边形情况顺序送入 GPU 进行预处理和测试, 而网元法需对每一帧的多边形情况在 CPU
上完成条带结构的创建再送入 GPU 进行检测. 实验表明, 网元法的平均帧率为 1.36 kHz, 而行元法的平均帧率为
47.61 kHz, 帧速提高约 35.0 倍.
为测试本文提出的行元法处理各种多边形的情况, 我们设计了一个多边形动态变化的例子以进行相关测试. 此
例中, 多边形会剧烈地动态变化, 甚至出现边相交、边重叠等非流形情况. 网元法与本文提出的行元法均可处理这些