location Points: distance to a specified route

Question

First let me state the idea:

I want to check the distance of a user to a specified route. The route consists of multiple Location Points (In the picture, point a, b, c, d). Two adjacent points describe a vector (the blue lines ab, bc, cd in the picture)

Now to the application (android in particular, but that is not part of this question) The users location is tracked while he is traveling along the route. With every new location I want to check, if the user is still on the route (or within a distance X).

I drew 3 possible locations along the route:

• location 1 is no problem. I drop the perpendicular from point 1 to the vector ab. That gives me a location point on this vector and I can calculate the distance between the two points (with android: Location.distanceTo())

• location 2 as I am dealing with vectors, they have no beginning and no end. The black line is the projection of vector ab. Calculating the nearest distance would give me a close distance to vector ab, but a far one from vector bc. Indeed I would need to calculate the distance to bc because that is how the route is proceeding. But how do I know in my algorithm which vector I need to choose to calculate the distance to?

• location 3 gives me th possibility to calculate with vector ab or bc. Both are nearly equally close. How to know which one to choose?

to round this up:

I have an array with location points:

{[lat1, lon1], [lat2, lon2],[...]}

My application is tracking the users location. I now want to compare the new location to this track in the array.

Does someone know an algorithm which is covering the problem, or could someone help me with the algorithm? (Pseudocode is sufficient)

//edit: I just read about the Quadtree algorithm. Maybe that is an option in addition to the implementation of Soonts.

Answer 1

First convert all your data (user position, points) from lat/lon into x / y km, using the following formulae:

Y = lat * 111, X = lon * 111 * cos( lat )

(this will slightly fail with routes longer then 1000 miles, and dramatically fail near the poles or when your path crosses the 180-th meridian, hope it's OK for your task).

Then use the following formula to find the find the distance between the point and each segment: https://stackoverflow.com/a/1501725/126995, and search for the minimum distance. Some performance optimizations are required of your route has more then 200 segments.

P.S. If you're unhappy about the limitations of this method - look for the formulae for distance between the point and segment on the sphere, but I can assure you those will contain a lot of trigonometry, and I doubt the cheap android phones will do it fast with long routes.