LR可視多邊形中ESP問題的求解算法研究.pdf

1、Euclidean最短路徑(ESP)問題是計(jì)算幾何領(lǐng)域的經(jīng)典問題。本文針對(duì)LR可視多邊形中ESP問題的求解算法研究，設(shè)計(jì)出一個(gè)簡(jiǎn)單、可行的求解算法，為解決一些實(shí)際應(yīng)用問題（如巡視員問題、機(jī)器人運(yùn)動(dòng)規(guī)劃等）提供技術(shù)支持。因此，針對(duì)本問題的研究，不僅具有重要的理論意義，而且具有較大的實(shí)際應(yīng)用價(jià)值。
　　 本文針對(duì)LR可視多邊形P中的ESP問題進(jìn)行研究，求解從起點(diǎn)s到達(dá)終點(diǎn)t的，且完全包含在P內(nèi)的最短路徑。為求解該問題，本文首先論述了

2、與求解ESP問題相關(guān)的計(jì)算幾何領(lǐng)域的基礎(chǔ)知識(shí)與算法，并通過分析LR可視多邊形的性質(zhì)以及與最短路徑的相互關(guān)系，給出了基于凸面路徑求解最短路徑的算法思路。以此為基礎(chǔ)，提出了一個(gè)以R鏈為基準(zhǔn)鏈構(gòu)造右凸面路徑，并通過分析L鏈上的凹頂點(diǎn)與右凸面路徑的位置關(guān)系，確定L鏈上屬于最短路徑SP(s，t)的凹頂點(diǎn)的最短路徑求解算法，編程實(shí)現(xiàn)所提出的算法并構(gòu)造測(cè)試數(shù)據(jù)驗(yàn)證了算法的有效性。
　　 實(shí)驗(yàn)結(jié)果表明，本文提出的算法是有效的，能夠針對(duì)LR可視多