[發明專利]一種基于等高線思維的哈密頓路徑求解方法

在審

• 申請號: 202011245037.2
• 申請日: 2020-11-10
• 公開（公告）號: CN112347312A
• 公開（公告）日: 2021-02-09
• 發明（設計）人: 魏金占;朱留存;陳進;盧玉南;錢偉文;陸韋春;黃曉生
• 申請（專利權）人: 北部灣大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/909
• 代理公司: 廣西中知科創知識產權代理有限公司 45130
• 代理人: 吳震輝

本發明涉及計算機圖形學與地理信息科學領域，具體公開了一種基于等高線思維的哈密頓路徑求解方法，包括以下步驟：S1、獲取節點樣本數據；S2、構建節點樣本的外包圖形；S3、分別以每一節點為中心構建泰森多邊形，形成泰森多邊形網；S4、以邊界線為基準，搜索與邊界線鄰接的泰森多邊形；S5、搜索與泰森多邊形環鄰接的泰森多邊形；S6、重復S5中的搜索步驟，直至搜索結果覆蓋所有的泰森多邊形；S7、以其中一泰森多邊形環中的任一節點為起始點，依次連接該泰森多邊形環內的所有節點；S8、重復S7中的連接步驟，結果即為哈密頓路徑的解。本發明的一種基于等高線思維的哈密頓路徑求解方法，原理簡單，能夠有效降低處理的難度、成本和時間，提高求解效率。

技術領域

本發明涉及計算機圖形學與地理信息科學領域，尤其涉及一種基于等高線思維的哈密頓路徑求解方法。

背景技術

哈密頓路徑問題求解方法是數學與計算機圖形學的研究熱點，在物流、旅游、軍事等領域具有巨大應用潛力。但傳統的哈密頓路徑問題的解決方法多從圖形學及數學角度進行，效率和適用范圍受到很大限制，在哈密頓路徑問題求解時樣本數據達到一定量后，計算機和傳統算法將無能為力。

哈密頓路徑問題求解方法屬于必經結點的路徑搜索問題，鑒于問題求解的特殊性，如必經結點的先后優化組合、空間相對位置等未作考慮，因此鮮有學者將傳統的空間路徑搜索方法用于哈密頓路徑求解領域以降低處理的難度、成本和時間。

發明內容

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

為了實現上述目的，本發明采用的技術方案為：一種基于等高線思維的哈密頓路徑求解方法，包括以下步驟：

S1、獲取節點樣本數據；

S2、構建節點樣本的外包圖形，以將所有節點覆蓋在外包圖形中；

S3、分別以每一節點為中心構建泰森多邊形，形成泰森多邊形網，并將外包圖形的邊線作為泰森多邊形網的邊界線；

S4、以邊界線為基準，搜索與邊界線鄰接的泰森多邊形，并將搜索結果合并得到泰森多邊形環；

S5、搜索與泰森多邊形環鄰接的泰森多邊形，并將搜索結果合并得到新的泰森多邊形環；

S6、重復S5中的搜索步驟，直至搜索結果覆蓋所有的泰森多邊形，以得到若干泰森多邊形環；

S7、以其中一泰森多邊形環中任一節點為起始點，依次連接該泰森多邊形環內的所有節點，并將最后一個連接的節點與相鄰的另一泰森多邊形環內的節點相連；

S8、重復S7中的連接步驟，直至將所有泰森多邊形環內的節點依次連接，以及相鄰的泰森多邊形環連接，結果即為哈密頓路徑的解。

優選的，所述外包圖形為矩形或者圓形。

優選的，所述外包圖形大于最小外包圖形，以使得所有的節點樣本未落在外包圖形的邊線上。

優選的，所述步驟S7中，以最外圍的泰森多邊形環中的任一節點作為起始點。

優選的，所述步驟S7中，同一泰森多邊形環中的節點在連接時，依次連接相鄰的節點。

優選的，所述步驟S7中，若其中一節點與多個節點相鄰，將所述其中一節點與任一相鄰的節點進行連接。

優選的，所述步驟S7中，其中一泰森多邊形環的最后一個連接的節點與相鄰的另一多邊形環中相鄰的任一節點連接。

優選的，上述任一的求解方法用于平面求解。