几何部件缓冲区域合并的Buffer算法及其并行优化方法

doi:10.13485/j.cnki.11-2089.2014.0122

测绘学报 ›› 2014, Vol. 43 ›› Issue (9): 969-975.doi: 10.13485/j.cnki.11-2089.2014.0122

几何部件缓冲区域合并的Buffer算法及其并行优化方法

范俊甫¹,²,³,马廷⁴,周成虎⁴,季民⁵,周玉科⁴,许涛³,⁴

1. 山东理工大学
2. 中国科学院地理科学与资源研究所
3. 中国科学院大学
4. 中国科学院地理科学与资源研究所
5. 山东科技大学

收稿日期:2013-12-06 修回日期:2014-06-23 出版日期:2014-09-20 发布日期:2014-09-25
通讯作者: 范俊甫 E-mail:fanjf@lreis.ac.cn
基金资助:
国家科技支撑计划项目;国家科技支撑计划项目;中国科学院重点部署项目

Research on a Buffer Algorithm Based on Region-Merging of Buffered Geometry Components and Its Parallel Optimization

FAN Junfu¹,²,³,MA Ting¹,ZHOU Chenghu¹,JI Min⁴,ZHOU Yuke¹,XU Tao¹,³

1. Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences
2. Shandong University of Technology
3. University of Chinese Academy of Sciences
4. Shan Dong University of Science and Technology

Received:2013-12-06 Revised:2014-06-23 Online:2014-09-20 Published:2014-09-25
Contact: FAN Junfu E-mail:fanjf@lreis.ac.cn

摘要/Abstract

摘要：

摘要：本文在介绍一种基于几何部件缓冲区域合并的矢量数据缓冲区生成算法的基础上，采用数据并行思想和MPI编程模型对缓冲区算法的并行化实现和优化方法开展研究。实验结果显示，与ArcGIS Buffer工具相比，（1）当缓冲区结果多边形不合并时，虽然串行缓冲区算法的时间开销较高，但可轻易通过并行方式实现加速。（2）当缓冲区结果合并时，本文算法要明显优于ArcGIS Buffer工具，并且经过优化的并行缓冲区算法表现出了更高的计算效率和更大规模的数据处理能力。因此，基于几何部件缓冲区域合并的Buffer算法具备一定的实用价值，本文提出的按结点数量的任务分解方法和进程间结果“树状”归并策略是对缓冲区算法进行并行优化的有效途径，对GIS中其他矢量分析算法的并行化及相关优化工作也具有一定的借鉴意义。

关键词: 并行算法, 缓冲区, MPI, 任务分解, “树状”归并

Abstract:

Abstract: The double-sided parallel line method and the geometry rasterization-based dilation method have been extensively used for buffer generation in spatial analysis. The former involves a series of complex numerical operations and may not be suitable for parallelized computation; the latter inevitably introduces precision problems and computation complexity. In this paper, we proposed a parallel buffer construction algorithm based on region-merging of buffered geometry components in association with the message passing interface (MPI) parallel programming model. Several optimization strategies were studied for the parallel buffer algorithm. The performances of both serial and parallel buffer algorithms were comparably analyzed. Three performance bottlenecks which significantly impact the algorithm efficiency were identified: area merging operation, task load balance strategy and MPI inter-process results merging methods. Corresponding optimization approaches involving tree-like area and inter-process results merging and the parallel task partition based on vertex number oriented parallel task partition strategy were suggested to overcome these bottlenecks. Several experiments were carried out to examine the performance efficiency of the optimized parallel algorithm. The estimation results suggested that our method could provide high performance and processing ability for buffer construction in a parallel environment. Our method could provide insights into the parallelization of spatial analysis algorithm.

Key words: Parallel Algorithm, Buffer, MPI, Task Partition, Tree-like Merging

中图分类号:

P209

范俊甫马廷周成虎季民周玉科许涛. 几何部件缓冲区域合并的Buffer算法及其并行优化方法[J]. 测绘学报, 2014, 43(9): 969-975.

