The algorithm used is Dijkstra (A* is used for more specialized purposes of one vertex to one other specific vertex), but that is not the whole story. To reduce the impact of the mesh triangulation on the result, we not only use edge-neighbors, we also take every pair of edge-connected triangles, and include another "neighbor" resulting from finding the shortest path between the far vertices in the two-triangle system (unless that path follows the edges, due to unusual angles). This is the difference between the default and "naive" methods. As such, it gives much more accurate distances, while still using simple Dijkstra code, and is basically the same speed as the naive version.
But, there is yet another wrinkle: when using group-average surfaces, there is much less folding definition, and therefore less surface area, and these make the distances between vertices artificially shorter than they are in the contributing subjects. We have an approximate correction for this change to the distances, by comparing the vertex areas (one third of the area of each triangle using the vertex) of the group average surface, to the group average of the vertex areas of the individual surfaces. This correction gets applied to all of the graph's edge lengths independently (including the 2-triangle-crawled extra "neighbors"), before Dijkstra or A* get run (and yes, I do tweak the A* euclidean distance heuristic by the minimum distance correction ratio, in case it anomalously said that an edge got shorter). It is not clear how to do a similar correction to exact geodesic distance code, as exact geodesic distance methods seem like they must require explicit geometry in 3-space, while Dijkstra applies to arbitrary graphs with positive edge lengths, even if they violate the triangle inequality, giving us much more freedom to tweak things. The original reason we didn't use an exact method is that an exact method is complicated and slower (the paper I previously looked at specifically started with Dijkstra to provide a heuristic to speed up the exact algorithm for the single destination case). Tim On Wed, Jun 13, 2018 at 10:11 AM, Stefan Pszczolkowski < [email protected]> wrote: > Hello > > I would like to ask what is the underlying method employed for computing > geodesic distances in the -surface-geodesic-distance Workbench command. > Is it simply a Dijkstra approximation? or something more sophisticated > like the exact algorithm of [1]? > > I have had a quick look at the code and I found methods like "dijkstra" > and "aStar", but I quickly realised that is probably better to ask here :) > > Thank you very much! > > [1] MITCHELL, J.S.B.,MOUNT, D.M., AND PAPADIMITRIOU, C. H. 1987. The > discrete geodesic problem. SIAM J. of Computing 16(4), 647–668. > > -- > Stefan Pszczolkowski P. Ph.D. > Research Fellow > > Radiological Sciences > Division of Clinical Neuroscience > Room B115-117, School of Medicine > University of Nottingham > Queen's Medical Centre, Derby Road > Nottingham > NG7 2UH > Tel: 44 (0) 115 748 4389 > Website: https://stefanpsz.github.io/ > > > > > This message and any attachment are intended solely for the addressee > and may contain confidential information. If you have received this > message in error, please contact the sender and delete the email and > attachment. > > Any views or opinions expressed by the author of this email do not > necessarily reflect the views of the University of Nottingham. Email > communications with the University of Nottingham may be monitored > where permitted by law. > > > > > _______________________________________________ > HCP-Users mailing list > [email protected] > http://lists.humanconnectome.org/mailman/listinfo/hcp-users > _______________________________________________ HCP-Users mailing list [email protected] http://lists.humanconnectome.org/mailman/listinfo/hcp-users
