[OSM-dev] Simplifying data for routing

Frederik Ramm frederik at remote.org
Sat Jul 28 16:29:59 BST 2007


Hi,

> Since I'm dropping most of the OSM nodes, I'm thinking that the  
> vertices on the graph should be intersections. Part of my current  
> post-processing involves doing a brute-force check of any newly-saved  
> Path for any that intersect it. I then create an intersection feature  
> as a point, linking to all the "branches." As such, I can now find  
> and describe nearby intersections in terms of how many "ways" they  
> have and render that description as something like "5-way  
> intersection: E 51st St. with Duval St. and Guadalupe St."

That's more or less what I would do but you may want to talk to Nic 
Roets and/or look at his "gosmore" page on the Wiki, and try to 
understand his "half-segment" approach which sounds quite clever to me.

> I have several questions. First, is using intersections for the  
> vertices of the routing graph the right way (no pun intended) to do  
> it? I thought about using nodes, but if I understand the model,  
> there's no reason to expect nodes to be placed at intersections.

Oh yes, we expect people to place nodes at intersections. If two roads 
intersect without a node being put there, that's either lazyness or a 
forgotten "bridge" tag or so. I'd suggest to use those nodes that are 
intersections and drop the rest.

> Second, I'm still trying to grok a*/Dijkstra algorithms for shortest  
> path. Seems like several routing apps I've checked out prefer  
> Dijkstra, but is there any reason for picking it over a*? My  
> understanding is that a* stops investigating paths that aren't  
> meaningful, so wouldn't move toward a point to the north by going  
> south. 

Yes. A* needs a heuristic that tells it (basically) "the best way 
between node X and the destination can never be shorter than Z units". 
For routing applications, you can use the straight line distance between 
a node and the destiantion as a heuristic which is what's normally done. 
  (However you must be careful not to *reduce* the length of your edges 
then, i.e. you must never say "this is a motorway so I'll multiply the 
length by 0.5" - you must instead use penalties for slower roads.)

In addition to that heuristic, A* also requires that your destination is 
known. Dijkstra doesn't require that, you can e.g. run Dijkstra until 
you reach the "nearest petrol station" or so.

Maybe some people use Dijkstra because it is a bit easier to implement 
or understand; but on the whole, A* is preferred for routing.

I believe there are some routing functions available for PostGIS (google 
for "pgRouting"); if you put your data in the format they expect, you 
might get away without any coding at all.

Bye
Frederik

-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00.09' E008°23.33'




More information about the dev mailing list