Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 5 down vote favorite
2

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!

share|improve this question

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
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
up vote 2 down vote

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.

share|improve this answer
up vote 0 down vote

Hej,

I am also looking for a cost distance algorithm I can use with python:

I have a numpy array (extracted from arcgis) which represents a rastarized river (river=1, else=nodatavalue) and I have a point shape file which is the startpoint. I want now to calcutlate how far each rastercell (rivercell) is away (distance) from the given point. It is possible to calculate with the ArcGIS-CostDistance tool, but is there also a native python/numpy/scipy way?

thanks /j

share|improve this answer
up vote 0 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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