[發(fā)明專利]基于掃描線法的多邊形柵格化并行轉(zhuǎn)換方法

有效

• 申請?zhí)枺?/td>: 201110442351.4
• 申請日: 2011-12-27
• 公開（公告）號: CN102542035A
• 公開（公告）日: 2012-07-04
• 發(fā)明（設(shè)計）人: 陳振杰;張帥;李飛雪;王亞飛;李滿春;蒲英霞;王加勝;程亮
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京知識律師事務(wù)所 32207
• 代理人: 蔣海軍

技術(shù)領(lǐng)域

本發(fā)明涉及一種矢量數(shù)據(jù)的柵格化方法，特別是涉及基于掃描線法的多邊形柵格化并行轉(zhuǎn)換方法。

背景技術(shù)

地理信息系統(tǒng)(?GIS?)是以空間數(shù)據(jù)為基礎(chǔ)，獲取、表達、處理、管理、分析和顯示空間數(shù)據(jù)并為地理研究和地理決策服務(wù)的計算機服務(wù)系統(tǒng)。空間數(shù)據(jù)通常有矢量數(shù)據(jù)(Vector?Data)和柵格數(shù)據(jù)(Raster?Data)兩種形式。矢量數(shù)據(jù)是通過記錄坐標(biāo)的方式，表示點、線、多邊形等地理實體，自然地理實體的位置是用其在坐標(biāo)參考系中的空間位置來定義的，坐標(biāo)空間設(shè)為連續(xù)，其特點是定位明顯，屬性隱含。而柵格數(shù)據(jù)又稱為網(wǎng)格數(shù)據(jù)(grid?cell)，即將平面劃分為m×n個像元（正方形小方格），每個像元由行列號唯一地確定其所在平面位置，給像元賦予屬性以表達該覆蓋的自然地理實體的類型，其最明顯的特點是屬性明顯，定位隱含。

在GIS空間分析時，由于柵格形式的GIS?數(shù)據(jù)非常適合諸如空間疊加、空間相關(guān)和空間模擬等空間分析，因而通常需要把矢量數(shù)據(jù)轉(zhuǎn)化成柵格數(shù)據(jù)。矢量數(shù)據(jù)柵格化被廣泛認(rèn)為是地理信息系統(tǒng)中的基礎(chǔ)問題。矢量數(shù)據(jù)柵格化包括點的柵格化、線的柵格化以及多邊形的柵格化。點和線的柵格化方法目前已經(jīng)比較成熟，方法也趨于固定。多邊形的柵格化就是對矢量數(shù)據(jù)的面狀圖斑根據(jù)給定的柵格化像元的大小離散化為像元的集合，像元值為矢量面狀圖斑所具有的某種屬性值。長期以來以矢量多邊形柵格化的研究最為熱點。多邊形的柵格化已有很多算法，傳統(tǒng)的串行算法如內(nèi)部點擴散法、復(fù)數(shù)積分算法、射線法、掃描法和邊界代數(shù)法等，這些方法各有優(yōu)缺點，目前還沒有一種標(biāo)準(zhǔn)統(tǒng)一的最優(yōu)算法。隨著計算機的快速發(fā)展，又產(chǎn)生了許多新方法，比如：2004年，王建等在《地理與地理信息科學(xué)》20卷第3期中發(fā)表“矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換的一種改進算法”一文，總結(jié)和分析了多邊形柵格化的傳統(tǒng)算法與新方法，提出了一種改進的折線邊界跟蹤方法，保證了多邊形填充的精度；2005年，章孝燦等在《計算機輔助設(shè)計與圖形學(xué)學(xué)報》17卷第6期中發(fā)表“面狀矢量拓?fù)鋽?shù)據(jù)快速柵格化算法”一文，提出了一種快速柵格化算法—差分邊界標(biāo)志與累加掃描算法，2009年，武廣臣等在《測繪科學(xué)》43卷第1期中發(fā)表“矢量數(shù)據(jù)柵格化的一種有效方法—環(huán)繞數(shù)法”一文，提出了一種基于計算幾何轉(zhuǎn)角理論的環(huán)繞數(shù)法，著重處理了自相交多邊形的柵格化問題；2010年，李青元等在《武漢大學(xué)學(xué)報?信息科學(xué)版》35卷第8期中發(fā)表“基于繪制—檢出的矢量數(shù)據(jù)柵格化方法研究”一文，探討了基于繪制—檢出的矢量數(shù)據(jù)柵格化方法。然而研究的重點都是圍繞改進串行算法展開的，對于海量多邊形的柵格化效率的提升相當(dāng)有限。

