面向空间关系复合的矢量多边形图形拓扑叠置分析算法

计算机辅助设计与图形学学报

Journal of Computer-Aided Design & Computer Graphics

Vol.30 No.9 Sep. 2018 面向空间关系复合的矢量多边形图形拓扑叠置分析算法

谢顺平1,2), 叶罕霖3) (南京大学江苏省地理信息技术重点实验室 南京 210023)

(南京大学地理与海洋科学学院地理信息科学系 南京 210023) 3)

(中国科学院遥感与数字地球研究所数字地球重点实验室 北京 100094) (xiesp@nju.edu.cn)

2)1)

摘 要: 矢量多边形图形拓扑叠置是挖掘和提取空间隐含信息的重要空间分析方法, 现有方法主要针对简单要素模型, 未考虑图形要素间空间关系的复合运算. 为使矢量多边形图形空间叠置能在有利于空间关系复合的操作模式下进行, 提出一种基于线-面运算的矢量多边形拓扑叠置分析算法. 对参与叠置的2幅矢量多边形图形, 分别将其中一幅图形的矢量链段与另一幅图形的面域图进行线-面叠置运算和空间关系复合处理, 检测出矢量图形中跨越面域图多边形的链段并进行分解; 通过面向叠置模式的链段筛选和结点匹配、空间关系构建等, 最终生成含空间拓扑关系的结果多边形图形. 实验结果表明, 该算法具有较高的鲁棒性和效率, 非常适用于面向空间关系复合的复杂矢量多边形图形空间拓扑叠置分析.

关键词: 矢量多边形; 拓扑叠置; 空间分析; 空间关系复合; 线-面叠置 中图法分类号: TP391.41 DOI: 10.3724/SP.J.1089.2018.16876

Topology Overlay Analysis Algorithm of Vector Polygon Maps for Spatial Relationship Composition

Xie Shunping1,2) and Ye Hanlin3)

1)2)3)

(Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology, Nanjing University, Nanjing 210023)

(Department of Geographic Information Science, School of Geographic and Oceanographic Sciences, Nanjing University, Nanjing 210023) (Key Laboratory of Digital Earth Science, Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100094)

Abstract: Topological overlay analysis of vector polygons is the key and fundamental spatial analysis method to extract spatial implicit information. The existing methods are mainly for the simple data structure, not taking into account the spatial relationship of map elements and the composite operation between them. In order to implement the topology overlay for vector polygon maps in the mode of spatial operation favor-ing spatial relationship composition, we presented a new topology overlay algorithm based on arc and poly-gon operation in this paper. The algorithm, for the two vector polygon maps to participate in topology over-lay, carries out respectively the overlay operators and spatial relationship composition for the every vector arcs of one and polygonal area map of another. In this process those arcs crossing polygon unit can be de-tected and decomposed, finally the result polygon map with spatial topological relationship has been gener-ated by overlay mode oriented arcs filtering, nodes matching, and spatial relationship reconstruction. The computational experiment shows that the proposed algorithm has higher robustness and efficiency, which is very suitable for spatial topological overlay analysis of complex polygon maps with spatial relationship.

收稿日期: 2017-09-05; 修回日期: 2018-02-08. 基金项目: 国家自然科学基金面上项目(41671390, 41571377). 谢顺平(1957—), 男, 博士, 教授级高级工程师, 硕士生导师, 主要研究方向为地理信息系统理论与方法、空间分析模型与算法、智能空间优化等; 叶罕霖(1991—), 男, 博士研究生, 主要研究方向为地理信息系统与空间分析、月基对地观测几何模型等.

第9期

谢顺平, 等: 面向空间关系复合的矢量多边形图形拓扑叠置分析算法 1679 Key words: vector polygon; topological overlay; spatial analysis; spatial relationship composition; overlay of arc and polygon

矢量多边形图形空间叠置分析是GIS重要的空间分析功能, 其基本运算是对2个单要素面状矢量图层进行叠置, 以产生一幅反映源图层面状要素属性叠加组合分布特征的新图层; 叠置分析的结果是获得多边形几何图斑较为细碎、单元属性更为多元的综合图层, 可挖掘源图层无法单独表征的有价值空间信息. 如果在空间叠置中考虑空间要素拓扑关系的复合, 则可提供更多的空间信息和空间分析支持, 便于多幅图形的拓扑叠置分析. 现有研究大多针对简单要素模型的矢量多边形图形叠置, 不考虑空间关系的复合和拓扑运算. 例如, 桌面ArcGIS软件以Shapefile格式进行多边形叠置分析, 参与叠置的图形和叠置结果图形均不含空间关系, 分析成果的信息量和应用均受到限制.

