北京大学学报自然科学版 ›› 2019, Vol. 55 ›› Issue (4): 675-682.DOI: 10.13209/j.0479-8023.2019.037

上一篇    下一篇

一种基于平面扫描的弧段分割与多边形自动构建算法

刘岳峰†, 孙鹰, 张凯, 陈越   

  1. 北京大学遥感与地理信息系统研究所, 北京 100871
  • 收稿日期:2018-06-15 修回日期:2018-09-19 出版日期:2019-07-20 发布日期:2019-07-20
  • 通讯作者: 刘岳峰, E-mail: yuefengliu(at)pku.edu.cn
  • 基金资助:
    国家自然科学基金(U1433102)资助

A Plane Sweep Based Arc Splitting and Polygon Auto-Construction Algorithm

LIU Yuefeng†, SUN Ying, ZHANG Kai, CHEN Yue   

  1. Institude of Remote Sensing and Geographic Information System, Peking University, Beijing 100871
  • Received:2018-06-15 Revised:2018-09-19 Online:2019-07-20 Published:2019-07-20
  • Contact: LIU Yuefeng, E-mail: yuefengliu(at)pku.edu.cn

RichHTML

PDF

摘要：

针对多边形自动生成的传统算法在自动化和时间效率方面的不足而导致的相应商用GIS软件数据处理和时空分析能力的欠缺, 提出一种基于扫描思想的弧段分割和多边形自动生成算法。本算法具有以下特点: 面向从求交开始至生成多边形结束的完整任务; 充分利用求交过程中的有益信息, 以较小的算法复杂度和极小的计算量, 实现弧段分割和多边形自动构建; 避免了传统方法中多边形嵌套关系的计算, 并能有效地处理桥和悬边问题。实验结果表明, 与传统算法相比, 本算法在效率方面有明显的提升。

关键词: 扫描线算法, 弧段分割, 多边形自动生成

Abstract:

Aiming at the deficiency of traditional polygon auto-construction algorithm in automation and time efficiency, which leads to the insufficiency of commercial GIS softwares’ data processing and spatial-temporal analysis ability, an arc splitting and polygon auto-construction algorithm based on plane sweep idea is proposed. Our algorithm contains three features as follows. First, it is a complete process from intersection testing until polygon construction. Next, it takes full advantage of useful information during intersection testing to realize arc splitting and polygon auto-construction at the cost of little algorithm complexity and computing resources. Finally, it avoids the calculation of nested relation and handles degenerate cases of bridge and dangling edge. The result of experiments proves the proposed algorithm improves efficiency significantly in comparison with traditional algorithms.

Key words: plane sweep algorithm, arc splitting, polygon auto-construction

版权所有 © 《北京大学学报（自然科学版）》编辑部
技术支持：北京玛格泰克科技发展有限公司