三角形网格上的测地计算？

Question

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

（我知道CGAL，scipy.spatial的，但我无法找到的文档任何东西，让我知道如果我错过了一些东西在那里）

Answer 1

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

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

由[1]提出并实现的MMP方法[2]。这种方法是准确的，代码在https://code.google.com/p/geodesic/。与Ante的评论相同。缺点是当网格拉伸时，MMP方法会消耗大量的内存，O（n^2），n是顶点的数量。

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

在[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 Surazhsky，Tatiana Surazhsky，Danil Kirsanov，Steven Gortler，Hugues Hoppe。网格上的快速准确和近似测地线。 ACM Trans。 Graphics（SIGGRAPH），24（3），2005.

[3] Chen，J.and Han，Y.1990。多面体上的最短路径。 InSCG '90：第六届计算几何年度研讨会论文集。 ACM Press，New York，NY，USA，360 {369

[4]辛世清王国金。 2009.改进Chen和Han关于离散测地线问题的算法。 ACM Trans。图形。第28条，第4条，第104条（2009年9月），8页。 [5] Crane K，Weischedel C，Wardetzky M.热测量：一种基于热流计算距离的新方法[J]。 ACM Transactions on Graphics（TOG），2013,32（5）：152.

Answer 2

该CGAL包为geodesic shortest paths实现[Xin & Wang]？