訪問平面內(nèi)線段序列的ESP問題求解算法研究.pdf

1、Euclidean最短路徑問題簡稱ESP問題,它是計算幾何研究領(lǐng)域的經(jīng)典問題。本文針對訪問平面內(nèi)給定線段次序的線段集的ESP問題進行研究,著重研究給定線段集中可能存在相交線段的情形。該問題是很多實際應(yīng)用問題的抽象模型,所以針對該問題的研究,具有較大的現(xiàn)實意義。
　　 本文首先分析了訪問平面內(nèi)線段序列的ESP問題的問題特征,對求解該問題所涉及到的計算幾何中的相關(guān)基礎(chǔ)知識、簡單多邊形的梯形分解與三角剖分等內(nèi)容做了較為深入的論述,并對

2、Rubberband算法及其特點做了較為深入的剖析。在此基礎(chǔ)上,針對給定線段集的相鄰線段可能出現(xiàn)相交的情形,詳細論述了Rubberband算法在處理這類問題時可能出現(xiàn)的退化現(xiàn)象,并針對這一現(xiàn)象提出了相應(yīng)的處理方法,同時引進分治方法,對Rubberband算法加以改進,使之能夠適用于本文所給出的這類ESP問題。在給出改進方案后,設(shè)計了相應(yīng)的數(shù)據(jù)結(jié)構(gòu),具體實現(xiàn)了改進前后的Rubberband算法,并隨機構(gòu)造了大量的測試數(shù)據(jù),實際測試運行改進