实现矢量多边形空间叠置的方法大致可分为直接方法和间接方法. 直接方法一般通过叠置图形间矢量多边形链段的求交、分解、重组等步骤实现, 这种基于“线-线”运算的过程较为繁复, 不利于空间关系复合和大数据量复杂图形间的分析. 一些学者对不涉及拓扑关系的简单要素模型多边形图形叠置方法开展研究, 如使用单形链之间的代数操作实现多边形间的布尔操作[1-2]; 通过设计高效的多边形裁剪算法实现多边形之间的交和并运算[3-4]; 基于扫描线矢量求交算法的多边形空间布尔运算[5-8]; 采用链段求交和交多边形搜索的叠置分析算法[9], 基于单调链求交和排序切片递归树的多边形叠置分析方法[10]; 利用改进四叉树的矢量地图叠加方法[11]等, 还有一些学者研究了通过过滤空间相离链段并利用栅格数据辅助加速链段相交求解的方法

[12-13]

.

间接方法先将参与叠置的多边形图形转换为栅格图形, 再进行栅格图形之间的叠置, 最后将叠置结果转换回矢量多边形图形. 例如, 基于游程编码的多边形栅格叠加方法[14], 基于栅格图层操作的模糊叠置分析模型[15]; 还有学者通过对多边形的梯形剖分和梯形面元间的叠置操作实现多边形集合间的布尔运算[16], 以提高算法分析精度等. 显然, 间接方法易于实现, 但需要高效的矢栅相互转换算法支持, 存在误差积累和产生数据冗余等问题.

矢量多边形图形空间拓扑叠置分析须在图形

几何对象空间叠置运算的同时, 考虑几何对象间空间关系的叠置与复合运算. 本文提出一种面向空间关系复合和基于“线-面”运算的矢量多边形图形拓扑叠置算法, 将这一复杂问题化繁为简地转化为有利于拓扑关系复合的线集与面集之间的叠置问题, 叠置结果图形中的几何要素及其空间关系同时生成, 实现了真正意义上的矢量多边形空间拓扑叠置. 实验结果表明, 本文算法达到了较好的实用性和较高的综合效率.

1 矢量多边形图形的面域图表达

1.1 面域图表达数据结构

本文以双重独立地图编码模型[17]组织和表达矢量多边形图形及其空间拓扑关系, 模型以无冗余数据存储方式记录相邻多边形的共同边界链段和外围边界链段, 并表达链段与起止结点和左右多边形面元之间的拓扑关系. 为简化矢量多边形图形拓扑叠置繁复的求解过程, 本文用两图间相互的“线-面”求交运算替换常规的“线-线”求交运算, 以便于叠置图件几何要素空间关系复合和结果图件拓扑关系构建. 为此, 需预先获得矢量多边形源图的面域图表达, 以适应高效的线-面叠置运算. 本文采用精度游程编码表达面域图, 具有实数水平精度和任意预置的纵向精度, 相应的数据结构如下:

