帮助 关于我们

返回检索结果

分治法在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 CSCD被引 234 次    
2.  Goodchild M F. Statistical aspects of the polygon overlay problem. Harvard Papers on Geographic Information Systems,1977:6 CSCD被引 1 次    
3.  吴信才. 地理信息系统原理、方法及应用,2002 CSCD被引 7 次    
4.  陈占龙. 基于单调链和STR树的简单要素模型多边形叠置分析算法. 测绘学报,2010,39(1):102-108 CSCD被引 10 次    
5.  Environmental Systems Research Institute, Inc. ESRI Shapefile Technical Description,1998 CSCD被引 2 次    
6.  Sutherland I E. Reentrant polygon clipping. Communications of the ACM,1974(17):32-42 CSCD被引 41 次    
7.  Weiler K. Hidden surface removal using polygon area sorting. Computer Graphics,1977,11(2):214-222 CSCD被引 21 次    
8.  Vatti B R. A generic solution to polygon clipping. Communications of the ACM,1992,35(7):56-63 CSCD被引 54 次    
9.  Greiner G. Efficient clipping of arbitrary polygons. ACM Transactions on Graphics,1998,17(2):71-83 CSCD被引 38 次    
10.  Murta A. A generic polygon clipping library,1998 CSCD被引 2 次    
11.  刘勇奎. 一个有效的多边形裁剪算法. 软件学报,2003,14(4):845-856 CSCD被引 35 次    
12.  王结臣. 一种有效的复杂多边形裁剪算法. 武汉大学学报(信息科学版),2010,35(3):369-372 CSCD被引 8 次    
13.  彭杰. 一种基于交点排序的高效多边形裁剪算法. 浙江大学学报(理学版),2012,39(1):107-111 CSCD被引 8 次    
14.  刘术华. 一种基于矢量游走的复域多边形合并算法. 微计算机应用,2011,32(6):1-7 CSCD被引 1 次    
15.  陈占龙. 多核环境下Hilbert曲线划分简单要素多边形合并算法. 计算机应用研究,2012,29(7):2747-2750 CSCD被引 5 次    
16.  Cormen T H. Introduction to algorithms (Second Edition),2001 CSCD被引 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 CSCD被引 1 次    
18.  Dwyer R A. A faster divide-and-conquer algorithm for constructing Delaunay Triangulations. Algorithmica,1987,2(2):137-151 CSCD被引 30 次    
19.  . Oracle Corporation and/or its affiliates. MySQL 5.6 Manual,2013 CSCD被引 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 CSCD被引 4 次    
引证文献 1 篇

1 周玉科 基于数据分治与双层索引的并行点面叠加分析方法研究 地理与地理信息科学,2015,31(2):1-6
CSCD被引 0 次

显示所有1篇文献

论文科学数据集
PlumX Metrics
相关文献

 作者相关
 关键词相关
 参考文献相关

版权所有 ©2008 中国科学院文献情报中心 制作维护：中国科学院文献情报中心
地址：北京中关村北四环西路33号 邮政编码：100190 联系电话：(010)82627496 E-mail:cscd@mail.las.ac.cn 京ICP备05002861号-4 | 京公网安备11010802043238号