三角形網格上的測地計算？

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]？