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

Question

我试图找到三角表面上两点之间的距离(大地距离)。它看起来像一个基本的操作，并非微不足道。所以我想知道是否有任何图书馆可以做到这一点？我的Google fo失败了，因此，我将不胜感激任何指点。

(我知道CGAL，scipy.spatial，但我在文档中找不到任何内容，如果我错过了那里的内容，请告诉我)

Answer 1

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

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

[1]提出并在[2]中实现的

MMP方法。此方法是精确的，并且代码在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.计算。 16，4(1987年8月)，647-668。

[2] Vitaly Surazhsky，Tatiana Surazhsky，Danil Kirsanov，Steven Gortler，Hugues Hoppe。在网格上快速精确和近似的测地线。 ACM Trans。图形(SIGGRAPH)，24(3)，2005。

[3] Chen J. and Han，Y.1990。多面体上的最短路径。 InSCG '90:第六届年度计算几何专题研讨会论文集。 ACM出版社，美国纽约，360 {369

[4]辛世清和王国国。 2009。改进了Chen和Han的离散测地线算法。 ACM Trans。图形。 28、4，第104条(2009年9月)，共8页。

[5] Crane K，Weischedel C，Wardedtzky M.加热中的测地线:一种基于热流计算距离的新方法[J]。 ACM图形交易(TOG)，2013，32(5):152。