[發(fā)明專利]一種包含多個洞的多邊形區(qū)域快速橋接方法

無效

• 申請?zhí)枺?/td>: 201410064160.2
• 申請日: 2014-02-25
• 公開（公告）號: CN103817938A
• 公開（公告）日: 2014-05-28
• 發(fā)明（設計）人: 傅建中;林志偉;賀永;沈洪垚;甘文峰
• 申請（專利權）人: 浙江大學
• 主分類號: B29C67/00
• 分類號: B29C67/00;G06T11/20
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

1.一種包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，包括：

步驟1、輸入一個表示平面區(qū)域的多邊形數組，其中第一個多邊形表示區(qū)域的外輪廓，定義為外輪廓多邊形，其余多邊形表示區(qū)域內輪廓，即各個洞的輪廓，定義為內輪廓多邊形；

步驟2、復制并存儲上述多邊形各頂點坐標，同時記錄每個頂點在對應多邊形上的序號以及該多邊形在多邊形數組中的序號，得到一組平面點云；

步驟3、對上述平面點云進行Delaunay三角化處理，得到一個平面三角形數組；

步驟4、刪除上述平面三角形數組中無用的三角形，這些三角形包括三個頂點都在同一多邊形上或三個頂點分別在三個多邊形上的三角形；

步驟5、在每個三角形內建立初始橋以連接對應的兩個多邊形，得到一個初始橋數組；

步驟6、在初始橋數組中尋找若干座有用橋并用這些橋將所有內輪廓多邊形橋接至外輪廓多邊形；

步驟7、輸出一個包含了所有內輪廓多邊形和外輪廓多邊形的統(tǒng)一多邊形。

2.根據權利要求1所述的包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，步驟3中，所述對平面點云進行Delaunay三角化處理之前，需隨機打亂平面點云中的點序。

3.根據權利要求1所述的包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，步驟5中，在每個三角形內建立初始橋的過程如下：設定A、B、C為任一三角形的三個頂點，該三角形連接兩個多邊形，其中頂點A在第一個多邊形上，頂點B、C在第二個多邊形上，則連接第一個多邊形、二個多邊形的橋的其中一個端點E₁在頂點A上，另外一個端點E₂在頂點B或C上。

4.根據權利要求3所述的包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，所述端點E₂取B、C中使得E₁E₂長度較小的點上。

5.根據權利要求1所述的包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，步驟6中，具體過程為：

步驟6.1、搜索初始橋數組中所有一端和外輪廓多邊形相連的橋，從中找出最短的那座橋，記為橋b，橋b的兩個端點分別為E₁′和E₂′、，其中E₁′為橋b在外輪廓多邊形上的端點，E₂′為橋b的另一個端點；

步驟6.2、找到和橋b另一端E₂′相連的那個內輪廓多邊形；

步驟6.3、復制提取橋b，并刪除初始橋數組中所有和上述內輪廓多邊形以及外輪廓多邊形相連的橋；

步驟6.4、將該內輪廓多邊形以橋b橋接到外輪廓多邊形上，即內輪廓多邊形成為外輪廓多邊形的一部分；

步驟6.5、判斷是否所有內輪廓多邊形都已被橋接到外輪廓多邊形上，是，則退出；否則，更新初始橋數組中內輪廓多邊形信息和外輪廓多邊形信息，跳至步驟6.1。

6.根據權利要求5所述的包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，所述步驟6.4中將內輪廓多邊形橋接至外輪廓多邊形的步驟如下：

步驟6.4.1、找出外輪廓多邊形上和橋b的E₁′端點連接的那個點，記為P₁；

步驟6.4.2、外輪廓多邊形在P₁處斷開，通過橋b連接進入內輪廓多邊形，進入點為內輪廓多邊行上和橋b的E₂′端點連接的那個點，記為P₂；

步驟6.4.3、從P₂開始，以順時針方向遍歷復制添加內輪廓多邊上的所有點至外輪廓多邊形上；

步驟6.4.4、從P₂點出來，連接至P₁，得到封閉多邊形。

7.根據權利要求1所述的包含多個洞的多邊形區(qū)域快速橋接方法，其特征在于，所述步驟1中輸入的多邊形為簡單多邊形，即沒有自相交的多邊形。