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

论文摘要

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

论文目录

摘要

Abstract

第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 进一步研究工作

参考文献

致谢

研究生履历

相关论文文献

[1].Optimal control on special Euclidean group via natural gradient algorithm[J]. Science China(Information Sciences) 2016(11)
[2].A Property of Continuous Mapping from a Sphere to the Euclidean Space and Its Applications[J]. 数学研究与评论 2010(02)
[3].Singularities of lightlike hypersurface in semi-Euclidean 4-space with index 2[J]. Science China(Mathematics) 2010(12)
[4].The Rigidity of Hypersurfaces in Euclidean Space[J]. Chinese Annals of Mathematics,Series B 2019(03)
[5].On the Parallel and Totally Umbilical Hypersurfaces of the Euclidean Ellipsoid[J]. Journal of Mathematical Research with Applications 2016(05)
[6].Euclidean Distance Transform on the Sea Based on Cellular Automata Modeling[J]. Journal of Geodesy and Geoinformation Science 2020(02)
[7].Commutators of Lipschitz Functions and Singular Integrals with Non-Smooth Kernels on Euclidean Spaces[J]. Analysis in Theory and Applications 2016(02)
[8].On the Number of Polynomials with Small Discriminants in the Euclidean and p-adic Metrics[J]. Acta Mathematica Sinica 2012(03)
[9].Solving the Euclidean Steiner Minimum Tree Using Cellular Stochastic Diffusion Search Algorithm[J]. Journal of Shanghai Jiaotong University(Science) 2011(06)
[10].Euclidean Distance Transform on the Sea based on Cellular Automata Modeling[J]. Journal of Geodesy and Geoinformation Science 2020(01)
[11].Enhancing Collaborative Filtering via Topic Model Integrated Uniform Euclidean Distance[J]. 中国通信 2017(11)
[12].A Distance Function for Computing on Finite Subsets of Euclidean Spaces[J]. Acta Mathematicae Applicatae Sinica 2018(01)
[13].A Schwarz Lemma for Harmonic Mappings Between the Unit Balls in Real Euclidean Spaces[J]. Chinese Annals of Mathematics,Series B 2018(06)
[14].The Euclidean Distance Spectra of FDMA-CPM: Algorithms and Applications[J]. Chinese Journal of Electronics 2014(04)
[15].用简化脉冲耦合神经网络实现交通标志图像的类Euclidean距离变换类内特征提取[J]. 光学精密工程 2012(12)
[16].An Addressing and Routing Scheme Based on Modified Euclidean Space for Hexagonal Networks[J]. 中国通信 2015(05)
[17].Lagrangian Mean Curvature Flow in Pseudo-Euclidean Space[J]. Chinese Annals of Mathematics(Series B) 2011(02)
[18].Higher Order Willmore Hypersurfaces in Euclidean Space[J]. Acta Mathematica Sinica(English Series) 2009(01)
[19].On the Rigidity Theorems for Lagrangian Translating Solitons in Pseudo-Euclidean Space Ⅰ[J]. Acta Mathematica Sinica 2013(07)
[20].Algorithms for degree-constrained Euclidean Steiner minimal tree[J]. Journal of Systems Engineering and Electronics 2008(04)
[21].Bernstein type theorem of minimal Lagrangian graphs in quaternion Euclidean space H~n[J]. Applied Mathematics:A Journal of Chinese Universities(Series B) 2009(01)
[22].A method for extracting anomaly map of Au and As using combination of U-statistic and Euclidean distance methods in Susanvar district,Iran[J]. Journal of Central South University 2017(11)
[23].A unified framework for isotropic meshing based on narrowband Euclidean distance transformation[J]. Computational Visual Media 2015(03)
[24].Evaluation of Surface Water Quality in Forest Catchment Based on Euclidean Distance Model with Varying Weights[J]. Chinese Forestry Science and Technology 2012(03)
[25].Empirical Euclidean likelihood for general estimating equations under association dependence[J]. Applied Mathematics:A Journal of Chinese Universities(Series B) 2010(04)
[26].L~1-Poincaré and Sobolev inequalities for differential forms in Euclidean spaces Dedicated to Professor Jean-Yves Chemin on the Occasion of His 60th Birthday[J]. Science China(Mathematics) 2019(06)
[27].基于ZigBee的加权改进Euclidean定位算法[J]. 电视技术 2011(23)
[28].MULTIFRACTAL DECOMPOSITION OF FRACTALS WITH FINITE MEMORY[J]. Acta Mathematica Scientia 2008(01)
[29].Double-Space-Cooperation Method for Increasing Channel Capacity[J]. 中国通信 2015(12)
[30].碎纸片的拼接复原[J]. 电子测试 2014(07)

标签：计算几何论文; 最短路径问题论文; 简单多边形论文; 分而治之论文;

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

论文摘要

论文目录

相关论文文献

猜你喜欢