北京大学学报（自然科学版）2019，Vol.55Issue(4)：675-682,8.DOI:10.13209/j.0479-8023.2019.037
一种基于平面扫描的弧段分割与多边形自动构建算法
A Plane Sweep Based Arc Splitting and Polygon Auto-Construction Algorithm
摘要
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引用本文复制引用
刘岳峰,孙鹰,张凯,陈越..一种基于平面扫描的弧段分割与多边形自动构建算法[J].北京大学学报（自然科学版）,2019,55(4):675-682,8.基金项目
国家自然科学基金(U1433102)资助 （U1433102）
