Exact geodesic for triangular meshes

Geodesic (shortest path) algorithm for triangular mesh (triangulated 2D surface in 3D).

Description

This is an implementation of exact geodesic algorithm for triangular mesh (first described by Mitchell, Mount and Papadimitriou in 1987) with some minor improvements, extensions and simplifications. The algorithm has O(n^2 \log n) worst-case time complexity, but in practice can work with million-node meshes in reasonable time. For the quick overview, see J. O'Rourke, "Computational Geometry Column 35", SIGACT News, 30(2) Issue #111.

• MATLAB release: MATLAB 6.5 (R13)

[Danil Kirsanov]

C++ code could be downloaded from
http://code.google.com/p/geodesic/downloads/list

[Jeff Jiang]

It looks a very nice contribution. I just tried examples, but it failed with long error message from mathwork basically saying "Segmentation violation detected ..."

[Danil Kirsanov]

yeap, my code has an issue with matlab 2007b. I am currently testing the fix, so let me know if you need it immediately.

[Gwenael Birot]

Thanks for this nice contribution. It works perfectly. I built the linux 32 and 64 bits shared library geodesic_matlab_api from the c++ code. It would be great to add them in this contribution...

[Paolo de Leva]

Good job. Contains five detailedly commented examples. Works perfectly after bug fixes (3 Mar 2008).

[RENOO Laborbe]

I am trying to run this code on linux 64bits. How did you compile the code geodesic_matlab_api ? I haven't see any makefile in the source code directory.
Thank you

[Danil Kirsanov]

I did not test the library on linux at all, but if I understand it correctly (and I might be wrong), you need to install BOOST, and create a shared library from geodesic_matlab_api.cpp.
Watch out for the compiler messages though -- from what I see now, you might have to put -1.0 instead of -1 on line 167 of geodesic_matlab_api.cpp for this file to work correctly.

[Hassan Radvar-Esfahlan]

Hi Danil and thanks for sharing this code. Actually i use Matlab (R2009a). for example 1 this error occured:
??? Error using ==> calllib
Pointer type must match data type

Error in ==> geodesic_distance_and_source at 19
    [num_vertices, d, s] = calllib(geodesic_library, 'distance_and_source_for_all_vertices',
    algorithm.id, tmp, tmp1);

Error in ==> example1 at 26
[source_id, distances] = geodesic_distance_and_source(algorithm);
approximately the same errors for example 3 and 5 but works very nice for examples 2 and 4.

[fraisa1985 Youssef]

hello,
please how i can use this implementtation to find the geodesic distance between two points for 3D face with triangular mesh

[David]

Segmentation violation error occurs when applied to some tri-mesh. This error is usually caused by memory leakage, it would be a nice contribution if the error can be fixed.

[carmi]

Thanks for the submit - to fix the "Pointer type must match data type", change int32PtrPtr to longPtrPtr in line 17 of file "geodesic_distance_and_source.m".

[dai zhengguo]

carmi, thanks for your note

[nicodhidt]

Thanks for the code. I have problems trying to run it under Win7 64 bits with a 64bits Matlab version also. It says "Microsoft Visual C++ 2005 or 2008 is required to use this feature." While loading a library. I've installed the runtime libraries from visual studio but it didn't work. Any idea?