卢 浩,钟耳顺,王天宝,王少华
(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中对应算法的时间复杂度进行了对比分析和验证。
地理信息系统;多边形;拓扑信息;包含关系
在GIS中,多边形数据的自动生成是一种常用操作,而算法性能是研究的重点之一。多边形边界和区域内是多边形数据的两个基本组成部分,GIS软件中的多边形数据处理功能的完善和性能的提高均直接依赖于对这两个基本要素的处理。例如:左转算法的发现导致了多边形拓扑信息生成的自动化,点与多边形包含关系的判定定理使得岛区判定实现了计算机处理[1]。在多边形数据的自动生成过程中,一个重要的步骤是对于简单多边形数据间包含关系进行判定。……