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

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

Key words: point-in-polygon test; grid method; stripe

判断一个点是否位于一个多边形内, 是计算几何和计算机图形学中的一个基本问题, 有广泛的应用需求, 如地
理信息系统中的位置确定 [1] 、遥感数据的地域分类 [2] 、计算机辅助设计 [3] 等. 针对该问题, 已提出很多方法, 其中
网格法 [4,5] 便于实现, 有很高的计算效率, 是当前主流的方法之一. 该方法对多边形的包围盒进行均匀网格划分, 并
在各个网格单元 (简称网元) 中记录所包含的多边形的边; 这样, 检测一个点是否位于多边形内时, 可基于均匀网
格的规整性快速定位其所在的网元, 然后只处理该网元所含的多边形的边, 即可判断该点是否位于多边形内. 迄
今, 已提出了多种网格法, 如预计算网元中心点位于多边形内/外属性的方法 [6] 、网格分辨率优化的方法 [7] 等. 近期
提出的一种网格法 [8] , 对网元中所含的多边形边片段进行条带结构的组织管理, 简称网元法, 大幅提升了网格法的
检测效率, 优于已有的各种方法. 该方法建立的条带结构, 确保条带中的多边形边片段均与该条带的左右两边相
交 (不失一般性, 假设条带按平行 y 轴的方向建立, 见图 1), 并预先计算各个条带的上端位于多边形内/外的属性.
这样, 测试点可通过定位其所在的条带结构, 只处理该条带中的多边形的边, 即可判断其是否位于多边形内. 这样,
加强了局部化处理, 降低了计算复杂性, 同时有利于使用 GPU 进行并行计算, 能很好地提高点在多边形内检测的
效率. 如图 1 所示, 网元以浅色网格线划分而得, x i (i=1,…,4) 表示位于一条网格横线上的带箭头虚线与多边形的
边的交点, s j (j=1,…,13) 表示一个网格行中生成的 13 个条带结构 (以它们之间平行 y 轴的断线和双实线分隔). 在
此, 有冗余的条带 (它们所含的多边形边的情况一样), 如 s 4 与 s 5 同性, s 8 与 s 9 同性, s 1 与 0 s 1 同性. 该方法将在第
1
2 节具体介绍.
网元法很好地提高了测试效率, 但其基于网元创建条带结构, 有一些不足: 1) 一个网格行中相邻的 2 个网元,
其网格分割线左右两侧的 2 个条带很可能包含相同的一组边, 且它们上端位于多边形内/外的属性也一样, 因而会
产生冗余的条带结构; 2) 创建时, 各个网元独自处理, 会有一些冗余计算; 3) 该方法在创建条带结构时, 每个网元
预期的空间需求要能处理多边形的所有边, 空间需求大, 妨碍了其在 GPU 上的实现. 为此, 本文提出基于网格行来
创建条带结构, 而网元则仅作为定位测试点所在条带的一种加速辅助结构. 这样, 一个网格行中的相邻条带不会一
样, 可大幅减少条带数量, 也因而减少大量冗余计算, 见图 2. 特别是, 这样处理, 只需估计每个网格行的预期空间,
使其能处理多边形的所有边即可, 从而大幅降低了空间需求, 因此可在 GPU 上方便实现条带结构的创建. 在第
3 节, 我们将对此进行具体讨论. 新方法基于网格行创建条带结构, 我们称之为行元法.

E E
A
s 5 s 6 s 7 s 8 A
x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4
s 1 s 8 s 9 s 1 s 4 s 7
s 3 s 4 s 5 s 6 s 7 s 10 s 11 s 13 s 3 s 5 s 6 s 8 s 10
D D
s 2 C s 12 C s 9
s 2
d 2
B d 1 B d 3 d 4
d 1 d 2 d 3 d 4
y G y G
F F
begin: s 4 end: s 7
o x o x Index cell
图 1 网元法创建的条带结构 图 2 行元法创建条带的条带结构
实验表明, 相比网元法, 行元法能大幅提升条带结构的创建速度, 甚至高达 40 余倍. 特别是, 行元法能在 GPU
上创建条带结构, 有力提高了处理动态多边形的效率, 在我们实验中可提高帧速达 35.0 倍.

1 相关工作

点在多边形内判断的方法已有很多, 一般可分为两大类: 逐边处理的方法, 及对多边形的边进行一定组织的方
法. 逐边处理的方法, 如射线法 [9] 、绕角法 [10,11] 等, 它们无需预处理, 但每次检测时要处理多边形的所有边, 如射线
法从测试点发出射线, 要检测其与各条边的相交情况, 统计相交次数, 如相交次数为偶数, 则测试点在多边形外; 反