struct PARLCODING {

float x; //交点x坐标 unsigned int rightpoly; //右侧多边形编码 };

该结构以一组具有相同纵向宽度(预置的纵向精度)的水平条带剖分源图形, 从左到右记录了每个水平条带中线(扫描线)与多边形图形链段交点的x坐标及其右侧邻近多边形编码, 构成面域图精度游程编码表, 并以条带索引表记录各条带中线的y坐标和其精度游程编码串在面域图精度游程编码表中的起止位置, 如图1所示.

1.2 矢量多边形图形的面域图生成

通过一次遍历矢量多边形图形的链段, 统计图形水平精度条带中线(扫描线)被链段穿越的次数. 考虑到图形链段节点可能会频繁落在精度扫描

1680

计算机辅助设计与图形学学报 第30卷

线上, 故对图2中的特殊情形做如下处理: 链段在扫描线上的纵向折返点不视为穿越点(对应图2中的情形1、情形2); 对链段与扫描线部分重叠并纵向折返情形(对应图2中的情形3、情形4), 重叠起止端点视为2个穿越点; 对链段上至扫描线向右水平重叠一段后上穿的情形, 或者链段下至扫描线向右水平重叠一段后下穿的情形(对应图2中的情形5、情形6), 均视第1个交点为穿越点; 对链段上至扫描线向左水平重叠一段后上穿的情形, 或者链段下至扫描线向左水平重叠一段后下穿的情形(对应图2中的情形7、情形8), 均视第2个交点为穿越点. 对扫描线上同一点处有多条链段穿越的情形, 只统计一次交点, 根据与x轴具有最小正夹角链段的走向和左右码确定该点右侧的多边形编码, 并约定多边形图形轮廓以外区域视为0区. 根据初次遍历统计的穿越点总数, 动态地创建精度游程编码顺序表, 依照各扫描线上的穿越点数及扫描线y坐标建立精度游程编码索引表; 再次遍历矢量图形的所有链段, 计算各链段穿越扫描线交点的x坐标, 连同穿越点右侧的多边形编码一起存储到所在行精度游程编码序列中; 最后以x坐标

图1 面域图精度游程编码数据结构

图2 矢量链段穿越扫描线的特殊情形

为关键码, 采用快速排序方法分别对各行的精度游程编码进行递增排序, 即获得矢量多边形图形的面域图数据表达.

1.3 基于面域图的点-面包含分析

点-面包含分析是线-面叠置运算的基础算法, 矢量多边形面域图的建立为面向复杂图形的点-面包含分析提供了便利. 为分析矢量链段中探测点所落入的多边形区域, 根据探测点的y坐标经线性映射直接定位到所在精度条带对应的精度游程编码有序表, 通过折半查找确定探测点x坐标所处的游程区段, 即获得探测点所落入的本底图形多边形区域. 假设矢量多边形图形的面元总数为n, 平均而言, 每个条带的精度游程数可估计为n, 故对其进行点-面包含分析的时间复杂度为O(lb n).

2 矢量图形与面域图的混合叠置

2.1 混合叠置

假设参与叠置分析的矢量多边形图形分别为图形A和B, 分析结果为矢量多边形图形C, 空间拓扑叠置的6种基本模式分别表示为A∪B, 即图形A与B并; A∩B, 即图形A与B交; (A∪B)∩A, 即图形A域内2个图的并; (A∪B)∩B, 即图形B域内2个图的并; AB, 即图形A与B的差; (A∪B)(A∩B), 即对称差叠置模式; 如图3所示.

a. 多边形A

b.多边形B

c. A∪B d. A∩B

e. (A∪B)∩A

f. (A∪B)∩B

g. AB h. (A∪B)(A∩B)

图3 矢量多边形图形拓扑叠置模式

图形混合叠置处理包括: (1) 图形转换. 分别生成矢量多边形图形A和B相应的面域图形AR和BR. (2) 混合叠置. 先以图形A为上覆图形, 以图BR为本底图形进行线-面混合叠置处理, 再以图形

B为上覆图形, 以图AR为本底图形进行线-面混合叠置处理. 混合叠置时, 对上覆矢量图形的各条链段进行内插探测点遍历、跨多边形检测、跨越点

第9期

谢顺平, 等: 面向空间关系复合的矢量多边形图形拓扑叠置分析算法 1681

计算、链段分解等处理. (3) 叠置模式处理. 按照预选的叠置模式对叠置运算产生的链段进行筛选, 拾取叠置结果图形的多边形及其链段、丢弃非结果多边形图形及链段. (4) 空间关系构建. 按设计的拓扑关系运算规则, 对结果图形链段进行左右多边形编码, 建立图形线-面(链段-多边形)之间的空间拓扑关系, 以及结果图形面元与图形A和B面元的空间隶属关系等.

2.2 线-面叠置运算与链段分解

线-面混合叠置中, 上覆矢量多边形图形链段出入某个本底多边形的临界点称为跨越点, 跨越点的检测与计算为上覆图形链段的分解提供依据. 逐条对上覆图形的链段进行等距离探测点内插, 采用点-面包含分析, 依次判断链段的2个相邻探测节点所落本底多边形是否一致. 若一致, 则继续探测; 否则, 在其连线上采用折半逼近法计算跨越点坐标, 并在该点处分解链段, 对多次跨越多边形的链段实施多次分解. 折半逼近法不断以落入不同多边形两点连线上的中点坐标替换与其落入相同多边形的一点坐标, 直至两点充分接近到距离小于预设精度为止, 最后的中点即为跨越点. 线-面混合叠置产生的所有链段连同其落入的本底多边形编码参与后续的叠置模式处理.

2.3 叠置模式处理

对于“并”叠置模式(union), 保留叠置产生的所有多边形, 叠置产生的所有链段均作为结果图形的构图链段. 对于“交”叠置模式(intersect), 仅保留两图重叠范围内的叠置多边形, 对图形A与图BR叠置产生的每一条链段, 若其落入图BR轮廓范围以内, 则选为结果图形的构图链段, 否则丢弃; 同样, 对图形B与图AR叠置产生的每一条链段, 若其落入图AR轮廓范围以内, 则选为结果图形的构图链段, 否则丢弃. 对于“差”叠置模式(difference), 仅保留“并”叠置产生在图形B轮廓范围以外的多边形, 对图形A与图BR叠置产生的每一条链段, 若其落入图BR轮廓范围以外, 则作为结果图形的构图链段, 否则丢弃; 对图形B轮廓链段与图AR叠置产生的每一条链段, 若其落入图AR轮廓范围以内, 则作为结果图形的构图链段, 否则丢弃. 对于“图形A域内的并”叠置模式(identity), 仅保留图形A轮廓范围内两图叠置产生的多边形, 图形A与图BR叠置产生的所有链段均选为结果图形的构图链段, 对图形B与图AR叠置获得的每一条链段,

若其落入图AR轮廓范围以内, 则作为结果图形的构图链段, 否则丢弃. 对于“图形B域内的并”叠置模式, 处理方法与上述方法类似.

此外, 对于“对称差”叠置模式(symmetrical difference)的处理, 仅保留两图公共范围以外的叠置多边形, 对混合叠置产生的每一条链段, 若其来自上覆图形轮廓链段或落在本底图形轮廓范围以外, 则选为结果图形的构图链段, 其余丢弃.

2.4 链段结点匹配

理论上, 叠置结果多边形图形中的相邻链段在连接处的结点坐标应完全相同, 但受制于相应本底多边形面域图的预设纵向精度, 分属于两源图的2条相交链段在混合叠置分解时的跨越点(交点)计算有可能存在一定的误差. 为此, 需要对结果图形所有构图链段进行结点匹配处理. 通过设置一个最初为空的构图链段结点表, 以面域图纵向精度作为匹配相同结点的距离容限, 依次将每条链段的首尾结点与结点表中的结点进行坐标匹配, 若匹配成功, 则以表中的结点坐标代替链段当前端结点的坐标; 否则, 链段的当前端结点作为新结点连同其坐标加入到结点表中, 直至完成所有构图链段结点的匹配处理.

3 叠置图形拓扑关系构建

3.1 叠置图形多边形编码

为便于分析, 假设参与叠置的图形A和B包含的多边形数分别为n和m, 图形A和B均采用连续自然数多边形编码. 考虑到图形轮廓以外为0区, 理论上, 图形A和B的“并”叠置最多可能产生(n+1)(m+1)个不同的多边形. 由于事先无法获知哪些多边形面元会在结果图形中出现, 因此, 须按公式

PC=PA(m+1)+PB(1)

为所有可能产生的结果多边形进行初始编码

. 其

中, PC为叠置结果图形C中某个生成多边形的初始编码; PA和PB分别为该生成多边形落入图形A和B中相关多边形的编码; m为图形B的多边形数目.

3.2 叠置图形链段关系编码

根据式(1), 可以计算获得叠置结果图形C所有构图链段的左右多边形编码. 假设来自图形A的一条叠置产生链段的原始左右多边形编码分别为LA和RA, 该链段在图形B中所处多边形的编码

1682

计算机辅助设计与图形学学报 第30卷

为PB, 则该链段在图形C中的左右多边形编码LC和RC可分别表示为

廓完全重合, 因此图形B的轮廓链段不参与线-面叠置; 图4c为图形A链段与图形B的面域图BR

LC=LA(m+1)+PB (2) 叠置的结果, 图4e反映图形A的跨区(本底多边形)RCRA(m1)PB (3) 链段在对应跨越点被分解; 图4d所示为图形B内

同样, 对于来自图形B的一条叠置产生链段, 若其原始的左右多边形编码分别为LB和RB, 该链段在图形A中所处多边形的编码为PA, 则其在图形C中的左右多边形编码可分别表示为

部链段与图形A的面域图AR叠置的结果, 图4f反映图形B的内部跨区链段在对应跨越点被分解; 图4g表示结果图形中多边形及其链段的初始编码, 图中链段pq是由图形A的链段pr分解获得, 其原

LCPA(m1)LB (4) 始左右码分别为1和2, 所落图形B多边形区域为RCPA(m1)RB (5) 1, 其中m=3. 根据式(2)(3), 链段pq的初始左右码

结果图形链段的初始编码是伴随着链段跨越点检测、分解、叠置模式处理相继完成的. 图4所示为混合叠置过程. 其中, 图4a和图4b为参与叠置的2个源矢量多边形图形A和B, 由于2个图轮

分别为14+1=5和24+1=9; 链段sk是由图形B的链段sw分解获得, 其原始左右码分别为2和3, 所落图形A多边形区域为1; 根据式(4)(5), 链段sk的初始左右码分别为14+2=6和14+3=7.

图4 上覆矢量多边形图形与本底多边形面域图形混合叠置示意图

3.3 叠置图形连续编码处理

多边形图形叠置实际产生的结果多边形数目一般远小于2个源图中多边形组合所产生的多边形最大数目, 很多初始编码多边形单元在结果图形中并未出现. 为便于后续空间叠置分析, 需要对结果图形中实际产生的多边形进行连续编码处理. 具体方法如下: 遍历结果图形C所有链段的初始左右码, 对所有出现的多边形初始编码进行排序后再按顺序连续编码, 相应更新结果图形所有链段的左右码, 并根据

例如, 初始编码多边形9被转换为连续编码多边形4, 其隶属源图形A中的多边形为9/4=2, 隶属源图形B中的多边形为9%4=1; 结果图形中的链段sk, 其初始的左右多边形编码为6和7, 多边形连续编码后相应地更新为2和3.

表1 叠置结果图形面元与源图面元的关系

图形C编码多边形 初始

连续

A

隶属多边形

B

5 1 1 1 6 2 1 2

PA (6) PC/(m1)7 3 1 3 PB 9 4 2 1 PC%(m1) (7)

11 5 2 3 14 6 3 2 15 7 3 3

建立结果图形多边形单元与参与叠置的2个源图多边形单元的关系表, 如表1所示; 根据表1更新结果图形中所有链段的左右码如表2所示.

第9期

谢顺平, 等: 面向空间关系复合的矢量多边形图形拓扑叠置分析算法 1683 表2 图形C叠置结果图形内部链段左右码更新

图C 链段 pq qr ry oq qs st sk kw rk kx

图C多边形初始编码左多边形

右多边形

图C多边形连续编码左多边形

右多边形

间约为O(snlbnsmlbm). 综合上述计算开销, 算法的时间复杂度为O(6n6msnlbn

smlbm). 可以看出, 面域图精度游程的纵向精

5 9 1 4 7 11 3 5 15 11 7 5 9 11 4 5 5 7 1 3 5 6 1 2 6 7 2 3 14 15 6 7 7 15 3 7 6 14 2 6

度是影响算法计算性能的因素之一, 当两图面元数相差悬殊即n>>m且sn时, 算法的时间复杂度简化为O(snlbn).

为验证算法的性能并以现有GIS专业软件ArcGIS10.0 Desktop作为参照, 本文在联想Think Pad T430(2.5 GHz 4GB)上对各种规模的矢量多边形图形进行空间叠置实验, 实验图形幅面为1.8 m 1.8 m、比例尺为1 10000, 精度游程编码采用的图面纵向精度为0.0001 m(实际的1 m). 图5所示为实验样图之一, 表3所示为实验获得的算法性能统计数据, 运行时间数据均以3次相同实验运算时间的平均值统计. 表3中, 2种算法的叠置时间均包括读取参与分析源矢量多边形图形文件的时间和存储叠置结果矢量多边形图形文件的时间, 区别在于本文算法是兼顾空间关系复合的拓扑叠置, 而ArcGIS仅是简单要素模型叠置. 本文算法的转换时间指将参与分析的源矢量多边形图形转换为精度游程编码格式面域图的时间, 对于一幅矢量多边形图形, 这种预处理转换可以为其参与的所有叠置分析所共享; 由于ArcGIS10.0 Desktop软件的叠置需通过Shapefile格式文件进行, 其转换时间指将包含拓扑关系的源多边形图形Coverage文件转换为Shapefile文件的时间和结果多边形图形Shapefile文件转换转为Coverage文件的时间. 为使转换、叠置、再转换的处理过程连续, 需通过定制编程实现对拓扑叠置分析的模拟, 且

4 算法分析与实验

假设参与叠置的矢量图形A和B的多边形数分别为n和m, 相应的面域图精度游程条带数平均为s, 按平均每个多边形具有6个邻域考虑, 两图的链段数大约分别为3n和3m. 为便于分析, 将多边形单元总体理想化为大致呈交错阵列状分布, 矢量多边形图形转换成面域图需遍历各图链段2次, 其处理时间为O(6n+6m); 平均每条扫描线被两图链段穿越的次数即游程数分别约为n和m, 对两面域图各自s个条带的精度游程编码快速排序时间为O(snlbnsmlbm), 而计算两图与扫描线交点的次数约为sn和sm. 假设混合叠置链段探测点的平均间距为2倍的精度游程条带宽度, 则两图的探测点数分别约为sn和sm, 对A图和B图的一次点-面包含分析时间为

O(lbn),和O(lbm), 故两图链段探测与分解时

a. 源多边形图形A b. 源多边形图形B c. 叠置结果多边形图形C

图5 多边形图形空间拓扑叠置分析实例

1684

计算机辅助设计与图形学学报 第30卷

表3 本文算法与ArcGIS10.0 Desktop软件的性能比较

多边形数/链段数

本文算法时间/s ArcGIS10.0叠置算法时间/s

图形A 图形B 结果多边形 转换 1 024/2 112 120/262 1 876/3 842 0.047 4 489/9 112 224/478 6 768/13 879 0.233 7 569/15 312 440/922 11 703/24 196 0.469 11 025/22 260 783/1 622 17 614/36 157 0.828 45 796/92 020

1 224/2 518

62 418/128 677

10.391

结果图形的格式转换无法通过预处理避免. 从表3实验数据可以看出, 在不同规模图形的拓扑叠置分析中, 为达到同样的分析目标, 本文算法的综合计算效率均优于ArcGIS软件; 但也注意到, 随着数据量的扩大, 这种优势有所减弱. 考虑到算法的可行性、易解性和鲁棒性, 本文算法在综合性能上取得了较好的结果.

5 结 语

本文将矢量多边形空间拓扑叠置简化为线集和面集之间的叠置问题, 为参与叠置图形链段的分解、空间关系复合以及结果图形空间关系的构建创造了便利, 可有效地降低大数据量复杂图形间空间拓扑叠置分析的难度, 为这类空间分析问题提供了新的求解思路. 由于矢量多边形图形转换到面域图可作为预处理, 因此, 一次转换可多次共享使用, 对大数据量复杂图形的适应性和鲁棒性强; 设计的面域图数据结构在满足分析精度的前提下支持高效的点-面包含分析, 有利于线-面之间空间关系复合和结果图形空间关系构建, 提高了混合叠置算法的可靠性和效率. 一定规模数据空间拓扑叠置分析的实验结果表明, 本文算法取得了较好的综合运算性能表现, 具有良好的应用价值. 下一步将分析本文算法中计算处理所隐含的内在并行性, 引入多核并行计算机制, 进一步提高算法的计算分析效率.

参考文献(References):

[1] Rivero M, Feito F R. Boolean operations on general planar

polygons[J]. Computers & Graphics, 2000 , 24(6): 881-896

[2] Peng Y, Yong J H, Dong W M, et al. A new algorithm for

Boolean operations on general polygons[J]. Computers & Graphics, 2005, 29(1): 57-70

[3] Liu Y K, Wang X Q, Bao S Z, et al. An algorithm for polygon

叠置 总时间 转换 叠置 总时间 0.202 0.249 2.871 0.561 3.432 0.782 1.015 4.820 1.904 6.724 1.778 2.247 6.365 2.949 9.314 3.370 4.198 8.880 4.508 13.388 25.084

35.475

26.208

16.302

42.510

clipping, and for determining polygon intersections and un-ions[J]. Computers & Geosciences, 2007, 33(5): 589-598

[4]

Liu Yongkui , Gao Yun , Huang Youqun. An efficient algorithm for polygon clipping[J]. Journal of Software, 2003, 14(4): 845-856(in Chinese)

(刘勇奎, 高 云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4): 845-856)

