[發明專利]矢量多邊形柵格化并行疊加處理裝置及方法

在審

• 申請號: 201710223338.7
• 申請日: 2017-04-07
• 公開（公告）號: CN106952324A
• 公開（公告）日: 2017-07-14
• 發明（設計）人: 范俊甫;何惠馨;胡桃英;孫廣偉;韓留生
• 申請（專利權）人: 山東理工大學
• 主分類號: G06T11/40
• 分類號: G06T11/40;G06F9/38
• 代理公司: 北京權智天下知識產權代理事務所(普通合伙)11638
• 代理人: 王新愛

技術領域

本發明涉及測繪地理信息空間分析領域，具體而言，涉及一種利用共享內存多核心處理器加速的復雜矢量多邊形柵格化并行疊加處理裝置及方法。

背景技術

矢量多邊形疊加分析是測繪地理信息領域中一種基礎的底層空間分析方法，在復雜地理建模、空間信息提取、空間數據挖掘、地理信息快速可視化等領域有廣泛的應用。隨著地理信息系統應用的日益普及，空間分析方法的計算效率越來越被人們所關注。矢量多邊形并行疊加分析計算過程由復雜的算法設計和并行優化技術構成，其中疊加分析方法的計算效率和處理規模對地理信息系統軟件的成功應用至關重要，高效的算法不僅可以提高各類行業應用領域分析模型的計算效率，還能夠縮短各類上層應用系統的應急響應時間，提升工作效率。為改善現有矢量多邊形疊加分析方法的計算效率，目前采用的技術包括串行疊加分析計算過程優化、底層新型多邊形裁剪算法優化、數據組織方法優化等，上述優化方法難以在根本上克服基于矢量計算過程的多邊形疊加分析方法的計算效率隨多邊形頂點數量增加快速下降的弊端。

發明內容

鑒于以上內容，本發明實施例提供一種矢量多邊形柵格化并行疊加處理方法，應用于具有多核心處理器的圖形處理設備，其中，所述方法包括：

按照疊加操作算子對兩個矢量多邊形進行矢量疊加計算得到結果多邊形，按照疊加操作算子的計算結果分別計算所述兩個矢量多邊形的外包矩形，所述兩個矢量多邊形包括一個目標多邊形和一個操作多邊形；

按照設定的離散網格單元大小對所述兩個矢量多邊形的結果外包矩形進行空間離散化；

采用環繞數法，在所述多核心處理器上進行離散網格特征點與目標多邊形和操作多邊形的包含關系進行并行計算；

根據離散網格特征點與所述目標多邊形和操作多邊形的包含關系進行矩陣元素值填充；

采用環繞邊界追蹤算法提取疊加計算得到的結果多邊形邊界的離散網格有序序列；

提取結果多邊形邊界離散網格的中心點或頂點，構造結果多邊形整體圖斑；

將所述結果多邊形整體圖斑與采用通用多邊形裁剪工具庫對所述兩個矢量多邊形進行計算得到的結果多邊形進行對比，計算得到二者的面積誤差；及

對所述結果多邊形進行屬性賦值，輸出疊加計算結果。

本發明實施例還提供一種矢量多邊形柵格化并行疊加處理裝置，應用于具有多核心處理器的圖形處理設備，其中，所述裝置包括：

外包矩形計算模塊，用于按照疊加操作算子對兩個矢量多邊形進行矢量疊加計算得到結果多邊形，按照疊加操作算子的計算結果分別計算所述兩個矢量多邊形的外包矩形，所述兩個矢量多邊形包括一個目標多邊形和一個操作多邊形；

多邊形離散化模塊，用于按照設定的離散網格單元大小對所述兩個矢量多邊形的結果外包矩形進行空間離散化；

多核心計算模塊，用于采用環繞數法，在所述多核心處理器上進行離散網格特征點與目標多邊形和操作多邊形的包含關系進行并行計算；

矩陣填充模塊，用于根據離散網格特征點與所述目標多邊形和操作多邊形的包含關系進行矩陣元素值填充；

邊界序列提取模塊，用于采用環繞邊界追蹤算法提取疊加計算得到的結果多邊形邊界的離散網格有序序列；

圖斑構造模塊，用于提取結果多邊形邊界離散網格的中心點或頂點，構造結果多邊形整體圖斑；

圖斑誤差計算模塊，用于將所述結果多邊形整體圖斑與采用通用多邊形裁剪工具庫對所述兩個矢量多邊形進行計算得到的結果多邊形進行對比，計算得到二者的面積誤差；及

結果輸出模塊，用于對所述結果多邊形進行屬性賦值，輸出疊加計算結果。

優選地，所述采用環繞數法，在所述多核心處理器上進行離散網格特征點與目標多邊形和操作多邊形的包含關系進行并行計算，具體包括：

定義環繞數計數器；

將矢量多邊形分解為一組環，并將所有的環區分為兩種類型，即外環或內環；該矢量多邊形為所述目標多邊形或所述操作多邊形；

對每一個環進行遍歷，進行如下處理：

將環繞計數器歸0，判斷特征點是否在該環的外包矩形內，當特征點在外包矩形內時，判斷特征點是否在構成矢量多邊形的環的相鄰頂點連線上，若在連線上將特征點標記為邊界點；若特征點不在外包矩形內，記錄特征點的環繞數為0；