jas*_*son 7 graphics scipy computer-vision cgal computational-geometry
我试图找到三角形表面上两点之间的距离(测地距离).它看起来像一个基本的操作,并不是微不足道的.所以我想知道是否有任何库可以做到这一点？我的谷歌失败了,所以我非常感谢任何指针.
(我知道CGAL,scipy.spatial,但我在文档中找不到任何内容,如果我错过了某些内容,请告诉我)
小智 9
在三角形网格上计算测地距离有许多实现.有些是近似的,有些是精确的.
1.快速行进方法.该方法是近似的,实际上平均误差低于1%.你可以参考Gabriel Peyre在matlab中快速行进方法的实现. http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching
MMP方法由[1]提出并在[2]中实现.此方法准确无误,代码位于https://code.google.com/p/geodesic/ .与Ante的评论相同.缺点是当网格是larege时,MMP方法会消耗大量内存,O(n ^ 2),n是顶点数.
[3]中提出的CH方法,并在[4]中进行了改进和实现.这种方法比MMP方法精确且消耗更少的内存.该代码位于https://sites.google.com/site/xinshiqing/knowledge-share中
[5]中提出的加热方法.一个实现在https://github.com/dgpdec/course中. 此方法是近似的,需要预处理过程.它比Fast Marching方法快.
[1] Joseph SB 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.图形(SIGGRAPH),24(3),2005.
[3] Chen,J.和Han,Y.1990.多面体上的最短路径.InSCG '90:第六届计算几何年度研讨会论文集.ACM Press,纽约,纽约,美国,360 {369
[4]施世庆和王国进.2009.改进Chen和Han的离散测地问题算法.ACM Trans.图形.28,4,第104条(2009年9月),8页.
[5] Crane K,Weischedel C,Wardetzky M. Geodesics in heat:一种基于热流计算距离的新方法[J].ACM图形交易(TOG),2013,32(5):152.