Shortest Paths on a TIN
Example of Sack and Lanthier's work:
http://doi.acm.org/10.1145/262839.262984
See the images on
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
- 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:
- Shortest path marked in green:
--
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.
--
YuanxinLiu - 22 Feb 2005
Level set methods
Sethian and co-authors have used their
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.
--
JackSnoeyink - 25 Feb 2005
to top