[OSM-dev] Nearest way for a location

[Nolan Darilek]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi, all. I'm working on an accessible GPS navigation app that provides
spoken feedback to blind or visually impaired travelers. The challenges
here are a bit different than simply drawing a map and updating a
pointer on that map. Instead, I need for the app to intelligently
analyze the data it is receiving such that it can announce when the user
is approaching an intersection, describe that intersection from the
user's current perspective (I.e. "3-way intersection: La Casa Dr.
crossing Anarbor Ave. on your left", etc.) For the most part, I have
these problems solved. I've written a library that can textually
describe intersections based on a number of factors, and that seems to
work well. The challenge, though, is in finding the nearest way for a
given point.

Basically, if a user reaches an intersection and turns onto a new
street, I'd like to provide feedback that he is on a new way as soon as
I can. Granted, GPS inaccuracy makes instantly doing so impossible, but
when the user is a few meters from a given intersection, I should be
able to pretty quickly establish what way he is on. Unfortunately, my
current method leaves a lot to be desired.

Previously, my nearest way calculation involved figuring out what the
nearest node was, then assigning the way based on that. It gets a bit
more complicated in cases where a node has two ways, determines if the
user's previous way is one of the node's ways and picks that one again
if so, but I'm discovering now that this approach was rather naive. The
failing case seems to be turning at an intersection where the next
closest node is further away than the intersection. In this instance, I
have to travel far enough such that the node on the new way is closest,
at which point the nearest way calculation happens again. Even so, since
the new nearest node is on an entirely different set of ways, there is a
real chance that my app gets the nearest way wrong, which is highly useless.

I'm using Traveling Salesman/LibOSM which doesn't do any post-processing
on the OSM data structures. Given standard nodes and ways, how can I
find the nearest way to a given point? Note that we can max out the
search at, say, 100 meters or so, meaning that somewhat expensive
algorithms are probably OK.

I was thinking of perhaps taking all nodes in a, say, 200-meter radius,
drawing segments between them, determining the user's nearest point of
approach to each and using that, but I could see that failing on long
straight roads with long gaps between nodes, and I'm not even sure how
to represent that numerically. Is there a better way?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkwnajMACgkQIaMjFWMehWJ4egCeLtkgmLNTe2pTKUuO9NhFQ+4y
RqkAnRp9fqtCqf5Bedxl/+1DLzRgJqzV
=QBiJ
-----END PGP SIGNATURE-----