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.ShortestPaths
r1.1 - 27 Apr 2005 - 16:26 - Main.guest
topic end
Start of topic |
Skip to actions
---+ Shortest Paths on a TIN Example of Sack and Lanthier's work: [[http://doi.acm.org/10.1145/262839.262984]] See the images on [[http://www.scs.carleton.ca/~lanthier/Research/projects/gis.html][this page of Mark Lanthier]]. * ShortestPathComparison -- a comparison of finding shortest paths using the Sack and Lanthier method and using fast marching methods ---++ Sack and Lanthier * Run Dijkstra on TIN using only paths connecting nodes; weights are euclidian distance * weight * Bad worst-case performance * Add steiner points to TIN edges to allow crossing face; assign weight based on weight of face * Better approximation * Not all paths feasible * Prune edges that are impassible ---++ Current status * Re-implementing approach used by Sack and Lanthier * Will refine for efficiency * Optimize for large TINs * Dijkstra's algorithm requires many nodes to be kept in memory * Find ways to reduce number of vertices in memory * Find shortest path in naive way, then fill in Steiner points only along that path * Find ways to optimize for a streaming representation * Toy example written in Java * TIN with steiner points now displays correctly: <br /> <img src="%ATTACHURLPATH%/stdemo.PNG" alt="Visualize TIN with Steiner points added" width="500" height="445" /> * Shortest path marked in green: <br /> <img src="%ATTACHURLPATH%/spdemo.PNG" alt="Demo of shortest paths visualization" width="472" height="429" /> -- Main.HenryMcEuen - 21 Feb 2005 ---++ Speed up of Dijkstra There is a paper by Ron Gutman called *Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized For Road Networks",presented at ALENEX04. He shows how to pre-compute some shortest paths with a small sample of the nodes, which can then be stored and used to speed up shortest path queries. He found experimentally that it speeds up the query by around ten times. I canot find an electronic copy of it. I do have a paper copy. -- Main.YuanxinLiu - 22 Feb 2005 ---++ Level set methods Sethian and co-authors have used their [[http://math.berkeley.edu/~sethian/Explanations/interface_explain.html][level set methods]] as another approach to approximating shortest paths on terrain. These are a fairly small modification of Dijkstra's on a graph, but give better approximations (and are mathematically well-grounded.) Since a couple of the other teams in the GEO* project are into level set methods, I thought we should know something about them. * [[%ATTACHURL%/KS-geodesic-pnas95.pdf][KS-geodesic-pnas95.pdf]]: Kimmel and Sethian on shortests paths by level sets * [[%ATTACHURL%/SV-unstructured-Pnas97.pdf][SV-unstructured-Pnas97.pdf]]: Sethian & V. level sets on unstructured meshes -- Main.JackSnoeyink - 25 Feb 2005
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
>
ShortestPaths
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