三角形网格上的大地测量计算

Question

我试图找到三角曲面上两点之间的距离（测地线距离）。它看起来像是一个基本的操作，并不是微不足道的。所以我想知道是否有这样的图书馆？我的谷歌搜索失败了，所以我非常感谢任何提示。

（我知道CGAL，scipy.spatial，但我在文档中找不到任何东西，如果我遗漏了什么，请告诉我）

Answer 1

在三角形网格上计算测地线距离有很多实现。有些是近似的，有些是精确的。

1.快速行进法。这种方法是近似的，在实践中平均误差低于1%。您可以参考Gabriel Peyre在matlab中对快速行进方法的实现。http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

2. MMP方法由[1]提出，并在[2]中实施。此方法是精确的，代码位于https://code.google.com/p/geodesic/。与Ante的评论相同。一个缺点是，当网格较大时，MMP方法会消耗大量内存，O（n^2），n是顶点的数量。

3. CH方法在[3]中提出，并在[4]中进行了改进和实现。与MMP方法相比，这种方法是精确的并且消耗更少的内存。代码在https://sites.google.com/site/xinshiqing/knowledge-share

4. [5]中提出的加热方法。一种实现方式在https://github.com/dgpdec/course这种方法是近似的，需要一个预处理过程。它比快速行军法快。

[1] Joseph S.B.Mitchell、David M.Mount和Christos H.Papadimitriou。1987.离散测地线问题。SIAM J.Comput。16，4（1987年8月），647-668。

[2] Vitaly Surazzky，Tatiana Surazsky，Danil Kirsanov，Steven Gortler，Hugues Hoppe。网格上的快速精确和近似测地线。ACM Trans。图形（SIGGRAPH），24（3），2005年。

[3] 陈，J.和韩，1990年。多面体上的最短路径。InSCG’90：第六届计算几何年度研讨会论文集。ACM出版社，美国纽约州纽约市，360｛369

[4] 石庆信、王国进。2009。改进陈和韩关于离散测地线问题的算法。ACM Trans。图表28，4，第104条（2009年9月），8页。

[5] Crane K，Weischedel C，Wardetzky M.热地学：基于热流计算距离的新方法[J]。ACM图形汇刊（TOG），2013，32（5）：152。

Answer 2

只需在wxnfifth之前的回答中添加一点，即快速行进方法不仅可以单独应用，而且可以作为接收测地线路径的良好近似的第一步，它被迭代改进如下：

1. 组成包含现有路径近似值的三角形条带
2. 在条形图中查找最短路径，这是一项可以在线性时间内精确求解的任务，例如Wolfgang Mulzer的"多边形中的最短路径"方法
3. 如果该路径经过三角形条带边界上的一个顶点，则考虑沿该顶点另一侧的路径，如果该路径较短，则更新条带，并从步骤2重新启动算法

至于实现它的库，可以考虑开源的MeshLib，特别是函数computeSurfacePath。甚至还有一个短视频展示了它在一些样本网格上的工作。

---