Hot answers tagged cost-path
4
A possible solution would be to use postgresql, postgis, pgrouting and osm2pgrouting.
Insert your fixed locations in a postgis database.
Insert the real road network in your database for the area that you need with an import of OSM data using osm2pgrouting.
Optional: find the closest point on your road network from the user defined location.
Use pgrouting ...
4
As @dassouki said, the Network Analyst solution could be suitable here, if you specify connectivity groups.
In your case the overpass and underpass would be in separate connectivity groups, so it would not be possible to traverse between them. (In cases where there are stairs, you can allow pedestrians to change elevations.)
In terms of allowing ...
3
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 ...
3
Julie,
The question you have asked is non-trivial. I can't speak from experience on how ArcGIS handles least cost paths on a raster, because I haven't played around with it. But if you want to use a strictly raster approach, then you are correct in your assumption that you will need to model the over/under for bridges and tunnels.
The other major issue ...
2
It looks like the Google Maps API has a service for this:
http://code.google.com/apis/maps/documentation/javascript/distancematrix.html
Limit of 25 destinations, though.
You might also be able to leverage the api form http://www.mapnificent.net/, though it's based on public transportation.
2
You say you are a "Excel tinkerer". "Mapping" in Excel is possible to some extent. I once saw a very involved Excel dashboard application that used a line chart to plot out boundaries of a study area and then VBA to determine what portion of the study area a given point was located within - all based on X\Y locations of both the study are line vertices and ...
2
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.
2
You want to favor edges that are "close" to the line segment joining the endpoints of the path (its "axis," let's say). One direct way to do this is to weight the edges accordingly. How you weight them will determine what kind of path is "nicest." Just make sure that edges further from the axis get proportionately greater weight.
As an illustration, I ...
1
For the first problem, you might want to check out line rasterization algorithms. Bresenham's algorithm , which @whuber mentioned, is one of them. This is so because your nodes, with their von Neuman neighborhoods, can be treated as the center of a raster cell. Your "nice" path requirement is also similar to the raster approximation of a line.
Below is an ...
1
This is very similar to what our output looks like from the path distance tool incorporating a dem, vertical raster, and vertical factor specification (which is basically what you are trying to do with your resistance layer but it differentiates between uphill and downhill movement). It may just be what's expected given your elevation range and resistance ...
1
You can use the A* search algorithm using slope as the cost between generated nodes. To see a quick visualization of what that looks like:
See A* Search Algorithm (Wiki)
and
Python A* Search Algorithm (SO)
to understand A*.
For a slope map there are options out there - Here is one.
With a slope map (raster) you can get cost values out of it with GDAL.
1
I found an article called Calculate distance in Google spreadsheet that may be of use.
It would take some tweaking to do exactly what you want, I think -- and Google's daily API caps could hinder you, but it's an interesting approach.
1
You might try to treat this as an indoor GIS problem.
Implementing Dijkstra Shortest Route for 3D Indoor Navigation System
It's not exactly brain surgery - but it's close.
Only top voted, non community-wiki answers of a minimum length are eligible
