利用网格索引与R树的弧段求交并行算法  

Parallel algorithm for arc intersection based on grid index and R-tree

作　　者：王文杰[1,2] 唐新明[2] 史绍雨[2] 闫浩文[1] 汪汇兵[2] 

机构地区：[1]兰州交通大学数理与软件工程学院,兰州730070 [2]国家测绘地理信息局卫星测绘应用中心,北京100830

出　　处：《测绘科学》2014年第3期111-115,共5页Science of Surveying and Mapping

基　　金：国家863基金资助项目(2009AA121404)

摘　　要：本文通过对图幅进行网格化划分,建立网格索引,对弧段按网格建立R树空间索引,进一步降低了空的相交判断次数;根据网格之间一定的独立性,对不同网格内弧段进行并行化求交,并在单CPU多核计算机上利用OpenMP并行机制对算法进行了实现。分析与实验表明:改进后的新算法对较大数据量弧段求交的处理效率较高,与同类算法相比,在空间数据拓扑的建立与空间分析的应用中具有一定优势。A parallel algorithm for arc index with gridding thought. It aims at int intersection was proposed based on grid index and R-tree spatial ersectlon terseeting judgment were further decreased by p grids. According to the independency of grids, the tion. The algorithm was realized on a single-CPU grammmg rithm coul algorithms rithm wou issues of large amount spatial data. Empty times of in- artitioning map and building R-tree spatial index to algorithm parallelly processes different grids intersec- and multi-core computer based on multi-threaded pro- thought and OpenMP mechanism. The analysis and experiment showed that the improved algo- d process a large amount of intersection for arc with high precision. Compared with the similar in the applications of establishing topology and spatial analysis on spatial data, the novel algo- ld be superior.

关 键 词：弧段求交 网格索引 R树 并行算法 

分 类 号：P208[天文地球—地图制图学与地理信息工程]