卢 浩，钟耳顺，王天宝，王少华

（1.中国科学院地理科学与资源研究所，北京100101；2.中国科学院研究生院，北京100039；3.北京超图软件股份有限公司，北京100015）

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

卢 浩1，2，钟耳顺1，3，王天宝1，2，王少华1，2

（1.中国科学院地理科学与资源研究所，北京100101；2.中国科学院研究生院，北京100039；3.北京超图软件股份有限公司，北京100015）

在GIS的众多应用中，多边形数据的自动生成和多边形数据拓扑关系的构建与维护都是一种高频率的操作。该文在分析和总结已有多边形数据自动生成算法和拓扑关系生成算法基础上，提出了一种基于拓扑信息的多边形数据自动生成算法（PG－TI）。介绍了该算法的数据结构以及弧段邻接关系确定、多边形搜索和拓扑关系确定3个核心过程，重点探讨了使用多边形搜索过程中建立的拓扑信息来提升拓扑关系确定过程性能，在此基础上与传统算法和Arc GIS中对应算法的时间复杂度进行了对比分析和验证。

地理信息系统；多边形；拓扑信息；包含关系

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 弧段邻接关系确定

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

（1）逻辑结点索引数组：

TNodeInfo［NodeCount］NodeIndex；

数组类型为逻辑结点信息结构体：

其中，nPos为构成此逻辑结点的弧段起始索引值，n Num为构成此逻辑结点的弧段数目，数组长度NodeCount为逻辑结点数目。

（2）弧段索引数组：

int［ArcCount＊2］ArcIndex；

其中，ArcCount为弧段数目，因为每个弧段包括起始和终止两个结点，因此数组长度为弧段数目的二倍。

（3）弧段到逻辑结点索引数组：

int［ArcCount］ArcFromID；

int［ArcCount］Arc ToID；

NodeIndex和ArcIndex记录逻辑结点到弧段的正向索引，其中NodeIndex为逻辑结点索引，因为每个逻辑结点都由一个或多个弧段的结点构成，则其需要记录的是每个逻辑结点对应的多个弧段在弧段数组ArcIndex中的起始索引（多个弧段按照方位角排序）nPos以及弧段数目n Num。ArcIndex中记录的是每个逻辑结点对应的弧段ID，如果为该弧段起始结点，则ID值为正，如果为终止结点，则ID值为负。ArcFromID和Arc ToID记录弧段到逻辑结点的反向索引，即分别记录每个弧段起始和终止结点对应的逻辑结点ID。索引结构如图1所示。

图1 弧段邻接索引结构Fig.1 Arc adjacency index chart

图1中，NodeIndex中每个元素对应一个逻辑结点，通过nPos和n Num可以索引到ArcIndex中对应此逻辑结点的一条或多条弧段ID（即图1中的ArcID），通过ArcID可以索引到ArcFromID和Arc ToID数组中记录的该弧段的起始和终止逻辑结点索引，即从ArcFromID和Arc ToID中通过弧段到逻辑结点的反向索引可以回到NodeIndex中。

弧段邻接关系确定整体过程如下：1）建立均匀网格索引，并计算每条弧段起始和终止结点对应的索引位置；2）计算索引结点处对应的方位角（此处约定为从X正半轴起逆时针旋转角度）和所归属的弧段一并存储；3）遍历均匀格网索引，进行结点匹配，由多个结点组成的逻辑结点按照方位角大小排序后将索引信息存入NodeIndex、ArcIndex、ArcFromID和Arc ToID结构中。

2.2 多边形搜索

当弧段邻接关系建立后，算法初始输入的离散弧段已通过起始和终止结点坐标匹配为对应的逻辑结点，通过此逻辑结点和弧段组成的“逻辑网络”即可进行多边形搜索（图2）。具体搜索过程为：1）假定起始逻辑结点为N1，则首先进行弧段A1搜索，通过A1到达逻辑结点N2后搜索到弧段A2，类似可以通过弧段A3后回到起始逻辑结点N1，此时构成闭合环路，生成多边形N1N2N3N1。2）继续以N1为起始结点搜索（逆时针寻找下一个弧段），此时处理弧段A5，到达结点N4后根据弧段顺序处理弧段A7，依次搜索到弧段A8和A1后构成闭合环路，生成多边形N1N4N5N2N1。3）继续以N1为起始结点，搜索该逻辑结点最后一个弧段A3，类似过程1，可以得到多边形N1N3N4N1，此时N1所有关联弧段的左右多边形都已生成。4）继续处理下一个逻辑结点N2，因为A1的左右多边形都已生成，则从A2弧段开始搜索，顺次进行A2A8A63个弧段的搜索，生成多边形N2N5N3N2，此时N2所有关联弧段的左右多边形都已生成。5）继续处理下一个逻辑结点N3，生成多边形N3N5N4N3，此时所有逻辑结点关联的弧段左右多边形都已搜索完毕，共生成5个简单多边形（面积最大的多边形N1N4N5N2N1为无效多边形）。

图2 多边形搜索示意Fig.2 Diagram of polygon search

2.3 拓扑关系确定

