?

并行化矢量多邊形疊加算法研究

范俊甫1,2

1. 山東理工大學建筑工程學院，山東 淄博 255049； 2. 中國科學院地理科學與資源研究所資源與環(huán)境信息系統(tǒng)國家重點實驗室，北京 100101

Parallel Algorithms for Polygon Overlapping

FAN Junfu1, 2

1. School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255049, China; 2. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences, Beijing 100101, China

空間數據規(guī)模的快速增長對傳統(tǒng)地學分析方法提出了更高的計算效率和處理規(guī)模要求。作為核心的空間分析算法之一，矢量多邊形疊加分析具有典型的高算法復雜性和計算密集性特征。隨著計算機硬件和軟件技術的進步，并行計算為提高多邊形疊加分析的計算效率，擴大問題處理規(guī)模提供了有效手段。研究面向新型計算架構的多邊形并行疊加分析算法對完善高性能GIS理論研究和實現(xiàn)方法，提升傳統(tǒng)地學分析算法的計算效率具有重要的理論價值和實踐意義。本論文針對多邊形非拓撲疊加算法的并行化問題，在多種高性能計算環(huán)境下解決了數據分解方法、并行任務映射方法、高效的多邊形裁剪算法等多個關鍵問題，主要研究內容包括以下幾點：

(1) 矢量多邊形疊加及其并行化的關鍵問題理論總結。在對矢量多邊形拓撲疊加與非拓撲疊加所需處理的關鍵問題、算法流程進行系統(tǒng)總結的基礎上，明確了研究開展的前提，確定了數據分解算法、任務映射方法、多邊形裁剪算法等多個研究重點。

(2) 多邊形“多對多”映射條件下的數據分解方法研究。對多邊形疊加過程中的“多對多”映射條件下的多邊形相交蔓延性問題進行了研究，分析了不同的多邊形疊加分析算法所適用的數據分解方法及之間的差異，提出了一種雙向種子索引數據劃分方法——DWSI算法；采用標記分割要素和設置期望分組大小的方法對DWSI算法進行了有效改進，解決了空間分布不均勻的要素疊加時易產生的并行失效問題；在多核并行環(huán)境下基于DWSI算法實現(xiàn)了多邊形并行疊加聯(lián)合算法，并實現(xiàn)了多種有效優(yōu)化方法。

(3) 多邊形疊加分析中的并行任務映射和算法應用研究?；赩atti算法的多邊形合并過程中的頂點累積效應是造成“滾雪球”合并模式效率低下的主要原因；采用分治法設計了多邊形集合合并的“樹狀”合并方法，規(guī)避了頂點累積效應，有效地提高了多邊形合并的計算效率；針對“多對多”映射下的集群并行任務映射問題，設計并實現(xiàn)了6種并行任務映射方法，其中采用R樹預篩選的直接合并方法是在集群環(huán)境下實現(xiàn)并行多邊形合并的有效方法；應用多邊形合并算法提出并實現(xiàn)了一種高效的并行緩沖區(qū)生成算法。

(4) 基于柵格化思想的任意多邊形裁剪算法的設計實現(xiàn)和并行應用研究。提出并實現(xiàn)了一種基于柵格化思想的任意多邊形裁剪算法——RaPC算法；分析了RaPC算法計算結果的面積誤差、形狀誤差和拓撲誤差的影響因素和變化規(guī)律；通過實驗比較了RaPC算法與Vatti算法的串行、并行計算效率差異，Vatti算法適用于小數據量疊加分析，RaPC算法在處理大數據量疊加時更有優(yōu)勢；RaPC算法的矩陣式處理模式比Vatti算法更適用于GPU并行計算，GPU加速的多邊形疊加求交算法驗證了RaPC算法對GPU并行的適用性和高效率。

(5) 開發(fā)實現(xiàn)了面向多種并行計算環(huán)境的、功能完備的開放式多邊形疊加分析工具集，并完成了在多平臺并行計算環(huán)境下的部署。

Author： FAN Junfu(1985—),male, received his doctoral degree from Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences on July 2014, majors in parallel spatial analysis algorithms.

E-mail： fanjf@lreis.ac.cn

作者簡介：范俊甫(1985—)，男，講師，2014年7月畢業(yè)于中國科學院地理科學與資源研究所，獲理學博士學位(指導教師：周成虎院士、馬廷副研究員)，研究方向為并行空間分析算法。

收稿日期：2015-09-24

基金項目：國家自然科學基金(41501425)；山東理工大學博士科研基金(4041-414039)；資源與環(huán)境信息系統(tǒng)國家重點實驗室開放基金。

文章編號：1001-1595(2016)04-0502-01

中圖分類號：P208

文獻標識碼：D

引文格式：范俊甫. 并行化矢量多邊形疊加算法研究[J].測繪學報，2016,45(4)：502. DOI:10.11947/j.AGCS.2016.20150495.

FAN Junfu.Parallel Algorithms for Polygon Overlapping[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):502. DOI:10.11947/j.AGCS.2016.20150495.