全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
测绘学报  2014 

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

DOI: 10.13485/j.cnki.11-2089.2014.0122, PP. 969-975

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]  Greiner G., Hormann K. Efficient clipping of arbitrary polygons[J]. ACM Transactions on Graphics, 1998, 17(2): 71-83.
[2]  Sutherland I. E., Hodgman G. W. Reentrant Polygon Clipping[J]. Communications of the ACM, 1974, 17(1): 32-42.
[3]  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.
[4]  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.
[5]  Turton I., Openshaw S. High-performance computing and geography: developments, issues, and case studies[J]. Environment and Planning: A. 30, 1998, pp. 1839-1856.
[6]  Clarke K. C. Geocomputation’s Future at the Extremes: High Performance Computing and Nanoclients[J]. Parallel Computing, 2003, 29(10): 1281-1295.
[7]  Grama A, Gupta A, Karypis G, et al. Introduction to Parallel Computing (Second Edition)[M]. Addison-Wesley, 2003, 656pp.
[8]  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.)
[9]  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.
[10]  Mineter M. J., Dowers S. Parallel processing for geographical applications: A layered approach[J]. Journal of Geographical Systems, 1999, 1(1): 61-74.
[11]  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.
[12]  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.
[13]  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.)
[14]  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].
[15]  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.
[16]  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.
[17]  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.)
[18]  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.)
[19]  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.)
[20]  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.)
[21]  Vatti B. R. A Generic Solution to Polygon Clipping[J]. Communications of the ACM, 1992, 35(7): 56-63.
[22]  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].

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133