FAN Junfu MA Ting ZHOU Chenghu JI Min ZHOU Yuke XU Tao. Research on a Buffer Algorithm Based on Region-Merging of Buffered Geometry Components and Its Parallel Optimization[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(9): 969-975.

参考文献

[1] Turton I., Openshaw S. High-performance computing and geography: developments, issues, and case studies[J]. Environment and Planning: A. 30, 1998, pp. 1839-1856.
[2] Clarke K. C. Geocomputation’s Future at the Extremes: High Performance Computing and Nanoclients[J]. Parallel Computing, 2003, 29(10): 1281-1295.
[3] Grama A, Gupta A, Karypis G, et al. Introduction to Parallel Computing (Second Edition)[M]. Addison-Wesley, 2003, 656pp.
[4] Wang J. C., Wang B., Hu W., et al. Review on Parallel Spatial Analysis Algorithms[J]. Geography and Geo-Information Science, 2011, 27(6): 1-5. (王结臣, 王豹, 胡玮, 等. 并行空间分析算法研究进展及评述[J]. 地理与地理信息科学, 2011, 27(6): 1-5.)
[5] Sloan T. M., Mineter M.J., Dowers S., et al. Partitioning of Vector-Topological Data for Parallel GIS Operations: Assessment and Performance Analysis[C]. In: Proceedings of Euro-Par’99 Parallel Processing, Lecture Notes in Computer Science, 1999, 1685: 691-694.
[6] Mineter M. J., Dowers S. Parallel processing for geographical applications: A layered approach[J]. Journal of Geographical Systems, 1999, 1(1): 61-74.
[7] Darling G.J., Sloan T.M., Mulholland C. The input, preparation and distribution of data for parallel GIS operations[C]. In: Proceedings of Euro-Par 2000, Lecture Notes in Computer Science, 2000, 1900: 500–505.
[8] Mineter M. J. A software framework to create vector-topology in parallel GIS operations[J]. International Journal of Geographical Information Science, 2003, 17(3): 203-222.
[9] Wu H. H. Problem of Buffer Zone Construction in GIS[J]. Journal of Wuhan Technical University of Surveying and Mapping (WTUSM), 1997, 22(4): 358-366. (毋河海. 关于GIS缓冲区的建立问题[J]. 武汉测绘科技大学学报, 1997, 22(4):358-366.)
[10] Environmental Systems Research Institute, Inc. Buffer - GIS Dictionary[EB/OL]. 2012. URL: http://support.esri.com/en/knowledgebase/GISDictionary/term/buffer, [accessed Mar. 1 2013].
[11] Zalik, B., Zadravec, M., Clapworthy, G. Construction of a Non-Symmetric Geometric Buffer From a Set of Line Segments[J]. Computers & Geosciences, 2003, 29(1): 53–63.
[12] Bhatia S., Vira V., Choksi D., et al. An algorithm for generating geometric buffers for vector feature layers[J], Geo-spatial Information Science, 2013, 16(2): 130-138.
[13] Wu H. Y., Gong J. Y., Li D. R. Buffer Curve and Buffer Generation Algorithm in Aid of Edge-Constrained Triangle Network[J]. Acta Geodaetica et Cartograohica Sinica, 1999, 28(4): 356-359. (吴华意, 龚健雅, 李德仁. 缓冲曲线和边约束三角网辅助的缓冲区生成算法[J]. 测绘学报, 1999, 28(4): 356-359.)
[14] Zhu Huang, Ai Tinghua, Wang Hong. The Buffer Construction of line object based on the geometric scan idea[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2): 171-176. (朱熀, 艾廷华, 王洪. 基于条带扫描思想的线目标缓冲区快速构建[J]. 测绘学报, 2006, 35(2): 171-176.)
[15] Li Ke, Du Lin. An Algorithm of Buffer Zones Based on Algorithm of Dilation. Journal of Institute of Surveying and Mapping, 2005, 22(3): 229-231. (李科, 杜林. 基于膨胀算法的缓冲区分析的设计与实现[J]. 测绘学院学报, 2005, 22(3): 229-231.)
[16] Yao Y. Q., Gao J. S., Meng L. K., et al. Parallel Computing of Buffer Analysis Based On Grid Computing. Geospatial Information, 2007, 5(1): 98-101. (姚艺强, 高劲松, 孟令奎, 等. 网格环境下缓冲区分析的并行计算[J]. 地理空间信息, 2007, 5(1): 98-101.)
[17] Vatti B. R. A Generic Solution to Polygon Clipping[J]. Communications of the ACM, 1992, 35(7): 56-63.
[18] Murta A., 1998. A Generic Polygon Clipping Library[EB/OL]. URL:http://www.cs.man.ac.uk/~toby/alan/software/gpc.html. [accessed Nov. 2012].
[19] Greiner G., Hormann K. Efficient clipping of arbitrary polygons[J]. ACM Transactions on Graphics, 1998, 17(2): 71-83.
[20] Sutherland I. E., Hodgman G. W. Reentrant Polygon Clipping[J]. Communications of the ACM, 1974, 17(1): 32-42.
[21] Weiler K., Atherton P. Hidden surface removal using polygon area sorting[C]. In: Proceedings of the SIGGRAPH’77. New York: ACM Press, 1977, pp. 214-222.
[22] Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching[C]. In: Proceedings of ACM SIGMOD Conference on Management of Data. New York: ACM Press, 1984, pp. 47-57.

几何部件缓冲区域合并的Buffer算法及其并行优化方法

Research on a Buffer Algorithm Based on Region-Merging of Buffered Geometry Components and Its Parallel Optimization

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	朱园媛, 朱庆, 张叶廷, 彭明军, 高山. 侧视地图中建筑物轮廓线提取的三维城市模型法[J]. 测绘学报, 2015, 44(9): 1036-1041.
[2]	周浩, 罗志才, 钟波, 陆飚. 利用最小二乘直接法反演卫星重力场模型的MPI并行算法[J]. 测绘学报, 2015, 44(8): 833-839.
[3]	闫志远孙文彬陈宗娟赵帅阳. PC集群环境下的并行地理网络车辆路径算法[J]. 测绘学报, 2014, 43(7): 753-760.
[4]	沈婕. MPI环境下等高线简化并行计算适宜性研究[J]. , 2013, 42(4): 0-0.
[5]	刘小凤吴艳兰胡海. 面状要素的多层次骨架线提取[J]. , 2013, 42(4): 0-0.
[6]	杨慧闾国年盛业华. 基于HTN规划的分布式协同地理建模任务分解方法研究[J]. , 2013, 42(3): 0-0.