[發明專利]一種封閉多邊形內三角網深度搜索提取中心線算法

在審

• 申請號: 202210079408.7
• 申請日: 2022-01-24
• 公開（公告）號: CN114972624A
• 公開（公告）日: 2022-08-30
• 發明（設計）人: 黃磊;吳文軍;王軍軍;肖涵予;劉禮衡;龍城仕;寇媛;何潔;羅海玲;劉新定
• 申請（專利權）人: 湖南省第一測繪院
• 主分類號: G06T17/00
• 分類號: G06T17/00;G06T17/05;G06T17/20
• 代理公司: 深圳市創富知識產權代理有限公司 44367
• 代理人: 汪學品

1.一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于，包括以下步驟：

（1）構建河流面封閉多邊形三角形：提取河流封閉多邊形數據，根據封閉多邊形邊上的節點產生一系列相互連接但不重合的三角形，三角形由多邊形頂點及多邊形邊線組成，每個三角形的外切圓內，不包含其它點；

（2）提取多邊形內部三角形：根據封閉多邊形范圍，依次剔除封閉多邊形外部的三角形；

（3）將三角形中點連接成中心線：選擇封閉多邊形內部的三角形，提取三角形邊線的中點，將中點連接成多段線；

（4）判斷連接成多段線的數量: 當連接成為多段線數量=1時，則此多段線為封閉多邊形中心線；當連接成為多段線的數量1時，需下一步處理；

（5）將連接的多條中心線在節點與結點相交處進行打斷處理；

（6）將多條中心線構建二叉樹；

（7）使用二叉樹深度搜索算法，找出中心線：使用二叉樹深度搜索算法，查找二叉樹最長路徑并對線段進行記錄，將多條線段連接成為最終中心線。

2.根據權利要求1所述的一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于：步驟（2）中僅選擇多邊形封閉面內三角形，外部三角形則剔除，外部三角形無法查找多邊形中心線。

3.根據權利要求1所述的一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于：步驟（3）中循環選取封閉多邊形面內各個三角形，查找三角形各條邊線是否與封閉多邊形邊線重合；當三角形邊線與封閉多邊形邊線不重合時，則求出邊線的中點，并將中點連接成為多段線，最終完成面內所有三角形中點連接多段線操作。

4.根據權利要求1所述的一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于：步驟（4）中當封閉多邊形面內多段線僅有一條多段線時，則此條多段線為封閉多邊形中心線；當面內有多條多段線時，則進行下一步操作。

5.根據權利要求1所述的一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于：步驟（5）中如果封閉多邊形面內存在多條多段線，當一條多段線結點與另一條多段線存在相交點，則在此相交點處打斷多段線。

6.根據權利要求1所述的一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于：步驟（6）中選取封閉多邊形面內打斷的多段線，建立所有多段線對象，對象包含多段線的長度、順序號、起始點、尾結點；抽取多段線中的其中一條多段線，作為根結點，此多段線起始點或者尾結點中存在一個結點不與其它多段線結點重合；隨后依次查找與根結點起始點或者尾結點重合的下一條多段線，作為根結點的子結點，查找出根結點所有子結點，再次以子結點作為根結點，繼續查找此根結點下子結點，直至所有多段線全部查詢完畢，則二叉樹構建完成。

7.根據權利要求1所述的一種封閉多邊形內三角網深度搜索提取中心線算法，其特征在于：步驟（7）中從二叉樹中篩選出無子結點的所有結點以及根結點，通過篩選的所有結點，查找篩選結點間的距離，并查找出結點間需通過的結點，依次存儲在數組中，最終查找出最長距離的結點；根據結點的順序號依次選擇多段線并進行連接，形成封閉多邊形中心線。