简单多边形内Euclidean最短路径问题算法研究

摘要

Euclidean最短路径问题是计算几何中一个比较典型的问题，它的主要研究议题是：对于给定的一系列欧氏空间中的障碍物与其中的任意两点，希望找出这两点之间的最短路径。本文对该问题中的一个子问题即简单多边形内Euclidean最短路径问题进行深入的研究。
　　 简单多边形内Euclidean最短路径问题的几何描述为：给定简单多边形P及其内两点s、t，求解该两点之间的最短路径。该问题的解决算法在很多问题的解决中被使用，如巡视员问题，机器人的运动规划等等。
　　 在求解简单多边形内Euclidean最短路径问题时，会遇到大量计算几何的基础问题，如判断两点是否重合、两条线段位置关系，所以本文首先对这些基础问题进行阐述与分析，并给出了相应的解决方法。随后，本文对Euclidean最短路径所具有的性质进行了深入的研究，然后对在该问题上前人已给出的Funnel算法与Rubberband算法进行了深入的研究，并详细分析了这两个算法的时间复杂度。本文的重点是在Rubberband算法基础上给出了改进算法，改进算法在原有的算法上引入了分而治之思想，这样可以把问题的规模缩小，从而使问题的求解速度加快。同时，本文给出了Rubberband算法与改进算法的实现，运用事后分析方法对两算法的运行时间结果曲线进行了拟合，并求解了拟合曲线的方程，从而验证了改进算法的优越性。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景与意义

1.2研究内容

1.3论文的组织结构

第2章Euclidean最短路径问题的基础问题

2.1计算几何基础

2.1.1计算几何

2.1.2准备知识

2.2典型算法

2.2.1基础算法

2.2.2三角剖分

2.2.3对偶图最短路径求解

2.3 Euclidean最短路径问题

第3章Euclidean最短路径问题求解算法

3.1 Euclidean最短路径性质

3.2 Euclidean最短路径求解算法

3.2.1 Funnel算法

3.2.2 Rubberband算法

3.3时间复杂度分析

第4章求解算法的改进

4.1改进算法思路

4.2数据结构

4.3算法实现

4.3.1 Rubberband算法实现

4.3.2改进算法实现

第5章结果分析

5.1测试数据的生成

5.2运行时间结果分析

第6章总结与展望

6.1论文工作总结

6.2进一步研究工作

参考文献

致 谢

研究生履历