隨著對地觀測技術(shù)的長足發(fā)展，海量柵格數(shù)據(jù)需求迅速激增，數(shù)據(jù)量為T級的柵格數(shù)據(jù)普遍存在（1TB=1024GB）。海量矢量數(shù)據(jù)柵格化呈現(xiàn)出計算高度密集的特點，耗時巨大。現(xiàn)有的矢量數(shù)據(jù)柵格化串行算法模式和傳統(tǒng)的硬件平臺，已經(jīng)無法滿足海量地理數(shù)據(jù)處理的需求。基于并行計算集群與多核處理器的新型硬件架構(gòu)的逐漸普及，為受制于計算性能而難以展開的地理數(shù)據(jù)轉(zhuǎn)換提供了契機。本發(fā)明充分利用現(xiàn)有的高性能計算機和并行處理技術(shù)，基于數(shù)據(jù)并行策略采用對等式的并行程序設(shè)計模式，提出了一種基于矢量多邊形掃描線的數(shù)據(jù)并行方法，有效地解決了海量的矢量數(shù)據(jù)柵格化的問題。

發(fā)明內(nèi)容

1.發(fā)明要解決的技術(shù)問題

針對如上所述，從數(shù)據(jù)需求方面說，矢量數(shù)據(jù)向柵格數(shù)據(jù)的轉(zhuǎn)換是GIS一直研究的基礎(chǔ)問題；從軟硬件上來說，逐漸普及的并行計算集群與多核處理器的新型硬件架構(gòu)需要得到有效利用；最重要的從效率上來說，海量的矢量數(shù)據(jù)的柵格化運行時間過長、效率過低的問題，本發(fā)明提供了基于掃描線法的多邊形柵格化并行轉(zhuǎn)換方法，該方法采用數(shù)據(jù)并行策略，即將待處理的矢量多邊形按進程數(shù)進行劃分，然后分發(fā)給各個進程，每個進程同時進行多邊形的柵格化。這樣數(shù)據(jù)劃分策略是基于目標(biāo)柵格數(shù)據(jù)的邏輯劃分，可以有效完成大數(shù)據(jù)量的矢量多邊形的柵格化，且不必考慮生成的柵格數(shù)據(jù)的拼接問題，取得了良好的柵格化效果和較高的效率，滿足海量的矢量數(shù)據(jù)的柵格化要求。

2.技術(shù)方案

發(fā)明原理：一般來說，數(shù)據(jù)并行的實現(xiàn)過程是主進程將待處理的數(shù)據(jù)分派到其他若干子進程分別處理，再由主進程負(fù)責(zé)收集不同子進程的數(shù)據(jù)處理結(jié)果并進行組合，達到多處理器共同完成某一個任務(wù)的目的。本發(fā)明中利用柵格數(shù)據(jù)行列規(guī)整的特征，先由一個進程生成一個像素值初始化為0的柵格數(shù)據(jù)集，接著按給定的進程數(shù)劃分該柵格數(shù)據(jù)，得到與進程數(shù)相等的柵格數(shù)據(jù)分塊。然后查詢柵格分塊范圍內(nèi)的多邊形（包括與該柵格分塊相交的多邊形）并提取出來分發(fā)給各個進程，每個進程進行相同的多邊形柵格化的操作。