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
  • 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:
  

• 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.

• KS-geodesic-pnas95.pdf: Kimmel and Sethian on shortests paths by level sets
• SV-unstructured-Pnas97.pdf: Sethian & V. level sets on unstructured meshes

-- JackSnoeyink - 25 Feb 2005
to top