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

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

是相关条带的分隔线 (如图 1 中的断线). 然后各个条带记录其所包含的多边形边.
3) 判断各个条带上端位于多边形内/外属性的方法如下: 根据网格划分横线与多边形的交点情况, 该横线可划
分为多个横线片段, 然后依据射线法 [9] 即可知晓各个片段位于多边形内/外属性. 如图 1 中位于网格横线上的带箭
头虚线所示, 其与多边形的边相交于 4 个点, 记为 x i (i=1,…,4); 由此网格横线被划分成 5 个横线片段. 该虚线最左
端起始点位于包围盒外, 必定在多边形外; 然后, 其由左向右行进, 每遇到一个交点, 其位于多边形内/外的属性就
交替地改变 1 次. 因此, 该射线的 x 1 x 2 横线片段、x 3 x 4 横线片段是位于多边形内, 其他横线片段位于多边形外. 每
个条带的矩形框的上端只能位于其所在网格横线上的一个横线片段内 [5] , 因此其位于多边形内/外的属性即可知.
如图 1 中所示, 网元法会产生冗余的条带, 如条带 s 8 和 s 9 所包含的多边形边相同, 且它们上端位于多边形内/
外的属性也一样. 但它们分属于不同的网元, 因而被重复创建了.

3 行元法

本文提出的行元法, 基于网格行进行条带结构的创建, 可减少创建的条带数量及计算开销, 大幅减少空间需
求, 便于在 GPU 上创建条带结构, 克服网元法难以在 GPU 上进行条带结构创建的不足, 很好地提高计算效率.
下面, 我们先介绍行元法创建条带结构的处理步骤, 然后讨论其相比于网元法的改进.

3.1 基于网格行的条带结构创建
不失一般性, 我们依据图 2 介绍行元法创建条带结构的步骤如下.
1) 对多边形的每条边, 计算其与各个网格划分横线 (平行 x 轴的网格线) 的交点 x 坐标 (其 y 坐标即横线的 y
坐标).
2) 对于每一网格行, 其上、下两条网格横线上与多边形的交点以及位于该网格行中的多边形的顶点, 就决定
了该网格行中的条带结构. 具体地, 根据这些交点及顶点的 x 坐标, 形成平行 y 轴的直线段, 就得到了该网格行的
条带分隔线, 见图 2 中的双实线; 然后, 根据该网格行中各个多边形片段的起止端点, 即可知各个条带所包含的边
的情况. 如图 2 中所示, 行元法所得的条带结构, 不会出现相邻条带同性的情况 (所包含的边情况、其上端位于多
边形内/外属性均一样). 相比图 1 中网元法创建的条带结构, 图 2 中创建的条带结构就减少了 3 个. 一个网格行中
创建的条带结构, 按照条带分隔线的 x 坐标依序排列, 用一个数组管理, 如图 2 中的条带数组依序管理 s 1 –s 10 .
3) 对于各个条带结构的上端位于多边形内/外的属性, 按照第 3 节中介绍的相关处理即可.
4) 一个网格行中可能包含较多的条带. 为高效找到包含测试点的条带, 我们在各个网格行进行均匀的网元划
分, 每个网元只需记录其所包含的条带在条带数组中的首、末下标即可. 如图 2 所示, 包含顶点 D 网元, 只需记录
其起始于条带 s 4 并结束于条带 s 7 . 这样, 检测时, 以 O(1) 的时间可定位测试点所在的网元, 然后只需检测该网元中
的少量条带即可知测试点所在的条带结构, 这与网元法在每个网元中要检测的条带结构的数量是一样的.

3.2 行元法的性能改进
行元法相比于网元法, 有以下一些改进.
1) 减少了条带数量. 基于网元法, 相邻 2 个网元的网格划分线的左右 2 个条带, 往往所包含的多边形边的情况
是一样的. 而对于行元法, 这样的 2 个条带只需生成一个. 当网格分辨率为 r h ×r v 时, 假设左右相邻的 2 个网元均
有 1 个冗余的条带构建, 则行元法最多可减少的条带数量为 (r h –1)×r v . 这样就减少了空间需求, 相应地也减少了创
建的计算开销, 比如, 创建条带结构时, 行元法可大幅减少调用多边形边的内存访问次数.
2) 行元法对一个网格划分横线上的交点进行统一的快速排序, 以进行各个横线片段位于多边形内/外属性的
判断, 具有更高的排序效率. 对此, 网元法的排序处理等价于按网元划分桶后再在每个桶内部进行排序. 根据相关
文献 [19] , 桶排序算法往往只在各桶内要排序的单元数量相近时才会取得比快速排序更高的效率. 显然, 各个网元
中的交点数量一般难以一致, 使得网元法对于一条网格划分横线上的交点进行排序的效率, 不及行元法. 如图 3 所
示, 对于测试的 4 个多边形 (在实验部分具体介绍), 行元法在创建条带结构时用于排序的时间开销, 明显少于网元
法的相关开销.