经过多边形搜索过程，所有简单多边形都已生成，此时需要进行无效多边形剔除和多边形包含关系判定（用以组合为复杂多边形）。齐华［2］给出的判定算法主要步骤为：1）将生成的简单多边形按照面积从小到大排序；2）从较小多边形开始处理，计算出此多边形内点，判定内点和其它多边形的包含关系，从而得到该多边形的父多边形。

值得注意的是，在判定内点和其它多边形的包含关系时，当生成多边形数目较多时，容易产生大量的无效判定，导致整体判定效率较低；而通过解析多边形搜索过程中记录的每个弧段左右多边形拓扑信息，可以提升判定效率。本文的主要思路是将离散的简单多边形根据其拓扑邻接关系组成若干拓扑邻接区域Tn（图3），则可以基于这些拓扑邻接区域判定拓扑关系，而不再基于多边形搜索过程产生的大量简单多边形进行判定。

图3 拓扑邻接区域Fig.3 Topology adjacency area

如图3所示，多个离散多边形被划分为T1、T2和T33个拓扑邻接区域，简单多边形P被T3中的某个多边形包含，但其本身不属于任何拓扑邻接区域（因为其边界弧段没有和其它多边形共用），而拓扑邻接区域具有如下优良性质：1）如果Pn∈Ti、Pm∈Tj且i＝j，则Pn和Pm不存在包含关系，即同属一个拓扑邻接区域的多边形之间不存在包含关系；2）如果Pn∈Ti且Pn被P包含，则有Pm∈Ti且Pm被P包含，即一个拓扑邻接区域中的多边形被另一个多边形包含，则此拓扑邻接区域中的其它多边形也被这个多边形包含。换言之，包含关系判定只需要在不属于任何拓扑邻接区域的多边形之间和该类多边形与拓扑邻接区域多边形之间进行，且同一拓扑邻接区域中的多边形具有同样的包含关系。

2.4 基于拓扑信息的判定算法

定义两个数组int［ArcCount］Arc LeftPolygon和int［ArcCount］Arc RightPolygon，分别存储每个弧段的左多边形ID和右多边形ID信息，在多边形搜索过程中，可以同步生成并存储每条弧度的左右多边形信息。定义一个二维数组int［RegionCount］［Arcs］Region ArcsID，存储构成每个多边形的边界弧段ID，第一维长度为多边形数目。

算法整体流程如下：1）遍历左右多边形数组，将构成每个多边形的弧段ID记录到Region ArcsID中，其中从Arc LeftPolygon中读取的记录为正ID，从Arc RightPolygon中读取的记录为负ID。2）遍历所有多边形对象，使用一个栈结构进行广度优先搜索，对共用公共弧段而同属于某一个拓扑邻接区域的多边形进行标识。3）将所有多边形按照面积从小到大排序，从面积较大的多边形开始遍历，将每一个拓扑邻接区域中面积最大的多边形（即外边界围成的无效多边形N1N4N5N2N1）剔除。4）从面积较小的多边形开始遍历，根据每个多边形的最小外界矩形范围建立空间索引。5）依次处理每个多边形，通过内点判定的方法寻找其是否被其它某个多边形包含，可通过一些过滤操作来提高判定效率：根据2.3节的性质1可知，同属于某个拓扑邻接区域的多边形之间不存在包含关系，则无需对相同拓扑邻接区域的多边形进行关系判定；由于在步骤4中使用多边形最小外接矩形建立空间索引，因此可以根据多边形最小外接矩形进行过滤操作，即最小外接矩形不存在包含关系的多边形之间一定不存在包含关系。

3 分析与实验

3.1 时间复杂度分析

假定n为输入弧段数目，则弧段结点格网索引生成和方位角计算次数为2n，又因为在格网索引基础上进行结点匹配，则匹配计算次数为k×n，即此过程时间复杂度为O（n）。多边形搜索过程中因为每条弧段只经过左多边形和右多边形两次搜索，则其时间复杂度也为O（n）。在传统拓扑关系确定算法中，需要判定每个多边形的内点与其它多边形的包含关系，其时间复杂度为O（m2）（m为生成的简单多边形数目）；而改进算法可以将需要判定的简单多边形数目显著减少为m0，时间复杂度为O（m20），且m0＜＜m，即算法整体时间复杂度为O（n＋m20）。

3.2 实验结果分析

为了验证该算法的有效性，使用C＋＋语言开发了原型系统，并使用多组不同规模的真实弧段数据进行对比测试，实验环境为一台主频2.6 GHz的双核处理器PC机，内存为2 GB。为了验证本文提出的基于拓扑信息的多边形生成算法（PG－TI）的高效性，与传统算法和ArcGIS中的多边形自动生成功能（Feature To Polygon）进行对比测试。

首先选取多组数据规模依次增大的弧段数据将PG－TI算法和传统算法进行对比测试（表1）。由于两个算法中多边形生成数目均相等（且生成的多边形形状一致），即PG－TI算法保证了生成结果的正确性，因此不再将生成多边形数目单独列出。从表1可以看出，PG－TI算法在生成效率方面较传统算法有了较大幅度的提升，且随着测试弧段数目增加，提升效果更加显著，即PG－TI算法对于大数据量下的多边形数据自动生成具有较好的处理性能。

