發(fā)布時間：2021-08-01 17:18

　　針對現(xiàn)有曲線分割與化簡算法多為串行算法,無法充分利用多核心處理器的并行計算能力以提升計算效率這一問題,該文提出了一種曲線分割與化簡的并行算法。該算法使用Numba庫,將曲線分割與化簡步驟中,例如彎曲面積計算、判斷線段是否相交等具有并行性的任務,加以分割并分配到多核處理器的每一個核心上,以充分利用多核處理器并行計算的優(yōu)勢,提高算法的性能。實驗證明,曲線分割與化簡的并行算法,可以有效地提高數(shù)據(jù)處理的效率,降低分割與化簡曲線的時間成本。 

【文章來源】：測繪科學. 2020,45(01)北大核心CSCD

【文章頁數(shù)】：5 頁

【部分圖文】：

算法流程圖

通過分析曲線分割與化簡的串行算法可知，其流程中存在兩個具有并行性的任務：(1)在曲線分割階段，本文采用的斜拉式曲線劃分方法，通過假設(shè)彎曲的軸線線段（即首尾點組成的線段P1Pn）與其內(nèi)部相鄰點組成的線段（P1P2、P2P3、…、Pn-1Pn）是否相交，判斷該彎曲是否為最終結(jié)果彎曲，任意兩線段間是否相交的向量運算以及判斷過程，其執(zhí)行順序和結(jié)果互不影響，可以同時執(zhí)行，見圖3(a);(2)在計算彎曲面積并將其與閾值進行比較時，每個彎曲的計算和比較，以及比較后是否需要對該彎曲進行刪除的操作都具有獨立性，也可以由處理器核心分工完成，見圖3(b）。將上述任務實現(xiàn)并行化后，按相應的順序執(zhí)行，即可完成算法從串行到并行的轉(zhuǎn)化。3 實驗結(jié)果與分析

化簡結(jié)果

【參考文獻】：
期刊論文
[1]保持移動速度特征的軌跡線化簡方法[J]. 楊敏,陳媛媛,金澄,程前.  測繪學報. 2017(12)
[2]顧及空間鄰接關(guān)系的多級河流線狀矢量數(shù)據(jù)并行壓縮算法[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曲線壓縮算法并行實現(xiàn)[D]. 劉婷.大連理工大學 2015



本文編號：3315926