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

有效

• 申請號: 200910214551.7
• 申請日: 2009-12-31
• 公開（公告）號: CN101923552A
• 公開（公告）日: 2010-12-22
• 發明（設計）人: 李巖;林智源
• 申請（專利權）人: 華南師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

技術領域

本發明涉及地理信息系統空間分析中矢量地圖間的分析方法，特別是一種多邊形矢量圖層快速疊合方法。

背景技術

空間分析是地理信息系統(GIS)創建的初衷，而疊合分析是其重要的分析方法之一，特別是矢量圖層間的疊合操作是最老和最困難的問題之一。盡管，Chrisman?et?al.發表了第一個方法，被稱為WHIRLPOOL(Dutton?1979)，但由于算法復雜度高，非常難以達到可運行的程度。人們始終面臨“如何針對點、線、面和復雜空間幾何對象的疊合計算，尤其是‘面’對象或多邊形圖層間疊合操作時，如何減少算法的復雜性，解決特殊情形(特殊面中出現孔洞)和保持圖形重建后的精度三大難題。

例如：計算某行政區內各類土地利用類型的分布狀況與數量的疊合分析計算，即：進行兩矢量圖層間多邊形的交、并、差和包含的計算，統計出各個行政區多邊形內的土地利用類型分布和數量。計算過程中，不僅需對兩矢量圖層多邊形邊界求交點，重建具有多重屬性的新多邊形，并保證疊合分析的幾何精度；還需統計分析多邊形范圍內的屬性特征；另外，特別需處理隨之產生的包含關系或出現“孔洞”現象。

其中，圖層中矢量圖形的疊合分析，它通過對各區域兩圖層中多邊形圖形求交點和多重屬性的搜索、判別，確定是否產生新多邊形，或是否需對剩余多邊形進行重新分類或分級，進行新多邊形重建，構成新的矢量圖層；然后，為圖層內容進行統計疊合分析，對疊合分析結果中所形成的新多邊形，進行屬性的重新計算和分配。

在矢量圖層疊合分析過程中，多邊形疊合的順序及兩圖層中多邊形求交、并、差是最核心的過程，其中：正確、適宜的多邊形疊合計算，可對兩圖層的疊合分析起到提高效率的作用。在國外，一個著名的算法是由Cyrus和Beck提出，它通過判斷直線段的方向矢量與多邊形邊法矢量的點積是否大于0，而將所有交點分為上、下兩組；然后，分別取上組中的最小交點和下組中的最大交點，作為線段可見部分的端點。但是，Cyrus-Beck算法只適用于凸多邊形的求交，對于凹多邊形則沒有意義。與此同時，只適用于凸多邊形的求交、并、差的算法還有Shamos算法和O’Rourke算法。近年來，M.Rivero也提出一種能處理任意簡單多邊形的算法，但其理論復雜，致使其時間復雜度達到0((n+k)(m+k))，其中：n，m分別是兩輸入圖層多邊形的邊數，k則是它們的交點數。在國內，也有不少學者從事該領域的研究，但大多數采用對兩圖層多邊形的邊進行兩兩求交，效率明顯很低；另外，有些算法甚至還需開二維數組，這對于GIS空間分析所面對的大規模數據集來說，明顯不可能滿足應用需求。其中，謝忠、薛勝等學者提出對兩圖層多邊形進行兩重循環的疊合分析，很明顯不僅會出現重復多邊形，導致錯誤，而且運行效率也必然很低。在眾多研究中，僅劉勇奎、楊維芳、杜爽等人的算法可求多邊形的交、并、差，它是基于第一個多邊形的所有邊，依次對第二個多邊形進行線裁剪操作，以求出所有邊的交點。雖然，它對于線裁剪提出了一種新的算法流程“錯切變換法”，提高了求交點的效率，但對于第一個多邊形的n條邊均對第二個多邊形的m個頂點依次進行置換操作，僅對于多邊形的線段求交，其復雜度已為O(n×m)。而且，該算法對于求多邊形的交、并、差，需分別重新構造多邊形鏈，造成重復工作，降低了計算效率。同時，它對多邊形的邊重合或者在頂點處相交等特殊情況的處理是采用偏移頂點操作，不僅降低了操作效率，還會損失圖形的精度，這對精度要求高的矢量圖層間的空間分析存在致命缺陷。

綜上所述，現有技術中，并沒有一種適用于矢量圖層間任意多邊形求交、并、差和包含的高效方法和屬性配置方法。在矢量圖層間的疊合操作和分析中的三大難點問題并沒有實質性的突破。因此，提出一種適用于矢量圖層間任意多邊形求交、并、差和包含的高效方法和屬性配置方法，對增強GIS空間分析功能的性能具有重要意義和實用價值。

發明內容

本發明的目的在于提供一種多邊形矢量圖層快速疊合方法，以解決現有技術的不足，提供一種既適用于處理任意多邊形的求交、并、差和包含關系，又能高效處理兩矢量圖層疊合分析的方法。

本發明采用的技術方案如下：

一種矢量圖層多邊形快速疊合分析方法，它包括以下步驟：

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