Research > Software > GeodesicPath
GeodesicPath is an application that finds the shortest path between two vertices on a surface. Two types of shortest paths the application can find are the Dijkstra path and the Geodesic path.
GeodesicPath is an application that finds the shortest path between two vertices on a surface. There are two types of shortest paths that can be computed.
Portable java executable make compilation unnecessary.
Installation InstructionsCopy java executable 'jar' file to local disk.
GeodesicPath takes a shape and two vertex indices as arguments and produces a contour that encodes the path between the specified vertices. There are several options for the programs output.
There are two types of shortest paths the application can find. The simpler one is the Dijkstra path, which is constrainted to lie on either the vertices or the edges of the shape. Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weightsThis path is dependent on the shape's parameterization. If the shape is sparsely sampled, then the Dijkstra path may not be the shortest possible path. The alternative path is the true geodesic path to the surface. This path is constrained to lie on the faces of the surface. This path is independent of the shape's parameterization. The geodesic path is computed in an iterative fashion, where the Dijkstra path is the initial path, and segments are added and changed to minimize the length of the path. This means that the geodesic will be a local minimum geodesic.
In general, the Dijkstra method is very fast and usually a very good approximation to the true geodesic. The geodesic method will give a local shortest path, but it's convergence rate depends heavily on the shape's geometry and the starting Dijkstra path.