分治法在GIS多边形快速合并算法中的应用及效率提升评价模型
Application of Divide-and-Conquer Method and Efficiency Evaluation Model in the Fast Union Algorithm of Polygons in GIS
查看参考文献20篇
|
文摘
|
分治法采用分解-解决-合并的问题处理模式,应用于多边形合并算法能规避结点累积效应,与经典的“滚雪球”处理模式相比能有效提升多边形合并算法的计算效率。本文以多边形合并算法为研究对象,首先通过分析基于Vatti算法实现的多边形合并算子的效率相对于多边形顶点数的变化特征,指出合并过程中的结点累积效应是“滚雪球”多边形合并模式的潜在性能瓶颈和隐患。考虑分治法的“分而治之”思想在解决多边形合并问题上的适用性以及在归并排序算法中表现出的高效率,提出分治法的多边形“树状”合并处理模式,实现了面向要素集合或者要素层的多边形快速合并算法,最后给出了面向多边形合并的算法效率提升评价模型。实验结果显示,当仅有400个多边形时,“滚雪球”模式的时间开销约是“树状”合并模式的26倍,当需要合并11200个多边形时,前者的时间开销约是后者的926倍。因此,基于分治法的多边形树状合并策略是对多边形合并算法以及应用到多边形合并算法的高级空间分析算法进行优化的可行途径。 |
|
其他语种文摘
|
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. |
|
来源
|
地球信息科学学报
,2014,16(2):158-164 【核心库】
|
|
关键词
|
多边形合并
;
“滚雪球”合并
;
“树状”合并
;
分治法
;
效率评价
|
|
地址
|
中国科学院地理科学与资源研究所, 资源与环境信息系统国家重点实验室, 北京, 100101
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1560-8999 |
|
学科
|
数学;自动化技术、计算机技术 |
|
基金
|
国家科技支撑计划项目
;
中国科学院重点部署项目
|
|
文献收藏号
|
CSCD:5090316
|
参考文献 共
20
共1页
|
|
1.
陈述彭.
地理信息系统导论,1999
|
被引
234
次
|
|
|
|
|
2.
Goodchild M F. Statistical aspects of the polygon overlay problem.
Harvard Papers on Geographic Information Systems,1977:6
|
被引
1
次
|
|
|
|
|
3.
吴信才.
地理信息系统原理、方法及应用,2002
|
被引
7
次
|
|
|
|
|
4.
陈占龙. 基于单调链和STR树的简单要素模型多边形叠置分析算法.
测绘学报,2010,39(1):102-108
|
被引
10
次
|
|
|
|
|
5.
Environmental Systems Research Institute, Inc.
ESRI Shapefile Technical Description,1998
|
被引
2
次
|
|
|
|
|
6.
Sutherland I E. Reentrant polygon clipping.
Communications of the ACM,1974(17):32-42
|
被引
37
次
|
|
|
|
|
7.
Weiler K. Hidden surface removal using polygon area sorting.
Computer Graphics,1977,11(2):214-222
|
被引
21
次
|
|
|
|
|
8.
Vatti B R. A generic solution to polygon clipping.
Communications of the ACM,1992,35(7):56-63
|
被引
51
次
|
|
|
|
|
9.
Greiner G. Efficient clipping of arbitrary polygons.
ACM Transactions on Graphics,1998,17(2):71-83
|
被引
37
次
|
|
|
|
|
10.
Murta A.
A generic polygon clipping library,1998
|
被引
2
次
|
|
|
|
|
11.
刘勇奎. 一个有效的多边形裁剪算法.
软件学报,2003,14(4):845-856
|
被引
34
次
|
|
|
|
|
12.
王结臣. 一种有效的复杂多边形裁剪算法.
武汉大学学报(信息科学版),2010,35(3):369-372
|
被引
8
次
|
|
|
|
|
13.
彭杰. 一种基于交点排序的高效多边形裁剪算法.
浙江大学学报(理学版),2012,39(1):107-111
|
被引
8
次
|
|
|
|
|
14.
刘术华. 一种基于矢量游走的复域多边形合并算法.
微计算机应用,2011,32(6):1-7
|
被引
1
次
|
|
|
|
|
15.
陈占龙. 多核环境下Hilbert曲线划分简单要素多边形合并算法.
计算机应用研究,2012,29(7):2747-2750
|
被引
5
次
|
|
|
|
|
16.
Cormen T H.
Introduction to algorithms (Second Edition),2001
|
被引
9
次
|
|
|
|
|
17.
Bentley J L. Divide-and-conquer in multidimensional space.
Proceedings of the Eighth Annual ACM Symposium on Theory of Computing (Proceeding STOC '76),1976:220-230
|
被引
1
次
|
|
|
|
|
18.
Dwyer R A. A faster divide-and-conquer algorithm for constructing Delaunay Triangulations.
Algorithmica,1987,2(2):137-151
|
被引
32
次
|
|
|
|
|
19.
.
Oracle Corporation and/or its affiliates. MySQL 5.6 Manual,2013
|
被引
2
次
|
|
|
|
|
20.
Guttman A. R-trees: A dynamic index structure for spatial searching.
Proceedings of ACM SIGMOD Conference on Management of Data,1984:47-57
|
被引
4
次
|
|
|
|
|
了解气象卫星更多信息，请访问