一种曲线分割与化简的并行算法

发布时间：2021-08-01 17:18

　　针对现有曲线分割与化简算法多为串行算法,无法充分利用多核心处理器的并行计算能力以提升计算效率这一问题,该文提出了一种曲线分割与化简的并行算法。该算法使用Numba库,将曲线分割与化简步骤中,例如弯曲面积计算、判断线段是否相交等具有并行性的任务,加以分割并分配到多核处理器的每一个核心上,以充分利用多核处理器并行计算的优势,提高算法的性能。实验证明,曲线分割与化简的并行算法,可以有效地提高数据处理的效率,降低分割与化简曲线的时间成本。 

【文章来源】：测绘科学. 2020,45(01)北大核心CSCD

【文章页数】：5 页

【部分图文】：

算法流程图

通过分析曲线分割与化简的串行算法可知，其流程中存在两个具有并行性的任务：(1)在曲线分割阶段，本文采用的斜拉式曲线划分方法，通过假设弯曲的轴线线段（即首尾点组成的线段P1Pn）与其内部相邻点组成的线段（P1P2、P2P3、…、Pn-1Pn）是否相交，判断该弯曲是否为最终结果弯曲，任意两线段间是否相交的向量运算以及判断过程，其执行顺序和结果互不影响，可以同时执行，见图3(a);(2)在计算弯曲面积并将其与阈值进行比较时，每个弯曲的计算和比较，以及比较后是否需要对该弯曲进行删除的操作都具有独立性，也可以由处理器核心分工完成，见图3(b）。将上述任务实现并行化后，按相应的顺序执行，即可完成算法从串行到并行的转化。3 实验结果与分析

化简结果

【参考文献】：
期刊论文
[1]保持移动速度特征的轨迹线化简方法[J]. 杨敏,陈媛媛,金澄,程前.  测绘学报. 2017(12)
[2]顾及空间邻接关系的多级河流线状矢量数据并行压缩算法[J]. 朱晓波,周廷刚,曾波,沈敬伟,潘勇卓,丁彤彤.  西南大学学报(自然科学版). 2017(02)
[3]曲线弯曲的多叉树表达[J]. 操震洲,李满春,程亮.  测绘学报. 2013(04)
[4]基于MapReduce的多机并行DP算法与实验分析[J]. 张栋海,黄丽娜,刘晖,唐健.  地球信息科学学报. 2013(01)
[5]利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素[J]. 马劲松,沈婕,徐寿成.  武汉大学学报(信息科学版). 2011(12)
[6]地图信息自动综合基本问题研究[J]. 毋河海.  武汉测绘科技大学学报. 2000(05)

硕士论文
[1]基于CUDA的D-P曲线压缩算法并行实现[D]. 刘婷.大连理工大学 2015



本文编号：3315926