最短路径和测地线
给定一个完全由四边形组成的网格，其中每个顶点都有价n(n >=为3)，并且不在同一平面上，我需要找出网格中每个顶点到一组封闭的种子顶点的距离。也就是说，给定一个或多个网格顶点(一个种子集)，我需要构建一个距离图，用于存储每个网格顶点与种子集之间的距离(它们之间的距离为0)。
在花了一些时间寻找可能的解决方案后，我得到了以下图片：
1)它不是微不足道的，在过去的20年左右，已经开发出了不同的方法。
2)每种考虑3d区域的算法都被限制在一个三角形区域内
说到这里，这是我得到的图片：
Dijkstra算法可以用来寻找两个顶点之间的最短路径，沿着网格的边，但它非常不准确，会导致错误的测地线。Lanthier (LA)提出了一项改进，但误差仍然很高。
Kimmel和Sethian (KS)提出了一种快速行进方法-FMM-来求解Eikonal方程，解决了计算从种子点开始的波的传播并记录波通过每个顶点的时间的问题。不幸的是，这个算法虽然很容易实现，但仍然带来了相当不准确的结果，并且必须小心避免钝化三角形，或者以非常特殊的方式处理它们。Novotni (NV)解决了单一种子场景中的(KS)精度问题，但我不清楚是否：
a)它仍然存在钝角问题。
b)在多个种子点场景中使用时，必须为每个单个种子实现单个FMM，以便找到每个网格顶点到每个种子的最小距离(即，在10个种子点场景中，每个网格顶点必须运行10次FMM )
另一方面，Mitchell等人提出了一种精确的算法-MMP-导致0误差。(MI)在87中，AFAIK从未真正实现过(可能是由于所需的计算能力)。在相同的方法上，Surazhsky和al。(SU)提供了一种基于MMP的替代精确算法，该算法在速度方面应该优于后者，但仍会导致正确的结果。不幸的是，计算所需的计算能力，即使比原始的MMP小得多，仍然足够高，以至于在这个时候实时交互实现是不可行的。(SU)还提出了他们的精确算法的近似，他们称之为扁平精确。它的计算时间应该与FMM相同，而误差仅为FMM的1/5，但是：
c)我不清楚它是否可以用于多种子场景。
Chen & Han (CH)和Kapoor (KP)已经提出了其他精确最短路径算法，但是第一种算法绝对慢，第二种算法太复杂，无法在实践中实现。
所以..。底线是:我需要到一个集合的距离，而不是两个点之间的最短路径。
如果我没弄错的话，
或者我使用FMM在单次遍历中获得每个顶点与集合的距离，
-或者-
使用另一个算法来计算从每个网格顶点到每个种子点的测地线，并找到最短的一个(如果我做对了，这意味着在每个网格顶点的每个种子点上调用该算法，即在10,000个顶点网格和50个点的种子集上，我必须计算500,000个测地线才能得到10,000个最短的)。
我是不是遗漏了什么？FMM是在单次传递中处理多个种子距离的唯一方法吗？有人知道扁平精确算法是否可以用于多个种子点的场景吗？
thnx
备注：
(LA)：Lanthier & al。“近似多面体曲面上的加权最短路径”
(KS)：Kimmel，Sethian“计算流形上的测地线路径”
(NV)：Novotni“计算三角网格上的测地距离”
(MI)：Mitchell & al。“离散测地线问题”
(SU)：Surazhsky，Kirsanov等人。“网格上的快速精确和近似测地线”
(CH)：Chen，Han，“多面体上的最短路径”
(KP)：Kapoor“测地最短路径的有效计算”
回答 4
Stack Overflow用户
发布于 2012-05-01 03:24:04
有一篇新论文确切地讨论了如何解决你的问题：Geodesics in Heat。(我刚刚发现了它，它让我想起了你的问题。)这个想法是，热方程可以被认为是描述粒子从某个中心点扩散的过程。虽然它模拟了随机扩散，但如果你运行热方程足够短的时间，那么从A到B的任何粒子都必须遵循最短路径，所以从数学上你可以得到距离的估计。
问题是，沿着最短路径的粒子比例很小，所以你必须解一个微分方程，这个微分方程在某个区域开始很大，在其他地方很快就会变小。这在数值上不太可能表现良好。诀窍是，对于较大的t，即使它不能正确测量距离，它也给出了距离函数的梯度，这可以与其他方法一起使用来获得距离。
链接的论文解决了从网格中的每个点到任何子域的距离，包括有限的种子点集合。
Oh...and我还没有亲自测试过。
Stack Overflow用户
发布于 2014-11-25 02:44:41
"a)它仍然存在钝角问题。“
是的，最初的FMM存在钝角问题，但研究人员已经解决了这个问题。这个链接是Gabriel Peyre在matlab中实现的快速行进方法。http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching
B)在多个种子点方案中使用时，必须为每个单个种子实施单个FMM，以便找到每个网格顶点到每个种子的最小距离(即，在10个种子点方案中，每个网格顶点必须运行10次FMM )
如果你指的是多源最短路径问题，快速行进方法不需要多次运行。例如，对于种子s1和s2以及目标v，s1和v之间的最短距离是d(s1，v)，s2和v之间的距离是d(s2，v)。为了找到v与s1，s2，s2(d(s1，v)，d(s2，v))之间的最短距离，运行一次快速行进方法就足够了。但是如果你想知道d(s1，v)和d(s2，v)，你需要多次运行FMM。
“另一方面，Mitchell等人提出了一种精确的算法-MMP-导致0误差。(MI)在87中，AFAIK从未真正实现过(可能是由于所需的计算能力)。在相同的方法上，Surazhsky和al。(SU)提供了一种基于MMP的替代精确算法，该算法在速度方面应该优于后者，但仍会导致正确的结果。不幸的是，计算所需的计算能力，即使比原始的MMP小得多，仍然足够高，以至于在这个时候实时交互实现是不可行的。(SU)还提出了他们的精确算法的近似，他们称之为扁平精确。它的计算时间应该与FMM相同，而误差仅为FMM的1/5，但是：
注释:MMP2005年有一个实现，该实现在1中发布。代码的链接在https://code.google.com/p/geodesic/中
"c)我不清楚它是否可以用于多种子方案。“
它可以用于多种子场景，上面的代码实现了它。
Chen & Han (CH)和Kapoor (KP)已经提出了其他精确最短路径算法，但第一种算法绝对慢，第二种算法太复杂，无法在实践中实现。
评论:第一个算法速度很慢，但在第二个算法中，作者改进了CH算法，并给出了一个实际的实现，它比MMP更精确、更快。代码在sites.google.com/site/xinshiqing/knowledge-share中
1Vitaly Surazhsky，Tatiana Surazhsky，Danil Kirsanov，Steven Gortler，Hugues Hoppe。网格上的快速、精确和近似测地线。ACM传输图形(SIGGRAPH)，24(3)，2005。
2改进了Chen &Han关于离散测地线问题的算法。辛世庆和王国进。ACM图形交易(TOG)：28(4)，第1-8页，2009年8月。
Stack Overflow用户
发布于 2012-03-27 02:03:41
https://stackoverflow.com/questions/6940051
复制相似问题
腾讯云开发者
