本文關(guān)鍵詞： 計算幾何 簡單多邊形 最短路徑 可視圖 可視點對　出處：《大連海事大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：本文針對簡單多邊形中限于給定點集的最短路徑問題進(jìn)行研究,以期設(shè)計出一個求解算法,使得對于簡單多邊形中給定的點集以及起點s和終點t,能夠找到一條從點s出發(fā),中間經(jīng)過給定點集中的某些點(也可能不經(jīng)過),到達(dá)點t的最短路徑。若這樣的路徑存在,則輸出該路徑;否則,報告出最短路徑不存在的結(jié)論。該問題是TSP問題的變形問題,也是很多實際應(yīng)用問題(如物流配送問題等)的抽象模型,因此研究該問題,不僅具有理論意義,而且具有很大的實際應(yīng)用價值。本文首先分析了簡單多邊形中點的可視性與最短路徑計算的關(guān)聯(lián)關(guān)系,然后通過分析簡單多邊形的頂點凸凹特性,將給定的簡單多邊形分割成若干個邊鏈,求出邊鏈對應(yīng)的可視集,使得分布于每個可視集中的給定點之間相互可視。在此基礎(chǔ)上,計算出關(guān)于給定點集的所有可視點對,最后運用Dijkstra算法計算出從點s到點t的最短路徑。由于給定點集具有任意性,所以滿足要求的最短路徑未必存在,本文詳細(xì)地分析了最短路徑存在性,設(shè)計出了相應(yīng)的判別算法以及最短路徑的求解算法并加以分析。為了驗證所設(shè)計算法的有效性,本文實現(xiàn)了所設(shè)計的算法并對算法運行結(jié)果做了較為詳細(xì)的分析。實現(xiàn)結(jié)果表明,本文所設(shè)計的算法是高效的,在時間性能上優(yōu)于已有的輸出敏感度等算法。
[Abstract]:This paper studies limited to the shortest path problem for point set simple polygons, in order to design an algorithm, which for a given set of points in a simple polygon and the starting point and end point of S T, to be able to find a s from the point of the middle point to point after certain concentration (or may not pass), the shortest path to reach the t. If such a path exists, then the output of the path; otherwise, the report of the shortest path does not exist. The conclusion of this problem is the deformation problem of the TSP problem, but also a lot of problems in practical applications (such as logistics and distribution problems etc.) abstract model, so the research of this problem, not only has the theory significance, but also has great practical value. This paper first analyzes the relationship between visibility and simple polygon point shortest path calculation, and then through the analysis of characteristics of simple polygon convex concave vertices will be given. A simple polygon is divided into a plurality of side chain, and set the corresponding visual side chain, the distribution at each given point between the visual focus mutually visible. On this basis, calculated on a given point set all the visible point on, finally using Dijkstra algorithm to calculate the shortest path from point s to point t. For a given point set is arbitrary, so the shortest path may not meet the requirements, this article makes a detailed analysis of the existence of the shortest path, designed the corresponding algorithm and the algorithm of the shortest path and analysed. In order to verify the validity of the designed algorithm, this paper realizes the design of the algorithm and the algorithm results are analyzed in detail. The results show that the algorithm is efficient, the time performance is better than the output sensitivity of the algorithm.

【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 胡國棟;李旭東;胡金喜;;一種判定簡單多邊形可視頂點的算法[J];甘肅科技;2007年10期

2 宋曉眉;程昌秀;周成虎;;簡單多邊形頂點凹凸性判斷算法綜述[J];國土資源遙感;2011年03期

3 胡國棟;李旭東;胡金喜;;簡單多邊形凸凹頂點的識別[J];甘肅科技;2007年08期

4 周文科;一種簡單多邊形凸包的快速算法及程序設(shè)計[J];廣州大學(xué)學(xué)報(自然科學(xué)版);2003年06期

5 曲吉林,楊洪萬;平面內(nèi)任意一組簡單多邊形的可見性[J];山東師大學(xué)報(自然科學(xué)版);2000年02期

6 宋立明;閆浩文;王邦松;方愛玲;;兩個簡單多邊形求交的算法[J];測繪與空間地理信息;2011年06期

7 崔先國;毛定山;;簡單多邊形間最大距離的求解算法[J];測繪科學(xué);2008年06期

8 劉國棟;;整點多邊形[J];惠陽師專學(xué)報(自然科學(xué)版);1991年03期

9 徐嘉;;二面體群作用下簡單多邊形的分類[J];計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報;2012年07期

10 王相海;制定點是否包容于簡單多邊形中的一個三角剖分方法[J];松遼學(xué)刊(自然科學(xué)版);1995年02期

相關(guān)碩士學(xué)位論文 前10條

1 周斌;基于建筑物空間結(jié)構(gòu)特征的三維重建算法關(guān)鍵技術(shù)研究[D];東南大學(xué);2016年

2 王玉瑩;簡單多邊形中限于給定點集的最短路徑求解研究[D];大連海事大學(xué);2017年

3 馬永卓;簡單多邊形構(gòu)造方法研究[D];南昌航空大學(xué);2013年

4 韓冰;簡單多邊形內(nèi)LR可視問題的求解算法研究[D];大連海事大學(xué);2011年

5 李玉娟;簡單多邊形中兩個守衛(wèi)的min-sum算法研究[D];大連海事大學(xué);2011年

6 周志峰;簡單多邊形中兩個守衛(wèi)的max-min算法研究[D];大連海事大學(xué);2012年

7 郭佳;可掃描簡單多邊形中兩守衛(wèi)間min-max距離求解研究[D];大連海事大學(xué);2013年

8 湯立東;計算幾何中LR可視化問題研究[D];大連海事大學(xué);2010年

9 何雨靜;Link-2可視多邊形中三守衛(wèi)問題的求解算法研究[D];大連海事大學(xué);2014年

10 劉元;兩個守衛(wèi)問題的最優(yōu)掃描算法研究與實現(xiàn)[D];大連海事大學(xué);2016年

，

本文編號：1522659