| Least Cost Path using Dijkstra's Algorithm [message #72978] |
Thu, 21 October 2010 06:03  |
![Bill[1] is currently offline](theme/default/images/xoffline.png.pagespeed.ic.XRkd1fkXye.png "Bill[1] is currently offline")
Bill[1]
Messages: 2
Registered: October 2010
|
Junior Member |
|
|
I would like to take a raster, which represents the "cost" of moving
through that pixel, and find the shortest path (i.e. least cost path)
through that raster. For example, using geospatial analysis and
several layers of data, this can often be used to model cross country
mobility with each raster cell represent the ease or difficulty of
moving through that cell.
Has any written an IDL program that does a least cost path from a
starting cell to an ending cell using Dijkstra's Algorithm?
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
It's a simple concept but can be very memory intensive depending on
the size of your raster, in my case could easily be 20,000 samples by
20,000 lines.
Thanks for your help. I am new to IDL so was looking for a jump start.
|
|
|
|
|
|
| Re: Least Cost Path using Dijkstra's Algorithm [message #73093 is a reply to message #72978] |
Fri, 22 October 2010 06:25  |
ben.bighair
Messages: 221
Registered: April 2007
|
Senior Member |
|
|
On 10/22/10 8:15 AM, David Fanning wrote:
> Bill writes:
>
>> Hopefully, speed. Is there a reason why I shouldn't?
>>
>> Currently, this is something typically accomplished with a GIS
>> package, such as ArcGIS. Hopefully, sometimes these processes are
>> painfully slower than they need to be. I work with a colleague that
>> did this in MatLab. I would like to go it with IDL, so I can
>> integrate this into ArcGIS.
>
> I think the chances of implementing this algorithm in
> anything other than a "painfully slow" way in IDL
> are slim and none. Too many necessary FOR loops, probably.
>
Hi,
I don't want to be contrary, but I wouldn't be too quick to dismiss IDL
in general regarding the algorithm. It isn't that hard to code up the
necessary search and nodes. IDL might do just fine.
But the size of the specific problem looks pretty daunting. I'm still on
the early side of my coffee, but a 20000 x 20000 single precision array
is about 1.6 GB isn't it? Yikes!
Ben
|
|
|
|
| Re: Least Cost Path using Dijkstra's Algorithm [message #73097 is a reply to message #72978] |
Fri, 22 October 2010 05:15 |
David Fanning
Messages: 11724
Registered: August 2001
|
Senior Member |
|
|
Bill writes:
> Hopefully, speed. Is there a reason why I shouldn't?
>
> Currently, this is something typically accomplished with a GIS
> package, such as ArcGIS. Hopefully, sometimes these processes are
> painfully slower than they need to be. I work with a colleague that
> did this in MatLab. I would like to go it with IDL, so I can
> integrate this into ArcGIS.
I think the chances of implementing this algorithm in
anything other than a "painfully slow" way in IDL
are slim and none. Too many necessary FOR loops, probably.
Cheers,
David
--
David Fanning, Ph.D.
Fanning Software Consulting, Inc.
Coyote's Guide to IDL Programming: http://www.dfanning.com/
Sepore ma de ni thui. ("Perhaps thou speakest truth.")
|
|
|
|
| Re: Least Cost Path using Dijkstra's Algorithm [message #73140 is a reply to message #72978] |
Mon, 25 October 2010 17:19 |
James[2]
Messages: 44
Registered: November 2009
|
Member |
|
|
I recently programmed the Fast Marching Method (
http://math.berkeley.edu/~sethian/2006/Explanations/fast_mar ching_explain.html
) as an external C program for IDL. The Fast Marching Method is the
continuous version of Dijkstra's algorithm: it simulates a boundary
moving through space monotonically with speed as a function of
position. The pixel/voxel grid is considered a sampling of the
continuous speed function.
You can find least cost paths by initializing the boundary at a single
point and then backtracking from the destination(s) through the
arrival time field using gradient descent. This will give you
interpolated points that might not be at exact grid points (pixels),
but it sounds like that's what you want. The algorithm is O(n lg n)
where N is the number of pixels, just like Dijkstra's.
Anyway, if this sounds interesting to you, I can send you the C code
and the IDL wrapper function. You can compile it with MAKE_DLL. I
optimized my implementation for sparse data sets (where the speed is 0
in most places), so if you want to travel through the entire
20000*20000 array, it will be slow. I might be persuaded to write a
non-sparse version if your application is interesting enough ;-)
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