[5] Žalik B. Two efficient algorithms for determining intersection points between simple polygons[J]. Computers & Geosciences, 2000, 26(2): 137-151

[6]

Martínez F, Rueda A J, Feito F R. A new algorithm for com-puting Boolean operations on polygons[J]. Computers & Geo-sciences, 2009, 35(6): 1177-1185

[7]

Martínez F, Ogayar C, Jiménez J R, et al. A simple algorithm for Boolean operations on polygons[J]. Advances in Engineer-ing Software, 2013, 64: 11-19

[8]

Zhu Xiaomin, Zhao Hongchao, Fang Jinyun. A robust and effi-cient method for vector map overlay[J]. Journal of Remote Sensing, 2012, 16(3): 457-466(in Chinese)

(朱效民, 赵红超, 方金云. 鲁棒高效的矢量地图叠加分析算法[J]. 遥感学报, 2012, 16(3) : 457-466)

[9]

Xie Zhong, Ye Zi, Wu Liang. Polygon overlay analysis algo-rithm using the simple data model[J]. Geography and Geo-Information Science , 2007, 23(3): 19-23(in Chinese)

(谢 忠, 叶 梓, 吴 亮. 简单要素模型下的多边形叠置分析算法[J]. 地理与地理信息科学, 2007, 23(3): 19-23)

