典型文献
多边形叠加Vatti算法的VCS优化方法与GPU并行化
文献摘要：
Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著.本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS(Vertex Coordinate Pre-Sorting)方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化.VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升.在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题.实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了 39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了 4.9倍.
文献关键词：
叠加分析;多边形裁剪;CUDA并行;双调排序;VCS;Vatti算法;数据结构;高性能计算;GIS
中图分类号：
作者姓名：
张志锟;范俊甫;徐少波;陈政
作者机构：
山东理工大学建筑工程学院,淄博255000;深圳大学建筑与城市规划学院,深圳518060
文献出处：
引用格式：
[1]张志锟;范俊甫;徐少波;陈政-.多边形叠加Vatti算法的VCS优化方法与GPU并行化)[J].地球信息科学学报,2022(03):437-447
A类：
Vatti,多边形裁剪,双调排序
B类：
VCS,GPU,并行化,矢量多边形,交点,二叉树,数据结构,递归计算,计算效率,顶点,算法执行,执行过程,建环,预排,Vertex,Coordinate,Pre,Sorting,细粒度,链表,外存,存储空间,查找效率,排序算法,数组,组元,并过,滤出,有效值,计算精度,CUDA,线程,CPU,加速比,叠加分析,算法效率,高性能计算
AB值：
0.31003
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
