Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.Sm_path
r1.1 - 31 Dec 2008 - 17:11 - Main.guest
topic end
Start of topic |
Skip to actions
*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. %TOC% ---+++Example Usage: ------------------------------------- ---++++General Usage: <pre> sm_path -i input_mesh -reorder|reorder_prune reordered_file -s source_coordinates -t target_coordinates -exact -path output_path.txt </pre> =-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 <pre> sm_path -i input_mesh.smb -s 0.0 34.52 12.2 -t 100.1 63.2 14.5 -path dijk_path.txt </pre> 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 . <pre> 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 </pre> 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 . <pre> 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 </pre> 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 . <pre> sm_path -i input_mesh.smb -s 0.0 34.52 12.2 -t 100.1 63.2 14.5 -path path.txt -exact </pre> 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 . --- -- Main.VishalVerma - 29 Dec 2008
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
Sm_path
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback