簡(jiǎn)單多邊形內(nèi)Euclidean最短路徑問題算法研究.pdf

1、大連海事大學(xué)碩士學(xué)位論文簡(jiǎn)單多邊形內(nèi)Euclidean最短路徑問題算法研究姓名：侯斌申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（計(jì)算機(jī)軟件與理論）指導(dǎo)教師：蔣波20100601英文摘要AbstractEuclideanshortestpathproblem(ESP)isoneofthetypicalproblemsinComputationalGeometryItsmainresearchtopicistofindtheshortestp

2、athbetweentwopointsforagivenseriesofobstaclesinEuclideanspaceThispaperwillsgiveafurtherresearchtoasubproblemofEuclideanshortestpathproblems，whichisEuclideanshortestpathprobleminasimplepolygonThegeometricdescriptionofEucl

3、ideanshortestpathinasimplepolygonisfindingtheshortestpathbetweenpointSandpointtforagivensimplepolygonPAlgorithmsforthisproblemhavemanyuseforsolvingalotofproblems，suchasWatchmanRouteProblemsandRobotmotionplanningproblemet

4、cWhensolvingESPinasimplepolygon，wewillencountermanybasicproblemsofComputationalGeometrysuchasjudgingwhethertwopointscoincideandthepositionrelationshipbetweentwosegmentsSothispaperdescribesandanalyzestheseproblems，andgive

5、stherelatedsolvingmethodsThenwestudythepropertiesofEuclideanshortestpath，andhavethefurtherresearchbasedonFunnelalgorithmandRubberbandalgorithm，andanalyzethetimecomplexityofthesealgorithmsindetailThefocusofthepaperisthatw

6、egiveanimprovedalgorithmbasedonRubberbandalgorithmTheimprovedalgorithmintroducesthethoughtofDivideandConquerandSOwecanreducethescaleoftheproblem，andacceleratethespeedofproblemsolvingAtthesametimethepapergivestheimplement

7、ationofRubberbandalgorithmandimprovedalgorithm，andwefitthecurveofmnningtimeofthesetwoalgorithmsbySubsequentanalysisWesolvetheequation，andverifytheadvantageofimprovedalgorithmKeyWords：ComputationalGeometry；ESP；simplepolyg