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

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

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