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

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

A Plane Sweep Based Arc Splitting and PolygonAuto-Construction Algorithm

Aiming at the deficiency of traditional polygon auto-construction algorithm in automation and timeefficiency, which leads to the insufficiency of commercial GIS softwares’ data processing and spatial-temporalanalysis 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 untilpolygon construction. Next, it takes full advantage of useful information during intersection testing to realize arcsplitting 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 resultof experiments proves the proposed algorithm improves efficiency significantly in comparison with traditionalalgorithms.