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

在審

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

1.柵格化并行疊加處理方法，應用于具有多核心處理器的圖形處理設備，其特征在于，所述方法包括：

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

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

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

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

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

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

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

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

2.如權利要求1所述的矢量多邊形柵格化并行疊加處理方法，其特征在于，所述采用環繞數法，在所述多核心處理器上進行離散網格特征點與目標多邊形和操作多邊形的包含關系進行并行計算，的步驟包括：

定義環繞數計數器；

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

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

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

將環作為一條閉合的路徑，構成環的頂點先后次序決定了構成環的每條邊的方向，對于閉合路徑的內部區域，從特征點做水平射線，從閉合路徑的起點開始行進，記錄每條水平射線與特征點相交的環的邊，若邊自左向右穿過該水平射線，則環繞數減1，若邊自右向左穿過該水平射線，則環繞數加1；

按照非零環繞數規則，若最終環繞計數器值為0，則判定特征點在環外部，若最終環繞計數器值不為0，則判定特征點在環內部；

遍歷完每一個環后，若特征點在矢量多邊形的任意一個外環內部且在該外環所包圍的所有內環的外部，則判定該特征點在矢量多邊形內。

3.如權利要求1所述的矢量多邊形柵格化并行疊加處理方法，其特征在于，根據離散網格特征點與所述目標多邊形和操作多邊形的包含關系進行矩陣元素值填充，的步驟包括：

判斷特征點是否同時位于目標多邊形和操作多邊形內部；

如果同時位于目標多邊形和操作多邊形內部，則將該離散網格對應的矩陣元素賦值為3；

如果特征點位于目標多邊形內部，但同時位于操作多邊形外部，將其對應的矩陣元素賦值為1；

如果特征點位于目標多邊形外部，但同時位于操作多邊形內部，將其對應的矩陣元素賦值為2；

如果特征點同時位于目標多邊形和操作多邊形的外部，則將其對應的矩陣元素賦值為0。