一种基于拓扑信息的多边形数据自动生成算法

0　引言

在 GIS中，多边形数据的自动生成是一种常用操作，而算法性能是研究的重点之一。多边形边界和区域内是多边形数据的两个基本组成部分，GIS软件中的多边形数据处理功能的完善和性能的提高均直接依赖于对这两个基本要素的处理。例如：左转算法的发现导致了多边形拓扑信息生成的自动化，点与多边形包含关系的判定定理使得岛区判定实现了计算机处理[1]。在多边形数据的自动生成过程中，一个重要的步骤是对于简单多边形数据间包含关系进行判定。齐华[2]给出了一个根据多边形内点和面积排序的闭合边界包含关系判定算法，该算法依赖于两个判定：判定1(闭合边界包含关系判定准则)：对于任意闭合边界a、b，如果a上有任意一点位于b的内部，则a被b所包含;判定2(父边界判定准则)：父边界是对于内边界满足判定1的外边界序列中面积最小的外边界。该算法主要通过判断多边形内点与其它多边形的空间位置关系得到多边形包含关系，而没有利用相关拓扑信息。

多边形数据自动生成算法主要步骤总结为弧段邻接关系确定、多边形搜索、拓扑关系确定3个过程。相关研究有：闫浩文等[3]提出了基于方位角计算的多边形自动生成算法，利用自动生成的内点进行点与多边形包含关系的判定;梁晓文等[4]提出了基于夹角变化趋势的多边形自动生成算法，根据相邻弧段夹角和判断多边形搜索方向，避免了无效多边形的生成;李大军等[5]在闫浩文[3]算法基础上，提出了一种改进算法，只进行2　N(N 为弧段数)次边的搜索，即可搜索出所有的多边形。但这些研究较少

涉及包含关系判定过程的改进。本文提出了一种基

于拓扑信息的多边形数据自动生成算法(PG-TI)，通过使用多边形搜索过程中生成的弧段左右多边形信

息，将此拓扑信息解析后用于后续的多边形包含关系判定中，使得多边形生成效率有了较大提升。

1　空间拓扑关系

地理实体间的空间拓扑关系是一种不随空间旋转、平移、放大/缩小等变换而发生改变的定性空间信息[6]，反映了空间目标的逻辑关系，其对空间推理、查询、分析等众多空间操作具有重要意义。研究较多的确定性空间拓扑关系模型包括 Egenhofer等在“四交模型”基础上提出的“九交模型”[7]，Randell等运用区域演算理论来表达空间区域拓扑特性的空间逻辑模型[8]，Li等基于空间代数方法提出的空间代数模型[9]，吴建新等提出的基于 Voronoi图的混合方法(用空间对象的 Voronoi区域作为其外部，对原模型进行了改进)[10]。

有学者将多边形拓扑关系的建立过程归结为：弧段结点的匹配和弧段连接关系的建立、同一结点上弧-弧拓扑关系的建立、闭合边界弧段相邻关系的建立以及闭合边界包含关系的确定等步骤[2]。针对计算较为耗时的同一结点上弧-弧拓扑关系的建立，众多学者提出了改进算法，包括使用泰勒级数展开近似值替代，使用函数Qi(x，y)[11]作为参数，基于计算几何矢量外积的算法[12]。而对于较为复杂的闭合边界包含关系确定过程研究和改进较少，本文则着重针对该过程进行基于拓扑信息的研究和改进。

2　改进算法描述

本文算法在弧段邻接关系确定过程中，通过使用均匀网格索引来加速邻接关系建立过程;在多边形搜索过程中主要使用左转算法，但会将弧段的左右多边形信息同步记录下来;由于左转算法会生成一些无效多边形，拓扑关系确定过程包括无效多边形的剔除和拓扑包含关系的确定。

2.1　弧段邻接关系确定

由于算法输入为离散的弧段数据，首先需要建立弧段之间的邻接关系，才可以进行后续的多边形搜索。而邻接关系的实质是公共结点的标识，因此该过程主要生成结点和弧段的双向索引。

更多内容请查看pdf