最短路径和测地线
给定一个完全由四边形组成的网格，其中每个顶点的化合价为n（n> =
3），并且不位于同一平面上，因此我需要找到网格中每个顶点与一组封闭的种子顶点之间的距离。也就是说，给定一个或多个网格顶点（一个种子集），我需要构建一个距离图，该距离图存储每个网格顶点到种子集的距离（与它们的距离为0）。
花了一些时间寻找可能的解决方案后，我得到了以下图片：
1）这并非微不足道，并且在过去20年左右的时间里已经开发出不同的方法
2）每种考虑3d域的算法都限于三角形域
说，这是我得到的照片：
Dijkstra算法可以用作找到两个顶点之间，沿着网格边缘的路径" title="最短路径">最短路径的方法，但是它非常不准确，会导致错误的测地线。Lanthier（LA）提出了一种改进，但是误差仍然很大。
Kimmel和Sethian（KS）提出了一种快速行进方法-FMM-
来求解Eikonal方程，解决了计算从种子点开始的波传播并记录波穿过每个顶点的时间的问题。不幸的是，该算法虽然简单易行，但仍然带来了相当不准确的结果，因此必须注意避免产生钝三角形，或者以非常特殊的方式对其进行处理。Novotni（NV）在单种子场景中解决了（KS）精度的问题，但是我不清楚是否：
a）它仍然遭受钝角问题
b）在多个种子点场景中使用时，必须为每个单个种子实施单个FMM，以便找到每个网格顶点与每个种子的最小距离（也就是说，在10个种子点场景中，FMM将具有每个网格顶点运行10次）
另一方面，Mitchell等人提出了导致0错误的精确算法-
MMP-。（MI）在87中，而且AFAIK从未真正被削弱（可能是由于所需的计算能力）。在相同的精确方法上，Surazhsky等人。（SU）提供了一种基于MMP的替代精确算法，该算法在速度方面应优于后者，但仍可得出正确的结果。不幸的是，即使比原始MMP小得多，计算所需的计算能力仍然足够高，以至于此时无法进行实时交互式实现。（SU）还提出了精确算法的近似值，即所谓的精确算法。它应该花费与FMM相同的计算时间，而仅带来误差的1/5，但是：
c）我不清楚是否可以在多种子场景中使用它。
Chen＆Han（CH）和Kapoor（KP）提出了其他精确的最短路径算法，但是尽管第一种绝对慢，但是第二种却过于复杂，无法在实践中实施。
所以..底线是：我需要距集合的距离，而不是2点之间的最短路径。
如果我做对了，
要么我使用FMM一次就获得了一组顶点与每个顶点的距离，
-要么-
使用另一种算法来计算从每个网格顶点到每个种子点的测地线，并找到最短的（如果正确，这意味着在每个网格顶点的每个种子点上调用该算法，即在10,000个顶点网格上）和50点的种子集，我必须计算500,000个测地线才能得到10,000个最短的测地线。
我想念什么吗？FMM是一次处理多个种子距离的唯一方法吗？有人知道精确算法是否可以在多个种子点场景中使用？
n
笔记：
（LA）：Lanthier等。“在多面体表面上近似加权最短路径”
（堪萨斯州）：塞缪尔州金梅尔“计算流形上的测地路径”
（NV）：Novotni“计算三角形网格上的测地距离”
（MI）：Mitchell等。“离散测地线问题”
（SU）：Surazhsky，Kirsanov等。“网格上的快速精确和近似测地线”
（CH）：Chen，Han，“多面体上最短的路径”
（KP）：Kapoor“大地测量最短路径的高效计算”
回答：
有一篇新文章详细讨论了如何解决您的问题：热中的测地线。（只是发现了它，它使我想起了您的问题。）这个想法是可以将热方程视为描述粒子从某个中心点的扩散。尽管它对随机扩散进行建模，但是如果您运行热方程足够短的时间，则从A到B的任何粒子都必须遵循最短路径，因此从数学上可以估算距离。
问题在于，沿着接近最短路径的路径的粒子比例很小，因此您必须解决一个微分方程，该方程在某个区域开始较大，而在其他区域迅速结束。从数字上讲，这不太可能表现良好。诀窍在于，对于较大的t，即使它不能正确测量距离，它也会给出距离函数的梯度，并且可以与其他方法一起使用以获取距离。
TL; DR链接的纸可解决从网格中的每个点到任何子域的距离，包括有限的种子点集。
哦…我还没有自己测试过。
以上是 最短路径和测地线 的全部内容， 来源链接： utcz.com/qa/430616.html