表1 多边形自动生成测试结果对比Table 1 The result of polygon automatic generation comparison

为了进一步验证PG－TI算法的有效性，将测试弧段数据转换为Shape文件格式后在ArcGIS的Arc ToolBox模块中使用Feature To Polygon功能进行对比验证。表1中ArcGIS中的生成时间使用Arc ToolBox进度条中自动记录的处理时间（精度为秒）。通过此组对比实验可以看出，虽然ArcGIS的生成效率优于传统算法，但PG－TI算法整体性能仍优于ArcGIS的多边形自动生成功能，且弧段数据量较大时处理性能表现较好，对比结果如图4所示。

图4 3种多边形自动生成算法实验结果比较Fig.4 Comparison of the experimental results of three methods of polygon automatic generations

4 结语

多边形数据的自动生成是一个较为基础与重要的数据处理操作，核心过程包括弧段邻接关系确定、多边形搜索、拓扑关系确定等步骤。本文在总结和分析已有算法基础上，提出了一种基于拓扑信息的多边形数据自动生成算法，通过多边形搜索过程中生成的弧段左右多边形信息生成拓扑邻接区域，利用拓扑邻接区域的优良性质使得拓扑关系确定过程的效率有了较大提升。对算法时间复杂度进行了分析，并使用多组真实弧段数据与传统算法、ArcGIS的多边形生成功能进行了对比实验，证明本文算法处理性能优于传统算法和ArcGIS的相应功能，且较适宜进行大规模弧段数据的多边形自动生成处理。

［1］ 陈春，张树文，徐桂芬.GIS中多边形图拓扑信息生成的数学基础［J］.测绘学报，1996，25（4）：266－271.

［2］ 齐华.自动建立多边形拓扑关系算法步骤的优化与改进［J］.测绘学报，1997，26（3）：255－260.

［3］ 闫浩文，杨维芳，陈全功，等.基于方位角计算的拓扑多边形自动构建快速算法［J］.中国图象图形学报，2000，5A（7）：563－567.

［4］ 梁晓文，刘宗岐，陈宜金.基于夹角变化趋势的多边形自动搜索和生成算法［J］.中国图象图形学报，2005，10（6）：785－789.

［5］ 李大军，刘波，赵宝贵，等.拓扑多边形自动构建的一种改进算法［J］.计算机工程与应用，2005（16）：80－82.

［6］ 邓敏，刘文宝，黄杏元，等.空间目标的拓扑关系及其GIS应用分析［J］.中国图象图形学报，2006，11（2）：1743－1749.

［7］ EGENHOFER M J，HERRING J.Categorizing binary topological relationships between regions，lines and points in geographic databases［R］.Oronoi：Technical report，Department of Surveying Engineering，University of Maine，Oronoi，ME，1991.

［8］ RANDELL D，CUI Z，COHN A.A spatial logical based on regions and connection［A］.Proceedings of 3rd International Conference on Knowledge Representation and Reasoning［C］.Morgan－Kaufman Publishers，1992.165－176.

［9］ LI Z，ZHAO R，CHEN J.An algebra model for spatial relations［A］.Proceedings of the 3rd ISPRS Workshop on Dynamic and Multi－dimensional GIS［C］.Bangkok，2001.170－177.

［10］ 吴建新，方裕，陈斌.拓扑空间关系描述理论研究现状与发展［J］.地理与地理信息科学，2005，21（3）：1－4.

［11］ 齐华，刘文熙.建立结点上弧－弧拓扑关系的Qi算法［J］.测绘学报，1996，25（3）：233－235.

［12］ 高云琼，徐建刚，唐文武.同一结点上弧－弧拓扑关系生成的新算法［J］.计算机应用研究，2002（4）：58－59.

Abstract：It is essential to GIS for automatic generation of polygon data，creation and maintenance of polygon topology information as many GIS operations are based on them.In this paper，the current polygon data automatic generation algorithms are summarized and analyzed，as well as polygon topology information generation algorithms with other scholars，a more efficient polygon data automatic generation algorithm based on topology information is proposed.Firstly，the core contents of the algorithm data structure are presented，describing the three core process including arc adjacency，polygon search and topology relationship determination.Secondly，the topology information creation by the polygon search process is described，which can accelerate the process of topology relationship determine.Finally，the algorithm time complexity analysis is presented，as well as the experimental verification.

Key words：GIS；polygon；topology information；contain relationship

A Polygon Data Automatic Generation Algorithm Based on Topology Information

LU Hao1，2，ZHONG Er－shun1，3，WANG Tian－bao1，2，WANG Shao－hua1，2
（1.Institute of Geographic Sciences and Natural Resources Research，CAS，Beijing 100101；2.Graduate University of the Chinese Academy of Sciences，Beijing 100039；3.Super Map Software Co.Ltd.，Beijing 100015，China）

P208

A

1672－0504（2012）04－0038－04

2012－01－09；

2012－03－06

卢浩（1984－），男，博士研究生，主要研究方向为GIS矢量核心算法。E－mail：luhaonihao2008＠163.com