algorithm - 最短路径和测地线

Question

给定一个完全由四边形构成的网格，其中每个顶点的价为n（n>=3），并且不在同一平面上，我需要找到网格中每个顶点与一组封闭种子顶点之间的距离。也就是说，给定一个或多个网格顶点（种子集），我需要构建一个距离贴图，该贴图存储每个网格顶点与种子集之间的距离（种子集与网格顶点之间的距离为0）。
在花了一段时间寻找可能的解决方案后，我得到了以下图片：
1）这不是小事，在过去20年左右的时间里，已经开发出了不同的方法
2）每一个考虑3d域的算法都被限制在三角形域内。
这么说，这是我拍到的照片：
dijkstra算法可以用来寻找网格边上两个顶点之间的最短路径，但是它是非常不精确的，并且会导致错误的测地线。lanthier（la）提出了一个改进方案，但误差仍然很大。
kimmel和sethian（ks）提出了求解eikonal方程的快速行军方法fmm，解决了从种子点开始计算波传播并记录波穿过每个顶点的时间的问题。不幸的是，这个算法虽然简单到可以实现，但仍然会带来相当不准确的结果，必须注意避免钝角三角形，或者以非常特殊的方式处理它们。
Novotni（NV）解决了单一种子方案中（KS）精度的问题，但我不清楚是否：
a）仍然存在钝角问题
b）当在多种子点方案中使用时，必须为每个种子实现单个fmm，以便找到每个网格顶点与每个种子的最小距离（即，在10种子点方案中，每个网格顶点必须运行fmm 10次）。
另一方面，mitchell&al提出了一种精确的误差为0的mmp算法。（mi）在87年，afaik从未真正实现过（可能是由于所需的计算能力）。同样的方法，苏拉兹斯基和阿尔。（su）提供了一种基于mmp的替代精确算法，该算法在速度上应优于后者，仍能得到正确的结果。不幸的是，计算所需的计算能力，即使远低于原来的mmp，仍然足够高，因此实时交互实现在这个时候是不可行的。
（SU）还提出了它们的精确算法的近似，它们称为平坦精确的。它所需的计算时间应与fmm相同，但只带来1/5的误差，但是：
c）我不清楚它是否可以用于多种子方案。
chen&han（ch）和kapoor（kp）提出了其他精确的最短路径算法，但是第一种算法速度非常慢，第二种算法太复杂，无法在实际中实现。
所以..底线是：我需要一个距离集合，而不是两点之间的最短路径。
如果我做对了，
或者我用fmm得到每个顶点与一个集合的距离，
-或者-
使用另一个算法计算从每个网格顶点到每个种子点的测地线，并找到最短的一个（如果我做得对，那就意味着对每个网格顶点的每个种子点调用该算法，即对10000个顶点网格和50个种子点集调用该算法，我将不得不计算500，为了得到10000个最短的测地线）
我遗漏了什么吗？FMM是在一次传送中处理多个种子距离的唯一方法吗？有人知道平面精确算法是否可以用于多种子点场景？
THNX
笔记：
（洛杉矶）：兰希尔和阿尔。”多面体上加权最短路径的逼近
（KS）：Kimmel，Sethian，“计算流形上的测地路径”
（NV）：Novotni“在三角形网格上计算测地线距离”
（MI）：米切尔和阿尔。”离散测地线问题”
（苏）：苏拉兹斯基、基桑诺夫和阿尔。”网格上的快速精确近似测地线
（CH）：陈，韩，“多面体上的最短路径”
（kp）：kapoor“大地测量最短路径的有效计算”

Answer 1

有一篇新论文专门讨论如何解决你的问题：Geodesics in Heat。（刚刚发现它，它让我想起了你的问题）这个想法是热方程可以被认为是描述粒子从某个中心点扩散的。虽然它模拟了随机扩散，但是如果你运行热方程足够短的时间，那么从a到b的任何粒子都必须遵循最短的路径，这样在数学上你就可以得到距离的估计。
问题是，沿着最短路径的粒子所占比例很小，所以你必须解一个微分方程，这个方程从某个区域开始大，到其他地方很快就变小。这在数字上不太可能表现良好。诀窍在于，对于较大的t，即使它不能正确地测量距离，它也会给出距离函数的梯度，这可以与其他方法一起使用来获得距离。
链接的论文解决了从网格中的每个点到任何子域的距离，包括有限的种子点集。
哦…我自己也没试过。