[發(fā)明專利]一種多邊形矢量圖層快速疊合方法

有效

• 申請?zhí)枺?/td>: 200910214551.7
• 申請日: 2009-12-31
• 公開（公告）號: CN101923552A
• 公開（公告）日: 2010-12-22
• 發(fā)明（設(shè)計）人: 李巖;林智源
• 申請（專利權(quán)）人: 華南師范大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 林麗明

1.一種多邊形矢量圖層快速疊合方法，其特征在于所述方法包括：

A)將兩矢量圖層多邊形(每個多邊形必須是封閉面狀對象)分別存入兩個鏈表G1和G2中，并為各圖層多邊形分配唯一ID號，規(guī)則為：第i個圖層第j個多邊形ID為i_j；同時，初始化一個結(jié)果圖層R為空；

B)分別從G1和G2中讀取多邊形，將從G1獲得的每個多邊形P_i與所有G2中的多邊形Q_i進(jìn)行分析判斷；直至G1為空，跳到第H步；否則將不斷從G1中取得多邊形P，并從G1中刪除；

C)如果滿足下述表達(dá)式：

(P_外包).x₂＜(Q_i外包).x₁‖(P_外包).y₂＜(Q_i外包).y₁‖(P_外包).x₁＞(Q_i外包).x₂‖(P_外包).y₁＞(Q_i外包).y₂，

則將該多邊形Q_i存入多邊形集合M中，否則存入多邊形集合N中；

D)進(jìn)行多邊形求交，只要多邊形集合N不為空，則采用基于事件點組的平面掃描線算法對P與N進(jìn)行掃描線求交點；如果N為空，則將P直接存進(jìn)結(jié)果圖層R中，跳回第B步；

(基于事件點組的平面掃描線算法需要保護(hù))

E)然后，開始進(jìn)行多邊形重建：先對步驟D中基于事件點組的平面掃描線算法所求得的多邊形交點進(jìn)行原線段截斷，產(chǎn)生新的節(jié)點和連通新線段的處理；并且，對連通后節(jié)點所關(guān)聯(lián)的邊進(jìn)行夾角排序，按同一節(jié)點邊的排列順序生成邊信息鏈表；

F)再根據(jù)最小夾角原則，采用深度搜索，按逆時針方式求出所有合法多邊形，包括P與N的交P∩N、P與N的差P-N、N與P的差N-P，并為每個新的多邊形重新分配ID；

G)將P∩N與P-N存入結(jié)果圖層R中，將N-P存進(jìn)集合M中，更新第二個圖層G2的圖形數(shù)據(jù)，用M覆蓋G2，即：使得G2＝M，返回步驟B；

H)兩圖層所有多邊形已經(jīng)疊合完畢后，則結(jié)果多邊形已經(jīng)全部更新，并存于結(jié)果圖層R中，接著，對R中所有多邊形圖形數(shù)據(jù)進(jìn)行屬性統(tǒng)計計算和配置；

I)返回結(jié)果圖層R，結(jié)束運算。

2.根據(jù)權(quán)利要求1所述的多邊形矢量圖層快速疊合方法，其特征在于：在步驟C中，根據(jù)外包矩形對第二個圖層G2中多邊形進(jìn)行分類，快速去除與第一個圖層多邊形P不可能相交的多邊形。

3.根據(jù)權(quán)利要求1所述的多邊形矢量圖層快速疊合方法，其特征在于：在步驟D中，運用基于事件點組的掃描線算法求多個多邊形的交點，采用平衡二叉樹及堆設(shè)計存儲事件點組。

4.根據(jù)權(quán)利要求1所述的多邊形矢量圖層快速疊合方法，其特征在于：在步驟E中，對同一頂點所關(guān)聯(lián)的邊進(jìn)行與橫軸夾角排序。

5.根據(jù)權(quán)利要求1所述的多邊形矢量圖層快速疊合方法，其特征在于：在步驟E中，按頂點順序新生成的邊信息鏈表包含有原多邊形P與N集合的邊方向信息，逆時針為正方向，順時針為負(fù)方向。

6.根據(jù)權(quán)利要求1所述的多邊形矢量圖層快速疊合方法，其特征在于：在步驟F中，根據(jù)最終生成的多邊形的夾角和，判斷搜索順序是逆時針還是順時針，如果夾角和為-2π則為逆時針多邊形，屬于交或者差；如果是2π，則為順時針多邊形，屬于多邊形的并。

7.根據(jù)權(quán)利要求1所述的多邊形矢量圖層快速疊合方法，其特征在于：在步驟F中，逆時針?biāo)阉鞯降亩噙呅危鶕?jù)所構(gòu)成的邊的方向判斷屬于交還是差，如果有邊屬于P的正邊，則屬于P；如果有邊屬于P的負(fù)邊，則不屬于P；如果有邊屬于N的正邊，則屬于N；如果有邊屬于N的負(fù)邊，則不屬于N；從而可以得出究竟屬于P∩N、P-N還是N-P。