给定一个完全由四边形组成的网格，其中每个顶点都具有效价n（n> = 3），并且不在同一平面上，我需要从一组封闭的种子顶点中找到网格中每个顶点的距离 . 也就是说，给定一个或多个网格顶点（种子集），我需要构建一个距离图，该距离图存储每个网格顶点距种子集的距离（距离自身的距离为0） .
在花了一些时间寻找可能的解决方案之后，我得到了以下图片：
1）这不是微不足道的，并且在过去20年左右的时间里已经开发了不同的方法
2）考虑3d域的每个算法都限于三角域
说，这是我得到的图片：
Dijkstra算法可以用作在网格边缘之后找到2个顶点之间的最短路径的方法，但是它非常不准确并且将导致错误的测地线 . Lanthier（洛杉矶）提出了改进，但错误仍然很高 .
Kimmel和Sethian（KS）提出了一种快速行进方法-FMM-来解决Eikonal方程，解决计算从种子点开始的波传播并记录波穿过每个顶点的时间的问题 . 不幸的是，这个算法虽然简单易于实现，但仍然会带来非常不准确的结果，必须注意避免使用钝角三角形，或者以非常特殊的方式处理它们 . Novotni（NV）解决了单个种子场景中（KS）精度的问题，但我不清楚是否：
a）它仍然受到钝角问题的困扰
b）当在多种子点场景中使用时，必须为每个种子实施单个FMM，以便从每个种子中找到每个网格顶点的最小距离（即，在10个种子点场景中，FMM将具有每个网格顶点运行10次）
另一方面，Mitchell等人提出了导致0错误的精确算法-MMP- . （MI）在87年，AFAIK从未真正被扼杀（可能是由于所需的计算能力） . 同样的方法，Surazhsky＆al . （SU）提供了基于MMP的替代精确算法，其在速度方面应该优于后者，仍然导致正确的结果 . 不幸的是，计算所需的计算能力，即使比原始MMP小得多，仍然足够高，因此此时实时交互式实现是不可行的 . （SU）也提出了他们的精确算法的近似，他们称之为平精确 . 它应该花费相同的FMM计算时间，同时只带来1/5的错误，但是：
c）我不清楚它是否可用于多种子方案 .
Chen＆Han（CH）和Kapoor（KP）已经提出了其他精确的最短路径算法，但是第一种算法绝对慢，第二种算法太复杂而无法在实践中实施 .
所以..底线是：我需要一组距离，而不是两点之间的最短路径 .
如果我做对了，
要么我使用FMM来获取单个通道中每个顶点的距离，
-要么-
使用另一种算法来计算从每个网格顶点到每个种子点的测地线，并找到最短的一个（如果我把它弄好，这意味着在每个网格顶点的每个种子点上调用该算法，即在10,000个顶点网格上和一个50分的种子集，我将不得不计算500,000测地线，以获得10,000最短的一个）
我错过了什么吗？ FMM是一次通过多种种子距离的唯一方法吗？有人知道平面精确算法是否可用于多种子点场景？
日Thnx
笔记：
（洛杉矶）：Lanthier等 . “在多面体表面上逼近加权最短路径”
（KS）：Kimmel，Sethian“在流形上计算测地线路径”
（NV）：Novotni“计算三角网格上的测地距离”
（MI）：米切尔等人 . “离散测地线问题”
（SU）：Surazhsky，Kirsanov等 . “网格上的快速精确和近似测地线”
（CH）：Chen，Han，“多面体的最短路径”
（KP）：Kapoor“高效计算geodeisc最短路径”
4 回答
有一篇新文章讨论了如何解决您的问题：Geodesics in Heat . （刚发现它并且它让我想起了你的问题 . ）这个想法是热量方程可以被认为是描述粒子从某个中心点的扩散 . 虽然它模拟随机扩散，如果你运行热方程足够短的时间，然后从A到B的任何粒子必须遵循最短的路径，所以在数学上你可以得到距离的估计 .
问题在于，沿着接近最短路径的路径的粒子比例很小，因此您必须求解一个在某个区域开始较大且在其他地方迅速变小的微分方程 . 这不太可能在数字上表现良好 . 诀窍在于，对于较大的t，即使它没有正确测量距离，它确实给出了距离函数的梯度，这可以与其他方法一起使用来获得距离 .
TL; DR链接的纸张解决了从网格中的每个点到任何子域的距离，包括有限的种子点集 .
哦......我自己没有测试过 .
“a）它仍然受到钝角问题的困扰”
是的，原来的FMM患有钝角问题，但研究人员已经解决了这个问题 . 这个链接是Gabriel Peyre在matlab中实现快速行进方法 . http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching
“b）当在多种子点场景中使用时，必须为每个种子实施单个FMM，以便从每个种子中找到每个网格顶点的最小距离（即，在10个种子点场景中，FMM将必须每个网格顶点运行10次）“
如果您的意思是多源最短路径问题，快速行进方法不需要多次运行 . 例如，对于种子s1和s2以及目的地v，并且s1和v之间的最短距离是d（s1，v），s2和v之间的距离是d（s2，v） . 要找到v和s1，s2，min（d（s1，v），d（s2，v））之间的最短距离，运行一次快速行进方法就足够了 . 但是如果你想知道d（s1，v）和d（s2，v），你需要多次运行FMM .
“另一方面，Mitchell等人（MI）在87年提出了一个确切的算法-MMP-导致0错误，AFAIK从未被真正扼杀（可能是由于所需的计算能力） . 同样精确的方法，Surazhsky等人（SU）提供了一种基于MMP的替代精确算法，在速度方面应该优于后者，仍然可以得到正确的结果 . 不幸的是，计算所需的计算能力，即使远低于原始的MMP，仍然足够高，以至于此时实时交互式实现是不可行的 . （SU）也提出了他们的精确算法的近似，他们称之为平精确 . 它应该采用相同的FMM计算时间，而只带来1/5的错误，但是：“
评论：MMP在2005年实施，实施发表在[1] . 该代码的链接位于https://code.google.com/p/geodesic/
“c）我不清楚它是否可用于多种子方案 . ”
它可用于多种子场景，上面的代码实现了它 .
“Chen＆Han（CH）和Kapoor（KP）提出了其他精确的最短路径算法，但第一种算法绝对缓慢，第二种算法太复杂，无法在实践中实施 . ”
评论：第一个是缓慢的，但在[2]中，作者改进了CH算法并给出了一个比MMP更精确和更快的实际实现 . 该代码位于sites.google.com/site/xinshiqing/knowledge-share中
[1] Vitaly Surazhsky，Tatiana Surazhsky，Danil Kirsanov，Steven Gortler，Hugues Hoppe . 网格上的快速精确和近似测地线 . ACM Trans . 图形（SIGGRAPH），24（3），2005 .
[2]改进Chen＆Han的离散测地线问题算法 . 施清新和王国进 . ACM Transactions on Graphics（TOG）：28（4），pp . 1-8，2009年8月 .
这可能更适合理论计算机科学堆栈交换 . 在最短边路径上查看此文章 .
https://cstheory.stackexchange.com/questions/6822/shortest-paths-disallowing-each-edge
也许吧
https://cstheory.stackexchange.com/questions/4034/complexity-of-computing-shortest-paths-in-the-plane-with-polygonal-obstacles
另一种选择：Euclidean Shortest Path Algorithm这是最近（2012）最短路径的通用实现 .