[發明專利]一種基于TIN三角形網絡的哈密頓路徑快速求解方法

在審

• 申請號: 202010942940.8
• 申請日: 2020-09-09
• 公開（公告）號: CN112070167A
• 公開（公告）日: 2020-12-11
• 發明（設計）人: 陳小祥;魏金占;汪維錄;李嘉誠;溫洲冰;張文暉
• 申請（專利權）人: 深圳市城市規劃設計研究院有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 廣西中知科創知識產權代理有限公司 45130
• 代理人: 吳震輝

本發明涉及計算機圖形學與地理信息科學領域，具體公開了一種基于TIN三角形網絡的哈密頓路徑快速求解方法，包括以下步驟：S1、獲取節點樣本數據；S2、根據節點樣本數據構建泰森多邊形和TIN三角形網絡；S3、提取TIN三角形網絡的最外圍邊線作為起始邊界，搜索與起始邊界存在共點的三角形，合并搜索結果得到一環形，再搜索與環形內邊界存在共點的三角形，重復上述搜索過程，直至搜索完整個TIN三角形網絡；S4、判斷所有節點度是否為2；S5、將多個多邊形合并成一個多邊形，合并后的多邊形即為哈密頓路徑的解。本發明的一種基于TIN三角形網絡的哈密頓路徑快速求解方法，原理簡單，能夠有效降低處理的難度、成本和時間，提高求解效率。

技術領域

本發明涉及計算機圖形學與地理信息科學領域，尤其涉及一種基于TIN三角形網絡的哈密頓路徑快速求解方法。

背景技術

哈密頓路徑問題求解屬于NP問題，人類至今都沒有找到有效的多項式問題解。但該問題除了是數學與計算機圖形學的研究熱點，也是人類認知世界至今難以突破的思維難題。該技術在與空間相關的各個領域、包括虛擬計算機空間等領域具有巨大應用潛力，但傳統的哈密頓路徑問題方法多從數學角度出發尋求求解思路，效率和適用范圍受到很大限制，在哈密頓環求解時樣本數據達到一定量時，計算機和傳統算法將無能為力，一個簡單的幾百節點的哈密頓路徑問題都可能需要現代計算技術數百年的運算。

哈密頓路徑問題求解方法屬于必經節點的搜索問題，其特點是每個節點都只與臨近兩個節點相連，共同形成閉環。該問題是連接問題，屬于一維空間問題，而該問題的樣本在二維環境拓展，因此該問題的求解就出現了難于跨越的維度升級，傳統解決方法無能為力。

發明內容

本發明旨在至少解決上述所提及的技術問題之一，提供一種基于TIN三角形網絡的哈密頓路徑快速求解方法，原理簡單，能夠有效降低處理的難度、成本和時間，提高求解效率。

為了實現上述目的，本發明采用的技術方案為：一種基于TIN三角形網絡的哈密頓路徑快速求解方法，包括以下步驟：

S1、獲取節點樣本數據；

S2、根據節點樣本數據構建泰森多邊形和TIN三角形網絡，以將所有節點樣本數據覆蓋在所構建的泰森多邊形以及TIN三角形網絡中；

S3、提取TIN三角形網絡的最外圍邊線作為起始邊界，搜索與起始邊界存在共點的三角形，合并搜索結果得到一環形，以環形的內邊界為基準，搜索與內邊界共點的三角形，合并搜索結果得到新的環形，重復搜索與環形內邊界存在共點三角形的過程，直至搜索完整個TIN三角形網絡，提取環形的邊界得到多個多邊形；

S4、判斷所有節點度是否為2，若存在節點度不為2情況，則對節點度不為2的節點進行處理，以使得所有的節點均在唯一的多邊形上；

S5、將多個多邊形合并成一個多邊形，合并后的多邊形即為哈密頓路徑的解。

優選的，所述步驟S4中包括：S41、當節點度為0時，將該節點分別連接臨近的兩個節點，并刪除臨近的兩個節點之間的連線，保留該節點分別連接臨近的兩個節點之間的連線。

優選的，所述步驟S4中還包括：S42、當節點度大于2時，刪除連接該節點的所有連線，以使得該節點度為0，且在該節點的周圍形成偶數個斷點，通過連線連接兩個相鄰斷點，以使得斷點的節點度為2，并采用步驟S41對節點度為0的節點進行處理。

優選的，所述步驟S5中，刪除相鄰的兩個多邊形中任意相鄰的兩個節點之間的連線，以使得兩個多邊形分別形成兩個斷點，將其中一個多邊形的兩個斷點分別與另一個多邊形的兩個斷點通過連線對應連接，以將相鄰兩個多邊形的合并成一個多邊形，重復上述的合并步驟，從而將所有的多邊形合并為一個多邊形。

優選的，兩相鄰多邊形中刪除連線的四個節點為最臨近的四個節點。