平面內(nèi)經(jīng)過若干不相交線段的L1問題求解研究.pdf

1、L1距離問題是計(jì)算幾何領(lǐng)域的重要研究課題之一。通過對(duì)L1距離問題特性的研究,能夠得到求解計(jì)算幾何經(jīng)典問題的有效算法。因此,對(duì)于L1距離問題的研究,不僅具有重大的理論研究意義,而且也有非常重要的實(shí)際應(yīng)用價(jià)值。
　　 本文在論述最短路徑的相關(guān)理論的基礎(chǔ)上,對(duì)L1距離問題進(jìn)行了深入的研究,給出了利用平面劃分思想解決L1最短路徑問題的算法,并加以嚴(yán)格證明其適用性。通過分析平面上點(diǎn)與線段的位置關(guān)系,給出了L1路徑所具有的簡(jiǎn)單特性。以這些特

2、性為基礎(chǔ),本文提出了一個(gè)時(shí)間復(fù)雜度為O(n)的構(gòu)建平面空間劃分的算法,通過該算法以及求解L1最短路徑問題的算法,可以在線性時(shí)間內(nèi)計(jì)算出從起始點(diǎn)s出發(fā),遍歷k條線段序列,最終到達(dá)目標(biāo)點(diǎn)t的L1最短距離。這大大簡(jiǎn)化了求解過程。
　　 為了驗(yàn)證算法的可行性和有效性,本文針對(duì)測(cè)試數(shù)據(jù)求解出了最短路徑點(diǎn)及結(jié)果圖,并給出其L1最短路徑長(zhǎng)度,最后對(duì)算法運(yùn)行結(jié)果進(jìn)行了分析顯示。結(jié)果表明,本文所給出的算法,不僅是高效的,而且是切實(shí)可行。