分治法在GIS多边形快速合并算法中的应用及效率提升评价模型

分治法采用分解-解决-合并的问题处理模式,应用于多边形合并算法能规避结点累积效应,与经典的"滚雪球"处理模式相比能有效提升多边形合并算法的计算效率。本文以多边形合并算法为研究对象,首先通过分析基于Vatti算法实现的多边形合并算子的效率相对于多边形顶点数的变化特征,指出合并过程中的结点累积效应是"滚雪球"多边形合并模式的潜在性能瓶颈和隐患。考虑分治法的"分而治之"思想在解决多边形合并问题上的适用性以及在归并排序算法中表现出的高效率,提出分治法的多边形"树状"合并处理模式,实现了面向要素集合或者要素层的多边形快速合并算法,最后给出了面向多边形合并的算法效率提升评价模型。实验结果显示,当仅有400个多边形时,"滚雪球"模式的时间开销约是"树状"合并模式的26倍,当需要合并11 200个多边形时,前者的时间开销约是后者的926倍。因此,基于分治法的多边形树状合并策略是对多边形合并算法以及应用到多边形合并算法的高级空间分析算法进行优化的可行途径。

Application of Divide-and-Conquer Method and Efficiency Evaluation Model in the Fast Union Algorithm of Polygons in GIS

Vector data overlay analysis methods, with the most difficult and tricky core issue of overlapping be-tween polygons, are the basic analysis approaches for many spatial analysis algorithms in Geography Informa-tion System （GIS） software and also the basis for many advanced spatial analysis models and complex spatial analysis applications. The divide and conquer strategy, with the paradigm of divide-conquer-combine for prob-lem solving, can reduce the cumulative effects of nodes of the polygon union results at average level. And, com-pared with classic snowball union strategy, it can accelerate the polygon union algorithm effectively. In this re-search, we took the polygon union algorithm as an example to describe a fast polygon union strategy named tree-like union method. Firstly, we analyzed the variation of the efficiency of the core operator, which is polygon union operation implemented by Vatti’s algorithm, with different node number of polygons, and figured out that the potential performance bottlenecks and pitfalls of the snowball union strategy is the cumulative effect of the nodes existing in the union process. Then based on the idea of divide and conquer we proposed a new approach named tree-like union strategy and implemented a union algorithm for polygon clusters or layers to solve the problem in polygon union process. Finally, we introduced an efficiency evaluate model by which the available ac-celeration potentiality derived from the tree-like union strategy can be assessed conveniently for a group of poly-gons. Experimental results in this research shown that compared with snowball union strategy, the tree-like union strategy based on the idea of divide and conquer could lead to great reduction of time costs of polygon union al-gorithm. Furthermore, we found that the time cost of snowball union was about 26-folds than that of tree-like method when union 400 polygons, and the number reached about 926 when union 11 200 polygons. Therefore, it can be inferred that the accelerate effects brought by the tree-like union strategy could become more significant when dealing with larger polygon datasets. We supposed that the tree-like union strategy proposed in this re-search represents a certain degree of applicability in operations similar with polygon union algorithm, which could be a potential and practical optimization approach for vector data overlapping and other advanced spatial analysis algorithms which involved with polygon union operations.