Fast Marching Methods
Fast Marching Methods
复制标题
DOI：
10.1007/978-0-387-21637-9_7
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
R. Kimmel
中科院分区：
文献类型：
--
作者：
R. Kimmel
快速行军法是由Sethian[190,191,192]提出的，它是平域对角方程的一种计算效率较高的求解方法。Tsitsiklis在[205]中提出了一种相关方法。Kimmel和Sethian在[112]中将快速行军法推广到三角曲面。扩展方法求解平面矩形或弯曲三角域上的正交方程，步数为n (M)步，其中M为顶点数。换句话说，找到解的计算复杂度是最优的。在这里，我们将介绍一个易于实现的anO（MlogM）方法。利用这种方法，可以有效地计算具有局部权值的弯曲流形上的距离。在本章中，我们从一维距离计算的一个简单例子开始，它简化了eikonal方程粘度解的概念。然后，将快速行军方法应用于机器人在非平凡位形空间中导航的路径规划。最后，我们探索了有效距离计算在曲面上的能力，并介绍了在三角曲面上的最小测地线计算、测地线Voronoi图和加权曲面上的曲线偏移计算等应用。
The fast marching method was introduced by Sethian [190, 191, 192] as a computationally efficient solution toeikonal equationson flat domains. A related method was presented by Tsitsiklis in [205]. The fast marching method was extended to triangulated surfaces by Kimmel and Sethian in [112]. The extended method solves eikonal equations on flat rectangular or curved triangulated domains inO(M)steps, whereMis the number of vertices. In other words, the computational complexity of finding the solution is optimal. Here, we will present anO(MlogM) method that is simple to implement. Using this technique, one can efficiently compute distances on curved manifolds with local weights. In this chapter we start with a simple example of distance computation in 1D that simplifies the notion of viscosity solutions of eikonal equations. Next, the fast marching method is applied to path planning of a robot navigating in nontrivial configuration space with a small number of degrees of freedom. Finally, we explore the power of efficient distance computation on curved domains, and present applications like minimal geodesic computation on triangulated surfaces, geodesic Voronoi diagrams, and curve offset calculations on weighted surfaces.