简单多边形中限于给定点集的最短路径求解研究

发布时间：2018-02-21 19:16

本文关键词： 计算几何简单多边形最短路径可视图可视点对　出处：《大连海事大学》2017年硕士论文　论文类型：学位论文

【摘要】：本文针对简单多边形中限于给定点集的最短路径问题进行研究,以期设计出一个求解算法,使得对于简单多边形中给定的点集以及起点s和终点t,能够找到一条从点s出发,中间经过给定点集中的某些点(也可能不经过),到达点t的最短路径。若这样的路径存在,则输出该路径;否则,报告出最短路径不存在的结论。该问题是TSP问题的变形问题,也是很多实际应用问题(如物流配送问题等)的抽象模型,因此研究该问题,不仅具有理论意义,而且具有很大的实际应用价值。本文首先分析了简单多边形中点的可视性与最短路径计算的关联关系,然后通过分析简单多边形的顶点凸凹特性,将给定的简单多边形分割成若干个边链,求出边链对应的可视集,使得分布于每个可视集中的给定点之间相互可视。在此基础上,计算出关于给定点集的所有可视点对,最后运用Dijkstra算法计算出从点s到点t的最短路径。由于给定点集具有任意性,所以满足要求的最短路径未必存在,本文详细地分析了最短路径存在性,设计出了相应的判别算法以及最短路径的求解算法并加以分析。为了验证所设计算法的有效性,本文实现了所设计的算法并对算法运行结果做了较为详细的分析。实现结果表明,本文所设计的算法是高效的,在时间性能上优于已有的输出敏感度等算法。
[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.

【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O18

【相似文献】