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.ShortestsPaths
r1.1 - 18 Dec 2008 - 05:49 - Main.guest
topic end
Start of topic |
Skip to actions
*Shortest path algorithms and simplification* We run the shortest path algorithms described in http://www.cs.unc.edu/~verma/shortest_path.pdf on simplified meshes and look at the effect of simplification on the length of these shortest paths. We consider the mesh 055_mesh.smb at two different levels of simplification: 1% and 0.5%. We then run the Dijkstra's and the MMP algorithm with A-star heuristics on these meshes. Note that the source and target can shift a little after simplification and thus cause minor changes in the length of the shortest paths. The following is the output generated by MMP algorithm on the 1% simplified mesh * 01percent.JPG: <br /> <img src="%ATTACHURLPATH%/01percent.JPG" alt="01percent.JPG" /> The length of this path is 276.429. Peak memory requirement was 64 mb and it took 4.7 seconds. The input mesh was ordered using !Dijkstra's method iwth A-star heuristics. Reordering took 12 secs and had a peak memory usage of 294mb. The length of the !Dijkstra's shortest path was 288.88. --- The following is the output generated by MMP algorithm on the 0.5% simplified mesh * 005percent.JPG: <br /> <img src="%ATTACHURLPATH%/005percent.JPG" alt="005percent.JPG" width="1026" height="767" /> The length of this path is 281.83. Peak memory requirement was 28mb and it took 1.86 seconds. The input mesh was ordered using !Dijkstra's method iwth A-star heuristics. Reordering took 3.2 secs and had a peak memory usage of 147mb. The length of the !Dijkstra's shortest path was 291.087. --- It can be noticed that the two paths are qualitatively and quantitavely very similar. However, it is possible that on simplification the shortest path changes qualitatively but their length will remain close. --- -- Main.VishalVerma - 17 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
>
ShortestsPaths
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