[10]

Chen Zhanlong, Wu Xincai, Wu Liang. Polygon overlay analy-sis algorithm based on monotone chain and STR tree in the simple feature model[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(1): 102-108(in Chinese)

(陈占龙, 吴信才, 吴 亮. 基于单调链和STR树的简单要素模型多边形叠置分析算法[J]. 测绘学报, 2010, 39(1): 102-108)

[11]

Dong Peng, Li Jinping, Bai Yuqi, et al. Vector map overlay al-gorithm based on improved quadtree indexing[J]. Journal of Computer-Aided Design & Computer Graphics, 2004, 16(4): 530-534(in Chinese)

(董 鹏, 李津平, 白予琦, 等. 基于改进四叉树索引的矢量地图叠加分析算法[J].计算机辅助设计与图形学学报, 2004, 16(4): 530-534)

[12]

Fei Lifan, Li Peichuan. Accelerating the process of intersection of vector data by raster detection plus vector calculation[J]. Acta Geodaetica et Cartographica Sinica, 1993, 22(3): 195-204(in Chinese)

(费立凡, 李沛川. 用栅格探测/矢量计算法加速矢量数据的求交过程[J]. 测绘学报, 1993, 22(3): 195-204)

[13]

Qiao Yanyou, Wu Honggan. An algorithm to compute intersec-

第9期

谢顺平, 等: 面向空间关系复合的矢量多边形图形拓扑叠置分析算法 1685 (虞强源, 刘大有, 王生生. 一种栅格图层的模糊叠置分析模型[J]. 中国图象图形学报, 2004, 9(7): 832-836)

[16] Cui Can, Wang Jiechen. Boolean operations on polygons by

using trapezoidal decomposition[J]. Acta Geodaetica et Carto-graphica Sinica, 2011, 40(1): 104-110(in Chinese)

(崔 璨, 王结臣. 一种基于梯形剖分的多边形布尔运算方法[J]. 测绘学报, 2011, 40(1): 104-110)

[17] Huang Xingyuan, Ma Jinsong, Tang Qin. An introduction to

geographic information system[M]. 2rd ed. Beijing: Higher Education Press, 2001: 37-41(in Chinese)

(黄杏元, 马劲松, 汤 勤. 地理信息系统概论[M]. 2版, 北京: 高等教育出版社, 2001: 37-41)

tions of many arcs[J]. Acta Geodaetica et Cartographica Sinica, 1997, 26(1): 47-51(in Chinese)

(乔彦友, 武红敢. 多曲线求交的批量解法[J]. 测绘学报, 1997, 26(1): 47-51)

[14] Shen Dingtao, Wang Jiechen, Cui Can. Polygon overlay opera-tion using run-length encoding[J]. Computer Engineering and Applications. 2009, 45(25): 41-44(in Chinese).

(沈定涛, 王结臣, 崔 璨. 借助游程运算实现多边形叠置分析[J]. 计算机工程与应用, 2009, 45(25): 41-44)

[15] Yu Qiangyuan, Liu Dayou, Wang Shengsheng. A fuzzy overlay

analysis model for raster map layers[J]. Journal of Image and Graphics, 2004, 9(7): 832-836(in Chinese)