SM_PATH
Computes shortest path between given source and target vertex. Dijkstra's method is used for finding approximate shortest path while MMP method is used for finding exact shortest path. A-star heuristic is used to guide the algorithm to find the target faster. The output of the algorithm is a text file containing a sequence of points corresponding to the shortest path between the source and the target.
Note: To minimize the time required to find the exact shortest path, this code does not maintain the inner frontier queue described in Section 3.4 of
http://www.cs.unc.edu/~verma/shortest_path.pdf.
Example Usage:
General
Usage:
sm_path -i input_mesh -reorder|reorder_prune reordered_file -s source_coordinates -t target_coordinates -exact
-path output_path.txt
-exact
When the -exact flag is specified the code runs MMP algorithm to find the exact shortest path. If this flag is not specified, Dijkstra's algorithm is run to find an approximate shortest path
reorder|reorder_prune reordered_file.smb
To reduce the memory requirement when finding the exact shortest path, the -reorder or -reorder_prune argument can be specified. If the -reorder argument has been specified the whole mesh is reordered and output to the given file argument. If -reorder_prune argument has been provided, only the part of the mesh relevant to shortest path computation is reordered and output to the given file argument.
-s source_x source_y source_z -t target_x target_y target_z
The -s argument is used to specify the coordinates of the source vertex, while -t argument is used to specify the coordinates of the target vertex. The source and target vertices are chosen to be those vertices of the mesh which are closest (in a Euclidean sense) to the specified coordinates.
Example
sm_path -i input_mesh.smb -s 0.0 34.52 12.2 -t 100.1 63.2 14.5 -path dijk_path.txt
The above command computes an approximation to the shortest path from the source vertex to the target vertex using Dijkstra's method. The shortest path is output to dijk_path.txt as a sequence of points. Source is chosen to be the vertex of the mesh closest to 0.0 34.52 12.2, while the target is chosen to be the vertex of the input mesh closest to 100.1 63.2 14.5 .
sm_path -i input_mesh.smb -s 0.0 34.52 12.2 -t 100.1 63.2 14.5 -path path.txt -exact -reorder_prune reordered_mesh.smb
The above command computes the exact shortest path from the source vertex to the target vertex using MMP method. First the input mesh is reordered and pruned and output to reordered_mesh.smb. The MMP algorithm is run on this reordered mesh for lower memory usage. The shortest path is output to path.txt as a sequence of points. Source is chosen to be the vertex of the mesh closest to 0.0 34.52 12.2, while the target is chosen to be the vertex of the input mesh closest to 100.1 63.2 14.5 .
sm_path -i input_mesh.smb -s 0.0 34.52 12.2 -t 100.1 63.2 14.5 -path path.txt -exact -reorder reordered_mesh.smb
The above command computes the exact shortest path from the source vertex to the target vertex using MMP method. First the input mesh is reordered (but not pruned) and output to reordered_mesh.smb. The MMP algorithm is run on this reordered mesh for lower memory usage. The shortest path is output to path.txt as a sequence of points. Source is chosen to be the vertex of the mesh closest to 0.0 34.52 12.2, while the target is chosen to be the vertex of the input mesh closest to 100.1 63.2 14.5 .
sm_path -i input_mesh.smb -s 0.0 34.52 12.2 -t 100.1 63.2 14.5 -path path.txt -exact
The above command computes the exact shortest path from the source vertex to the target vertex using MMP method. The MMP algorithm is run on the unordered input mesh and can result in higher memory usage. The shortest path is output to path.txt as a sequence of points. Source is chosen to be the vertex of the mesh closest to 0.0 34.52 12.2, while the target is chosen to be the vertex of the input mesh closest to 100.1 63.2 14.5 .
--
VishalVerma - 29 Dec 2008