# Find the best path along raster

I've just posted a question to StackOverflow about the best way to go about finding the best path on the raster below (where whiter pixels are 'better'), but have realised that it might actually be very easy to solve using some inbuilt GIS functions. To clarify, I'm trying to choose the best path down each of the lines shown in the image, staying on the bright white pixels as much as possible.

I have a feeling that the idea of Cost Surfaces and Cost Paths might help me with this, but I've had a play in ArcGIS and can't seem to get anything sensible out of it. Is this the right approach to take within a GIS? If not, are there some other inbuilt functions in a GIS that can do this kind of thing?

-

## 4 Answers

In terms of premade GIS, there's a bunch of stuff out there for travel costs on raster surfaces, e.g. r.cost, r.walk (different costs for uphill vs downhill!)

If you prefer brewing up code yourself so you know the exact algorithm:

http://stackoverflow.com/questions/2311486/how-to-calculate-the-shortest-path-between-two-points-in-a-grid

-

If you're okay with some algorithm programming then a pathfinding algorithm is a good option. A* would work if you have a desired destination, if not Dijkstra would do well. Assign lower costs to brighter pixels. If you're looking for speed, though, it might not be the best option.

-
+1. For this particular application, Dijkstra would be extremely fast, because--with reasonable choices of costs--most of the black cells would never even be visited. – whuber Dec 4 '10 at 19:07

I'd try something like this (example given in GRASS but the steps are similar for other software):

• Identify the source locations. One technique: mask the raster to the start row and filter the raster by value.
• Identify the destination points: in this case, select just the bottom row, and convert the results to vector points, then convert this 'end' raster to vector points.
• Compute the cost distance for the surface, using something like r.cost, using the computed start and end point datasets, and making the cost path raster scaled appropriately.

This does the above, skipping over the masking operations:

``````# identify start points, dump to raster
r.mapcalc start_rast='if(MASK && map > 100, 1, null())'

# identify the end points and convert to vector
r.mapcalc end_rast='if(END_MASK && map > 100, null())'
r.to.vect in=end_rast out=end_pts

r.cost -k in=raster_to_analyze start_rast=start_rast end_points=end_pts
``````

Depending on what you're trying to do, this may be sufficient, or may require iteration over your start points to get multiple 'shortest cost' rasters.

-

Using ArcScan is the quickest way - http://www.esri.com/software/arcgis/extensions/arcscan/automatic-vectorization.html

Converts Raster pixels to vector lines and the length can be applied giving you the best path.

Note: You might need to inverse your image to 2 colour bitmap so the white pixels become black and vectorisation can be best applied.

-
I don't think this is such a great answer... I assume that, in general, the poster isn't after 'best paths' that follow well-defined lines, but instead a best path across some arbitrary grid of travel costs. – Dan S. Dec 3 '10 at 23:13
It's not quite the right solution to my problem...but it is a VERY useful tool to know about. In fact, it's solved another major problem I've been struggling with - so +1 for that :-) Also, I think it will be useful once I've done some other processing on this problem. – robintw Dec 3 '10 at 23:36
I voted this down because it's not useful to have a wrong answer as one of the top-rated answers to this questions. Maybe robintw or Mapperz can post the question this would answer as a new question and move this answer there. – Sean Dec 4 '10 at 20:49
It was a suggested answer to find the best route - the OP was open to all suggestions, if stated only a raster solution then would not of suggested it. – Mapperz Dec 6 '10 at 0:10
Could you perhaps explain in what sense the ArcScan solution is a "best" route? Also--I'm not familiar with ArcScan--what guarantee do you have that it will actually create connected routes from top to bottom? – whuber Dec 6 '10 at 14:53