[OSM-dev] Help designing specialized navigation software using OSM

[Nolan Darilek]

Hello, all. I recently discovered OSM and, while acknowledging that  
it probably isn't quite usable for this task just yet, I'm hoping  
that will change.

I'm blind, and am using a specialized GPS navigation system called  
Trekker. Rather than displaying maps, Trekker provides verbal  
descriptions of your surroundings. For instance, it can announce  
which street you are on or near. 30 feet or so from an intersection,  
it announces and describes the intersection ("Four-way intersection:  
West North Loop Boulevard crossing Guadalupe Street" for instance.)  
It provides verbal route guidance, POI announcement with directions  
when passing or nearby, etc.

There are some drawbacks to this system, however. It's closed and,  
for a geek like me, rather limiting. For instance, its off-road  
support is incredibly limited in that it can only handle single  
points, and I'd really like a system that can handle ways/traces so I  
can map out networks of trails in my off-road use. There are bugs  
that make the system unusable in some of my current use cases, and  
with the last release nine months old, the slow release cycle is  
quite discouraging. The price is also quite prohibitive--$1500,  
though fortunately map and software upgrades are free.

There are other shortcomings about which I could write, but I'd  
rather do something more productive, so I'm trying to write my own  
and open source it. Unfortunately, this is an entirely new area for  
me and I'm having a hard time coming to terms with how to accomplish  
some of these tasks. I was hoping I could toss out a bunch of  
assorted questions here and ask for help from folks more experienced  
in a wide variety of areas.

At the moment I'm targeting fairly high-end embedded platforms, or  
perhaps small notebooks. I'm coding in Ruby with the intent of  
optimizing to C if it proves necessary. I'm using WX because of its  
support for GTK which is the only accessible open source GUI toolkit  
of which I'm aware, and will need something capable of running GNOME  
so I can use its screen reader. I'm using ActiveRecord for ORM and  
PostgreSQL for the database, since SQLite proved too light for the  
task. Yes, I realize these are incredibly heavy requirements, but the  
platform will already need a keyboard for access, which likely rules  
out most tiny handhelds. I also can't really remove the GNOME  
requirement, because for various reasons GUI apps are more accessible  
than console ones (since the GUI lets you model content presentation  
where something like ncurses just chunks it at the screen.)

Given these requirements, plus bluetooth and 802.11, is there a  
handheld capable of meeting them? I don't have a good reason for  
using PostgreSQL other than "it's what I normally use." Might MySQL  
be a better choice for an embedded platform? Smaller memory  
footprint, lighter, something? *shrug*

I'm also questioning my data model. At the moment I'm just snarfing  
in the OSM data as is. I've borrowed from the rails_port source,  
refined and normalized the schema some, and have a slightly better  
data model that only differs slightly from OSMs. I'm not sure this is  
the best model for navigation, though, and I'm wondering if perhaps I  
can scrap some of the heaviness by getting rid of the database. I  
could also simplify the model and return to using SQLite, though my  
attempt to import 50 megs of Tiger data converted to OSM seemed to  
take over a day, possibly two, whereas it only took 8-9 hours with  
Postgres so I don't know how good of an idea that is.

What would be a good, or the best, data model for navigation  
software? Someone pointed me at Gosmore, but I couldn't understand  
the code. I grasp, though, that it uses a tile-based model for maps.  
Is this the way to go?

Currently I'm thinking of rounding each coordinate off to, say, 5  
decimal places, which should be plenty of accuracy for any need  
(apparently 4 digits is 36 feet or so of accuracy according to  
geocoder.us, but my GPS claims to be capable of 2-5 meters of  
accuracy in good conditions.) I'd have a tile model with lat/long  
columns, then link the nodes to each tile. For segments I'd create  
intervening tiles, placing them between the two nodes and associating  
the tiles with the endpoints. Perhaps there's a better name for these  
points than "node" since they'd simply be an anchor (hmmmm) for the  
string of tiles. Rather than finding sets of endpoints and  
calculating the point of closest approach for the lines connecting  
them, I'd only need to search for nearby tiles and link them to an  
anchor, which would also hold node tags, to determine what street  
someone is on. Then if I find, say, clusters of tiles ahead connected  
to different anchors, I'd know that an intersection is coming up.

Does this sound like a reasonable algorithm? Or am I just going to  
have way too many tiles to deal with, making imports take forever and  
it impractical to store more than a small area at any given time? If  
so, can anyone suggest how I might place tiles between nodes in a way  
that makes sense? Basic trig seems easy, but that'd treat the earth  
as a grid rather than a sphere. Are the distances between nodes small  
enough such that this doesn't really matter much? Or is there a  
better way?

One final point of clarification. Just as with normal GPSs,  
accessible GPSs aren't intended to replace skill or common sense. The  
software I'm designing doesn't have to be any more accurate than  
standard pedestrian GPS just because it's written for blind people.  
I'm just not sure where the line between "useful accuracy" and  
"pointless waste of cycles and space" is. :)

Thanks for reading.