Hi Jess, As Paul said, the key is the data. If you got the ESRI data for California you would load it into your chosen database-presumably PostGIS :-)
If the data were in Shapefile format (or many other formats) you could use the ogr2ogr program to read the shapefiles and load the data into PostGIS. Here is the ogr2ogr page: http://www.gdal.org/ogr/ogr2ogr.html Ogr2ogr is also part of the precompiled FWTools toolkit: http://fwtools.maptools.org/ Versions are precompiled for Linux, Windows, and OSX. The road/bicycle path data will now be in your database in the form of a 'graph' -> that is, there will be vertices and edges, or 'intersections' and 'roads.' Road routing is computationally the same as routing ip packets-see this wikipedia page: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm (at least, look at the first two paragraphs) Dijkstra's algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights. For example, if the vertices of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities. The 'weights' are your assertions of the relative 'costs' of each road segment. For example, a segment on the freeway is (usually) faster than a segment of the same length on the surface streets, and so the 'weight' of the freeway segment is lower. Routing then becomes the task of finding the series of edges which connect the two vertices (er, intersections :-) of interest with the lowest total weight. Assuming you had a reasonable road network of roads which were all legal for bicycles you could then assign weights to each road segment in (inverse) proportion to how desirable that section of road is for cycling. One of the aspects of 'desirability' could of course be the change in elevation, which you can get by comparing the location of each intersection with elevation data (like the Digitial Elevation Model, or DEM, data). In theory, the Dijkstra algorithm works on directed graphs, that means you can go from point A to B, but not from B to A (or if you can go from B to A that is considered a different 'edge' which can have a different weight, so the uphill direction would have a higher weight, and the downhill direction would have a lower weight.). (you should probably ignore elevation change in routing, at least until you have the rest of the system working the way you'd like). Having the data in PostGIS you can then install the pgdijkstra module, and aside from a few details, you'll be set. (it would be very cool to allow community weighting of segments, a Digg for selecting good routes). Regards, Rich On 5/3/07, jessica forbess <[EMAIL PROTECTED]> wrote:
On 5/3/07, Paul Ramsey <[EMAIL PROTECTED]> wrote: > > On 3-May-07, at 12:19 PM, jessica forbess wrote: > > > The PGDijkstra routing engine mentioned is interesting. And the > > pgRouting that is based on it. I haven't looked at those closely, but > > I just thought I'd see if anyone here knew of a good place to start, > > given my goal is open source routing for bicycles. > > The key is not so much software as data. What distinguishes bike > routing from car routing? Knowing what existing automotive roads are > good to bike, and knowing supplementary information about connections > (bike paths, cut throughs, walkways) are available to bikes that are > not available to cars. Without that, the routing software is moot. California is releasing ESRI data regarding official bike lanes, paths and wide shoulders. I believe Oregon is as well. How does one pull that data into a routing database? I don't know, but it was done for cars, and is still being refined for them, so I can do it for bicycles. Other sites like bikely.com may supply useful data (probably after significant massaging). That site allows users to store bike routes either by uploading gps tracks or just clicking on the map a la gmap pedometer. Not so easy to take that to a routing database, but a stepping stone. A similar site dedicated to collecting data for routing could be set up. I'm also curious how one could integrate topography information with a routing database to take hills into account. Obviously one can't do the whole world immediately, but one can start in SF/Boston/Austin and expand. (Places I've lived and/or biked.) jess > > P > _______________________________________________ > Geowanking mailing list > [email protected] > http://lists.burri.to/mailman/listinfo/geowanking > _______________________________________________ Geowanking mailing list [email protected] http://lists.burri.to/mailman/listinfo/geowanking
-- Now offering training and consulting in maximizing corporate efficiency using Web 2.0 tools and techniques. Rich Gibson Chief Scientist (and bottle washer), Locative Technologies http://mappinghacks.com http://geocoder.us http://testingrange.com AIM period3equals
_______________________________________________ Geowanking mailing list [email protected] http://lists.burri.to/mailman/listinfo/geowanking
