7

What sort of algorithms can I use to find a least cost path through a DEM where it costs more to traverse a cell going downhill or uphill than it does to follow the contour of the land?

All the examples I've seen involve creating a least cost surface where the magnitude of the slope is part of the cost - but the direction isn't.

Additionally, the examples assume the cost to travel through a cell does not depend on the direction of travel.

Improve this question
9
  • 3
    Have you reviewed the ArcGIS PathDistance command for Spatial Analyst? If you're interested in algorithms rather than just software, it may help to notice this is an example of a Calculus of variations problem. In fact, by introducing a third dimension to represent all possible orientations at each point (the circle bundle over the region of interest), this becomes a least-cost problem within a 3D space (which can be gridded into voxels for a raster-based solution).
    – whuber
    Commented Apr 19, 2012 at 22:52
  • 1
    +1 even if you are not using ArcGIS (you don't say), the ESRI explanations that whuber points you towards are a great overview from which you can work out how to do it in some other application.
    – MappaGnosis
    Commented Apr 20, 2012 at 8:30
  • 1
    @whuber Thanks, I overlooked the vertical cost component in the PathDistance. If I run into bugs with the PathDistance it would be nice to have an algorithm for Plan B. Although the Calculus of variations is a bit over my head. It mentions "functionals" ... does that imply I could use functional programming and not have to worry about learning the math?
    – Kirk Kuykendall
    Commented Apr 20, 2012 at 15:01
  • LOL! That's a nice example of a collision of technical terms in GIS. In mathematics, the term "functional" is usually used for a function whose domain itself consists of functions. (The Riemann integral is a good example: it assigns a number to real-valued functions.) When you find an optimal corridor for a pipeline, your functional assigns a "score" or "value" to any possible route. Because a route would be described as a path--that is, assignment of a point in space to the interval of times needed to traverse that route--"functional" is apt.
    – whuber
    Commented Apr 20, 2012 at 15:16
  • 1
    @whuber Thanks. I think I'll stick with PathDistance, and remain functionally illiterate for the time being.
    – Kirk Kuykendall
    Commented Apr 20, 2012 at 15:45

1 Answer 1

Reset to default
2

The ArcMap Path Distance tools can do this, although it's moderately complex. Specifically, you need to use the horizontal and vertical factors. This looks at the aspect/elevation to figure out whether it's going uphill, downhill, or parallel to the slope, and assigns a different weight to each direction of approach.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.