一种GIS拓扑多边形链搜索的改进算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (34): 23-27.

一种GIS拓扑多边形链搜索的改进算法

邱永红1，2，曾永年2，秦建新1，邹滨2

1.湖南师范大学地理信息工程系，长沙 410081
2.中南大学地球科学与信息物理学院，长沙 410083

出版日期:2012-12-01 发布日期:2012-11-30

Improved algorithm for searching GIS topological polygonal chains

QIU Yonghong1，2, ZENG Yongnian2, QIN Jianxin1, ZOU Bin2

1.Department of Geographic Information Engineering, Hunan Normal University, Changsha 410081, China
2.School of Geoscience and Info-Physics, Central South University, Changsha 410083, China

Online:2012-12-01 Published:2012-11-30

摘要/Abstract

摘要： 针对GIS拓扑多边形链搜索中悬挂弧段的处理问题，提出了一种改进算法。该算法利用在一趟搜索中，非悬挂弧段仅经过一次，而悬挂弧段会经过两次这一规律来识别并标记悬挂弧段；在进行多边形链搜索时，通过避让悬挂弧段以避免将其对应的关联弧段加入多边形链，从而保证搜索结果的正确性。测试结果表明，该算法能明显提高多边形链搜索的效率。

关键词: 多边形拓扑, 拓扑构建, 悬挂弧段, 多边形链

Abstract: An improved algorithm is proposed for dealing with the dangled edges in searching topological polygonal chains. In the algorithm, the laws, which a dangled edge is visited twice on one polygonal chain searching trip while only once for a non-dangled edge, are used to identify and mark dangled edges； and then to ensure the correctness of the search results, the associated incidences of dangled edges are eliminated from the polygonal chain. The test results show that the algorithm can significantly improve the efficiency of the polygonal chains search.

Key words: polygon topology, topology building, dangled edges, polygonal chains

邱永红1，2，曾永年2，秦建新1，邹滨2. 一种GIS拓扑多边形链搜索的改进算法[J]. 计算机工程与应用, 2012, 48(34): 23-27.

QIU Yonghong1，2, ZENG Yongnian2, QIN Jianxin1, ZOU Bin2. Improved algorithm for searching GIS topological polygonal chains[J]. Computer Engineering and Applications, 2012, 48(34): 23-27.