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

?

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

范俊甫1,2

1. 山東理工大學(xué)建筑工程學(xué)院，山東 淄博 255049； 2. 中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 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

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

(1) 矢量多邊形疊加及其并行化的關(guān)鍵問(wèn)題理論總結(jié)。在對(duì)矢量多邊形拓?fù)浏B加與非拓?fù)浏B加所需處理的關(guān)鍵問(wèn)題、算法流程進(jìn)行系統(tǒng)總結(jié)的基礎(chǔ)上，明確了研究開(kāi)展的前提，確定了數(shù)據(jù)分解算法、任務(wù)映射方法、多邊形裁剪算法等多個(gè)研究重點(diǎn)。

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

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

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

(5) 開(kāi)發(fā)實(shí)現(xiàn)了面向多種并行計(jì)算環(huán)境的、功能完備的開(kāi)放式多邊形疊加分析工具集，并完成了在多平臺(tái)并行計(jì)算環(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

作者簡(jiǎn)介：范俊甫(1985—)，男，講師，2014年7月畢業(yè)于中國(guó)科學(xué)院地理科學(xué)與資源研究所，獲理學(xué)博士學(xué)位(指導(dǎo)教師：周成虎院士、馬廷副研究員)，研究方向?yàn)椴⑿锌臻g分析算法。

收稿日期：2015-09-24

基金項(xiàng)目：國(guó)家自然科學(xué)基金(41501425)；山東理工大學(xué)博士科研基金(4041-414039)；資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金。

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

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：D

引文格式：范俊甫. 并行化矢量多邊形疊加算法研究[J].測(cè)繪學(xué)報(bào)，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.