[OSM-dev] Creating a graph for routing

[Nolan Darilek]

Hello. First, I'm not certain whether my questions are completely on- 
topic for this list, and apologize if they aren't. If there's a  
better community for folks developing mapping applications that  
aren't necessarily OSM core, do let me know and I'll go there.

As a brief summary, I'm designing GPS navigation software for blind/ 
visually-impaired users. So instead of displaying a map, for  
instance, the software displays everything in a text stream--what  
street you're on, upcoming intersections, how many ways they are,  
what streets meet, etc. It's written in Ruby using ActiveRecord,  
WXRuby and Postgres/Postgis for the data store. I intend for this to  
be run on high-end mobile devices, and the stack may be too heavy for  
that, I just don't know yet. I registered my domain yesterday,  
though, and what I have thus far can be found at http://hermes- 
gps.info. Apologies for the stock website--I tweaked the newgem  
default and am leaving it for now.

But, anyway, onto the questions. I'm planning on using pgRouting, and  
for this and other features I need to create a graph of all  
intersections. I currently check whether each path I save intersects  
any others and generate intersection models at the point of  
intersection. I tried determining whether or not any given node was  
at an intersection between ways, but this didn't seem markably  
faster, and since I'd eventually like to support users creating new  
paths on the fly, this unifies everything under a single callback  
invoked whenever paths are saved. I also generate edges for each  
intersection and path, two edges if the path completely contains the  
intersection point (I.e. crosses) but since I don't have all  
intersections saved in the initial import, it's impossible to  
complete the graph by setting the "to" component of each edge. I have  
an algorithm for this, but it looks like it may take more than a day  
to run for a single county, and I can't help but wonder if it could  
be optimized, or if I'm missing something super obvious.

Here's the algorithm. Iterate over all edges created during a given  
import. First, find all intersections on an edge's path sorted by  
distance. Then check whether an edge from the given intersection  
exists to the target. If so then another edge has already been  
created, so move on (since, again, the initial pass only knows how  
many are necessary, not where they will lead.) Then for each  
intersection, iterate through all points between the edge's  
intersection and the target intersection exclusive. If any  
intermediate point is an intersection, move onto the next furthest  
intersection. Otherwise, you've found the closest intersection with  
none between, so set this as the destination of the edge and set the  
distance along the line as the cost of the edge.

Thoughts as to how I might optimize that? Or is there a better way?

And if anyone is interested in helping with this project, check out  
the above website. This scratches an itch for me, but I really know  
little about how this stuff works, so I'm figuring it all out by  
brute-force thinking my way through. While this may seem admirable,  
it discounts the notion that others have already done the same, and  
have probably done so with better results. :)