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

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

之则在多边形内. 这类方法的计算复杂度较高, 为 O(N), N 为多边形的边数. 为降低测试计算复杂度, 许多方法提
出特定数据结构管理多边形的边, 使得每次测试时无需处理多边形的所有边, 如将多边形分解成较简单形状的梯
形法 [12] 、凸剖分法 [13] 、分层法 [14,15] , 以及对多边形的包围盒进行均匀划分的网格法 [4,5] 、层次化迭代划分的四叉
树、KD 树 [16] 、三叉树 [17] 等. 这些方法能很好地降低检测的计算复杂度, 比如梯形法 [12] 的计算复杂度为 O(logN).
在这些方法中, 网格法是应用最广泛的方法之一, 因为其易于实现, 且计算效率较高. 为提高网格法的效率, 已有大
量相关研究 [4−7,18] , 比如中心点法 [6] 预计算每个网元中心点位于多边形内/外的属性, 在检测时, 只需计算点与网元
中心点之间的连线与其所在网元中的多边形边片段的相交次数. 这样处理可很好地减少需要求交测试的边数量,
因为该连线较短, 可简便剔除许多与连线不相交的边.
网格法的一个困境是网格分辨率的处理. 如果网格分辨率低, 则网元较大, 每个网元所包含的多边形的边就
多, 对测试点进行测试时要处理的边就多, 检测效率会降低. 反之, 如果网格分辨率高, 每个网元所包含的多边形的
边就少, 有利于测试效率的提高, 但此时网元数量较多, 使得网格结构的创建开销较大, 不便处理动态多边形或边
数很多的大规模多边形. 对此, 近期提出的网元法 [8] 对每个网元中的边进行条带结构的组织, 能较好地化解检测效
率对于网格分辨率的敏感性, 大幅提升点在多边形内的检测效率. 这是因为网格分辨率较少, 使得网元较大, 所含
多边形的边多, 则网元中的条带就较多; 反之, 网格分辨率较大, 则网元较小, 所含多边形的边少, 因而网元中的条
带较少. 但该方法在条带结构的创建时, 会产生过多的条带、有许多冗余计算, 且其空间需求较大, 妨碍了其在
GPU 上的实现, 见引言中相关讨论. 对此, 本文提出行元法, 以改进网元法的不足, 将更好地促进相关应用的发展.

2 网元法简介

网元法 [8] 是一个基于网格单元均匀划分的点在多边形内检测算法. 该方法将多边形的包围盒向外扩张少许,
使得包围盒的边均位于多边形外; 然后, 对扩张的包围盒进行均匀的网格划分, 并根据每一个网元内的多边形片段
创建条带结构, 见图 1.
不失一般性, 根据图 1 对网元法进行简要介绍. 在此, 由浅色实线划分而得的均匀网格单元, 即是网元; 网元中
由断线和双细实线分割而成的每个矩形框就是一个条带, 每个条带中的所有多边形边, 均与该条带的左右两边相
交. 每个条带记录以下信息: 该条带所包含的多边形的边, 该条带上端位于多边形内/外的属性.
基于这样的组织结构, 点在多边形内的检测, 按以下步骤进行.
1) 根据测试点的坐标, 以 O(1) 的时间获知其所在的网元.
2) 根据该测试点的 x 坐标, 对比该网元中各个条带的 x 坐标范围, 可知测试点所在的条带.
3) 从测试点发出的一条垂直于 x 轴的向上射线, 检测该射线与条带中的边相交情况, 统计相交的边的数量. 根
据射线法的原理, 如果有偶数条边相交, 则测试点位于多边形内/外的属性与该条带上端位于多边形内/外的属性相
同, 否则相反.
基于网元法进行点在多边形内的判断具有很高的执行效率, 其原因如下: 1) 只需处理一个条带中的多边形的
边, 且一个条带所含的多边形的边一般较少; 2) 测试点发出的射线与 x 轴垂直, 使得该射线与一条边的相交测试可
以较少的计算来完成, 其处理为: 根据该测试点的 x 坐标, 计算该边的相应点的 y 坐标, 并比较该 y 坐标是否大于
测试点的 y 坐标, 即可知晓射线是否与该边相交; 3) 一个条带中的边均与该条带的左右两边相交, 因此, 检测测试
点发出的射线与这些边的相交情况时, 便于在 GPU 上进行高效的并行化实现.
下面, 介绍网元法的条带结构的生成步骤如下.
1) 对多边形的每条边, 计算其与各个网格划分横线 (平行 x 轴的网格线) 的交点 x 坐标 (交点的 y 坐标即横线
的 y 坐标), 由此知晓各个网元中所包含的多边形边的片段情况.
2) 根据每个网元中所含的多边形边的片段, 创建该网元中的条带结构. 在此, 依据网元内的多边形顶点 (如图 1
中的 D 点), 以及多边形的边与该网元的上、下网格横线的交点 (如图 1 中的 d i 、x j (i, j = 1,…,4)), 由它们的 x 坐标
生成平行 y 轴的直线段 (如图 1 中的双实线), 即得到了该网元内的条带划分结构. 当然, 相邻网元之间的分隔线也