多边形间空间关系查询的异构多核架构并行算法

摘要：

目前在空间关系查询中常用的Plane Sweep算法是一种串行算法,在处理海量空间数据时效率较低,而已有的并行计算方法对于普通的计算机并不适用.本文针对这个问题,提出了一种多边形间空间关系查询的异构多核架构并行算法,该算法先利用STR树索引过滤掉不相交的多边形,然后将过滤后的多边形数据集合分解为点集合和边集合,并对其构建四叉树索引;在保证数据浮点运算精度符合要求的情况下,利用GPU强大的批量运算能力快速处理边与边的相交情况并据此逐步计算得到环间的拓扑关系,再根据环间拓扑关系计算得到多边形间的维度扩展九交模型(DE-9IM)参数值;根据DE-9IM参数值与空间关系查询条件相比对,输出查询结果.最后通过试验验证了算法的准确性与高效性.

关键词：异构多核、并行计算、拓扑关系、空间关系查询

所属期刊栏目：45

分类号：P208(一般性问题)

资助基金：国家863计划2011AA120302,2011AA120306,2012AA12A401;海洋公益性项目201105033-6;The National High-tech Research and Development Program of China 863 Program.2011AA120302,2011AA120306,2012AA12A401;The Marine Public Welfare Project201105033-6

在线出版日期：2016-05-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：119-126