地球信息科学学报

地球信息科学学报 ›› 2014, Vol. 16 ›› Issue (2): 158-164.doi: 10.3724/SP.J.1047.2014.00158

• 本期要文(可全文下载) • 上一篇    下一篇

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

范俊甫1,2, 马廷1, 周成虎1, 周玉科1, 许涛1,2   

  1. 1. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室, 北京 100101;
    2. 中国科学院大学, 北京 100049
  • 收稿日期:2013-05-27 修回日期:2013-09-23 出版日期:2014-03-10 发布日期:2014-03-10
  • 通讯作者: 范俊甫（1985- ），男，博士生，研究方向为并行空间分析算法和遥感信息提取等。E-mail：fanjf@lreis.ac.cn E-mail:fanjf@lreis.ac.cn
  • 作者简介:范俊甫（1985- ），男，博士生，研究方向为并行空间分析算法和遥感信息提取等。E-mail：fanjf@lreis.ac.cn
  • 基金资助:

    国家科技支撑计划项目（2011BAH06B03、2011BAH24B10）；中国科学院重点部署项目（KZZD-EW-07）。

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

FAN Junfu1,2, MA Ting1, ZHOU Chenghu1, ZHOU Yuke1, XU Tao1,2   

  1. 1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research, CAS, Beijing 100101, China;
    2. University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2013-05-27 Revised:2013-09-23 Online:2014-03-10 Published:2014-03-10
  • Contact: 10.3724/SP.J.1047.2014.00158 E-mail:fanjf@lreis.ac.cn

PDF (PC)

赞

被引次数

11 | 1

摘要：

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

关键词: 多边形合并, “树状”合并, 效率评价, 分治法, “滚雪球”合并

Abstract:

Vector data overlay analysis methods, with the most difficult and tricky core issue of overlapping between polygons, are the basic analysis approaches for many spatial analysis algorithms in Geography Information 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 problem solving, can reduce the cumulative effects of nodes of the polygon union results at average level. And, compared with classic snowball union strategy, it can accelerate the polygon union algorithm effectively. In this research, 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 acceleration potentiality derived from the tree-like union strategy can be assessed conveniently for a group of polygons. 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 algorithm. 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 research 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.

Key words: polygon union, divide-and-conquer method, efficiency evaluation, snowball union, tree-like union