[發(fā)明專利]一種基于臨近矩形的哈密頓路徑快速求解方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010942911.1
• 申請(qǐng)日: 2020-09-09
• 公開(kāi)（公告）號(hào): CN112070166A
• 公開(kāi)（公告）日: 2020-12-11
• 發(fā)明（設(shè)計(jì)）人: 陳小祥;魏金占;岳雋;郜昂;徐雅莉;劉力兵
• 申請(qǐng)（專利權(quán)）人: 深圳市城市規(guī)劃設(shè)計(jì)研究院有限公司
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 廣西中知科創(chuàng)知識(shí)產(chǎn)權(quán)代理有限公司 45130
• 代理人: 吳震輝

本發(fā)明涉及計(jì)算機(jī)圖形學(xué)與地理信息科學(xué)領(lǐng)域，具體公開(kāi)了一種基于臨近矩形的哈密頓路徑快速求解方法，包括以下步驟：S1、獲取節(jié)點(diǎn)樣本數(shù)據(jù)；S2、構(gòu)建節(jié)點(diǎn)樣本的最小外包矩形；S3、測(cè)量節(jié)點(diǎn)的平均臨近距離；S4、以平均臨近距離的整數(shù)倍為基準(zhǔn)，將最小外包矩形沿橫軸或縱軸劃分成若干相等的臨近矩形；S5、將每一臨近矩形中的節(jié)點(diǎn)沿橫軸或縱軸方向依次連接，構(gòu)造成一連線；S6、依次連接相鄰臨近矩形的連線，以將所有的連線合并為一條連線，結(jié)果即為哈密頓路徑的解。本發(fā)明的一種基于臨近矩形的哈密頓路徑快速求解方法，原理簡(jiǎn)單，能夠有效降低處理的難度、成本和時(shí)間，提高求解效率。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)圖形學(xué)與地理信息科學(xué)領(lǐng)域，尤其涉及一種基于臨近矩形的哈密頓路徑快速求解方法。

背景技術(shù)

必經(jīng)結(jié)點(diǎn)下快速路徑搜索方法是當(dāng)前位置服務(wù)領(lǐng)域研究熱點(diǎn)，在物流、資源配置、軍事等領(lǐng)域具有巨大應(yīng)用潛力。但是傳統(tǒng)的必經(jīng)結(jié)點(diǎn)快速路徑搜索方法多從圖論及數(shù)學(xué)角度進(jìn)行，其搜索效率和準(zhǔn)確度都不盡人意。而且傳統(tǒng)必經(jīng)結(jié)點(diǎn)最快路徑搜索方法在樣本數(shù)據(jù)數(shù)量達(dá)到一定級(jí)別，運(yùn)算量呈幾何級(jí)增長(zhǎng)，傳統(tǒng)算法將無(wú)能為力。

必經(jīng)結(jié)點(diǎn)最快路徑搜索方法屬于障礙物環(huán)境下必經(jīng)結(jié)點(diǎn)的路徑搜索問(wèn)題，因此傳統(tǒng)的路徑搜索方法適用于必經(jīng)結(jié)點(diǎn)最快路徑搜索領(lǐng)域。但鑒于必經(jīng)結(jié)點(diǎn)最快路徑搜索方法的幾何特殊性，必經(jīng)結(jié)點(diǎn)的先后優(yōu)化組合等未作空間關(guān)系方面的深入考慮，因此當(dāng)前研究中很少學(xué)者將傳統(tǒng)空間關(guān)系用于必經(jīng)結(jié)點(diǎn)最快路徑搜索領(lǐng)域，防止運(yùn)算量向指數(shù)級(jí)擴(kuò)散，達(dá)到降低處理的難度、成本和時(shí)間的目的。

發(fā)明內(nèi)容

本發(fā)明旨在至少解決上述所提及的技術(shù)問(wèn)題之一，提供一種基于臨近矩形的哈密頓路徑快速求解方法，原理簡(jiǎn)單，能夠有效降低處理的難度、成本和時(shí)間，提高求解效率。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案為：一種基于臨近矩形的哈密頓路徑快速求解方法，包括以下步驟：

S1、獲取節(jié)點(diǎn)樣本數(shù)據(jù)；

S2、構(gòu)建節(jié)點(diǎn)樣本的最小外包矩形；

S3、測(cè)量節(jié)點(diǎn)的平均臨近距離；

S4、以平均臨近距離的整數(shù)倍為基準(zhǔn)，將最小外包矩形沿橫軸或縱軸劃分成若干相等的臨近矩形；

S5、將每一臨近矩形中的節(jié)點(diǎn)沿橫軸或縱軸方向依次連接，構(gòu)造成一連線；

S6、依次連接相鄰臨近矩形的連線，以將所有的連線合并為一條連線，結(jié)果即為哈密頓路徑的解。

優(yōu)選的，所述步驟S3中，通過(guò)構(gòu)建節(jié)點(diǎn)樣本的TIN三角形網(wǎng)，求解出節(jié)點(diǎn)的平均臨近距離。

優(yōu)選的，所述步驟S4中，沿橫軸方向?qū)⒆钚⊥獍匦蝿澐譃槿舾上嗟鹊呐R近矩形。

優(yōu)選的，所述步驟S4中，沿縱軸方向?qū)⒆钚⊥獍匦蝿澐譃槿舾上嗟鹊呐R近矩形。

優(yōu)選的，所述步驟S5中，將每一臨近矩形中的節(jié)點(diǎn)沿橫軸方向依次連接。

優(yōu)選的，所述步驟S5中，將每一臨近矩形中的節(jié)點(diǎn)沿縱軸方向依次連接。

優(yōu)選的，所述步驟S6中，選取合并后連線長(zhǎng)度短的作為哈密頓路徑的解。

優(yōu)選的，上述任一的求解方法用于平面求解