9

I've been scouring the internet for a fast, open-source cost-distance function that I can embed inside my code. The functionality should basically work like the ArcGIS implementation where I can specify a source raster and cost raster and output a cost distance raster. That said, the implementation does not need to be as sophisticated as ArcGIS in that I don't need to necessarily input "rasters" with embedded geo metadata - a signature that takes simple numeric arrays will suffice since I can verify that the data overlaps correctly at the time I call the function.

My specific intent is to calculate the cost-distance to a single point in the center of a 1000 x 1000 cost raster based on a user click, so fast execution is very important.

A C# implementation would be ideal but I'll look at anything that's out there.

Does anyone know of an open-source library that supports this? Thanks for your help!

5

GRASS GIS has a C implementation in r.cost (source, documentation) which uses a min-heap. Alternatively, you could use a graph package like QuickGraph and Floyd-Warshall to compute the cost.

Recent changes in GRASS 6.4 have made r.cost significantly faster, so perhaps performance may be good enough: on my laptop, it takes about 3s for a 1M cell region, or 5s with knight's move enabled. GRASS is a C application, not a drop-in solution for a C# codebase. If you're OK adding to your stack, you could use PyWPS to make calls to GRASS, and then use the result elsewhere in your application.

  • I'm going to be using this in a web application, so my goal is to complete the operation in only a few seconds. I will only ever have a single target cell and a relatively tight max cost-distance (the distance from the center target cell to the edge of the cost raster, assuming a straight line at minimum cost). My tests using ArcMap under these conditions make me think it is possible. Any tips or experience using GRASS in C#? – atogle Aug 5 '10 at 20:58
  • I've updated my question to answer your questions, it started as a comment, but got too long. Hope that helps! – scw Aug 5 '10 at 23:29
  • Thanks scw! This is all great information, but doesn't really get me to where I need to be unless I start porting GRASS code (which I'm not anxious to do). Maybe there are some other raster geeks out there with some tips. I'm going to continue digging into this and I'll post the solution I settle on. – atogle Aug 9 '10 at 12:18
  • Perhaps you can turn to your colleague: azavea.com/research/staff-research-projects/map-algebra ;-) I suggested the GRASS code because its a robust and fast implementation, C# is relatively new to the geoprocessing space, so preexisting implementations may be difficult to come by. – scw Aug 9 '10 at 19:05
  • scw - that's where my journey started, actually. My problem is that his implementation sacrifices processing time for high-quality calculations. We're working now on an algorithm to do the opposite. GRASS is a great suggestion, I just don't have a way of actually making use it. =) – atogle Aug 16 '10 at 15:31
3

I have use the r.cost function in GRASS a lot. 1000 * 1000 grids were no problem on a normal laptop. There is also a R package (gdistance, http://r-forge.r-project.org/projects/gdistance/) under development. I found GRASS a lot faster.

0

This is able to find the shortest path across an int array.... written in C#. Seems to be working fine on my laptop with 4000,4000 arrays, might be worth a look.

http://www.codeproject.com/Articles/9040/Maze-Solver-shortest-path-finder

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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