Geodätische Berechnung auf Dreiecksnetzen?

Question

Ich versuche den Abstand zwischen zwei Punkten auf einer triangulierten Oberfläche zu finden (geodätischer Abstand). Es sieht wie eine grundlegende Operation aus und ist nicht trivial. Ich frage mich, ob es Bibliotheken gibt, die das tun? Mein Google FO ist fehlgeschlagen, daher würde ich alle Hinweise sehr schätzen.

(ich bin mir dessen bewusst CGAL, scipy.spatial, aber ich konnte nichts in der Dokumentation finden, lassen Sie mich wissen, ob ich da etwas verpasst)

Answer 1

Es gibt viele Implementierung sind für die Berechnung geodätischen Abstand auf Dreiecksnetz . Einige sind ungefähre und einige sind genau.

1.Fast Marching-Methode. Diese Methode ist ungefähr und in der Praxis liegt der durchschnittliche Fehler unter 1%. Sie können sich auf Gabriel Peyres Implementierung der Fast-Marching-Methode in Matlab beziehen. http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

2. MMP Methode vorgeschlagen durch [1] und umgesetzt in [2]. Diese Methode ist genau und der Code ist in https://code.google.com/p/geodesic/. Genauso wie der Kommentar von Ante. Ein Nachteil ist, dass, wenn das Netz large ist, die MMP-Methode viel Speicher verbrauchen wird, O (n^2), n ist die Anzahl der Vertices.

3. CH-Methode vorgeschlagen in [3] und verbessert und implementiert in [4]. Diese Methode ist genau und verbraucht weniger Speicher als die MMP-Methode. Der Code ist in https://sites.google.com/site/xinshiqing/knowledge-share

4. Wärme-Methode in [5] vorgeschlagen. Eine Implementierung ist in https://github.com/dgpdec/course Diese Methode ist approximiert und erfordert einen Vorverarbeitungsprozess. Es ist schneller als Fast Marching-Methode.

[1] Joseph S. B. Mitchell, David M. Berg, und Christos Papadimitriou. 1987. Das diskrete geodätische Problem. SIAM J. Comput. 16, 4 (August 1987), 647-668.

[2] Vitaly Surazhsky, Tatjana Surazhsky, Danil Kirsanow, Steven Gortler, Hugues Hoppe. Schnelle exakte und ungefähre Geodäten auf Netzen. ACM Trans. Graphics (SIGGRAPH), 24 (3), 2005.

[3] Chen, J. und Han, Y.1990. Kürzeste Wege auf einem Polyeder. InSCG '90: Proceedings des sechsten jährlichen Symposiums über Computational Geometry. ACM Presse, New York, NY, USA, 360 {369

[4] Shi-Qing Xin und Guo-Jin Wang. 2009. Verbesserung von Chen und Han's Algorithmus für das diskrete geodätische Problem. ACM Trans. Graph. 28, 4, Artikel 104 (September 2009), 8 Seiten.

[5] Kranich K, Weischedel C, Wardetzky M. Geodäsie in Wärme: ein neuer Ansatz zur Berechnung der Entfernung basierend auf Wärmefluss [J]. ACM Transactions on Graphics (TOG), 2013, 32 (5): 152.

Answer 2

Das CGAL-Paket für geodesic shortest paths implementiert [Xin & Wang]?