I have added functions (in geodesics.py) to compute the distance maps to a set of points. For that I use networkx and gdist. Note that for large mesh and large set of points it is recommended to use Dijkstra distance (with length attached to each edge of the graph) because it is:
1) much faster than gdist
2) less precise but the correlation with gdist is very close and the percentage of error is quite low
The idea is due to Maxime Dieudonné:
1) compute a distance map for each point of the set and
2) compute the min of the distance maps, for each point of the graph.
In terms of complexity, it it O( N log(N) k ) where k is the size of the set. Of course if it possible to do better (remove the k) but it would require to recode gdist or networkx. So it remains tractable for k not more than 1000 vertices in the set (it takes 12 min for a mesh with 120k vertices, about 3 to 5 times more with gdist).
A new test_geodesics.py file with simple examples: a rectangular grid and the set of point is one the side, so you expect the maximal distance is given by the length of the other side.
pep8 corrected as much as possible (there was a "trailing whitespace" error I was not able to correct).
Hello,
Contributions:
The idea is due to Maxime Dieudonné:
1) compute a distance map for each point of the set and 2) compute the min of the distance maps, for each point of the graph.
In terms of complexity, it it O( N log(N) k ) where k is the size of the set. Of course if it possible to do better (remove the k) but it would require to recode gdist or networkx. So it remains tractable for k not more than 1000 vertices in the set (it takes 12 min for a mesh with 120k vertices, about 3 to 5 times more with gdist).
A new test_geodesics.py file with simple examples: a rectangular grid and the set of point is one the side, so you expect the maximal distance is given by the length of the other side.
pep8 corrected as much as possible (there was a "trailing whitespace" error I was not able to correct).