iOS Calculating nearest path

[moonman239]

Suppose an app of mine has collected data on walking paths in a particular area. I want the app to find the closest path to the user, but I want the app to download only GPS coordinates that will allow the app to figure out the closest path.

I'm thinking that what I could do is tell the app to only log a contributing user's location when either the contributing user makes a significant turn or his or her bearing to some predefined point on the map becomes significant.

 

[xArtx]

Suppose an app of mine has collected data on walking paths in a particular area. I want the app to find the closest path to the user, but I want the app to download only GPS coordinates that will allow the app to figure out the closest path.

I'm thinking that what I could do is tell the app to only log a contributing user's location when either the contributing user makes a significant turn or his or her bearing to some predefined point on the map becomes significant.

If they turned 90 degrees from the track, and stopped for thirty seconds,
and went back to the track on the same path, they took a pee!

 

[xArtx]

More often than not, the contributor sets a bad example for the people who
need the app (start about 20 seconds in) :

http://www.youtube.com/watch?v=B2nHh8s985M

There is always some perfectly good explanation from the contributor
This time, due to a river being up sure to recent rain.
So you collect and overlay contributors tracks over a number of years,
and sometimes still don't have a track, even when they are clearly defined when you're at the location!

 

[chown33]

Suppose an app of mine has collected data on walking paths in a particular area. I want the app to find the closest path to the user, but I want the app to download only GPS coordinates that will allow the app to figure out the closest path.

This seems like a logical contradiction to me.

If the app is responsible for selecting which GPS coordinates to download, then how would it know what to download unless it downloads all coordinates first? "Closest path" inherently implies some kind of comparison between HERE (wherever that is) and one or more other paths. Without knowing the other paths, how could anything possibly decide which path was closest to HERE?

However, if the app tells the server its current coordinates, say as a query string in a URL, then the server already has all the coordinates, and it can choose the closest path and send that to the app as an HTTP REST response.

 

[xArtx]

This seems like a logical contradiction to me.

If the app is responsible for selecting which GPS coordinates to download, then how would it know what to download unless it downloads all coordinates first? "Closest path" inherently implies some kind of comparison between HERE (wherever that is) and one or more other paths. Without knowing the other paths, how could anything possibly decide which path was closest to HERE?

However, if the app tells the server its current coordinates, say as a query string in a URL, then the server already has all the coordinates, and it can choose the closest path and send that to the app as an HTTP REST response.

You can narrow down the search when the list of coordinates has been
indexed into georeferenced sectors first.
If you were interested only in the path ahead, you could search only the blocks in front of you,
but as you say, that doesn't get you the closest path.

 

[Duncan C]

Suppose an app of mine has collected data on walking paths in a particular area. I want the app to find the closest path to the user, but I want the app to download only GPS coordinates that will allow the app to figure out the closest path.

I'm thinking that what I could do is tell the app to only log a contributing user's location when either the contributing user makes a significant turn or his or her bearing to some predefined point on the map becomes significant.

I would suggest creating some sort of location database. Save a center point (or start/end point) of each walking path in lat/long coordinates, plus a radius for each walking path.

When looking for nearby paths, first just download the array of center points/radii (and probably a path ID of some sort)

Then you could do a crude sort of all paths by distance to the user

For every path, calculate
(user_lat-path_lat)^2 + (user_long-path_long)^2

Sort smallest to largest.

That lets find the closest paths with very fast math. (just multiplication and addition)

Then go through the array in smallest to largest order. Calculate the distance in meters between the user's location and the path center (fairly expensive calculation that would allow for the fact that lat/long coordinates are not cartesian), and see if it falls within a certain distance threshold, perhaps using the saved path radius in the decision-making process.

Once you hit the first path that is outside your distance threshold, stop, because each subsequent path will be still further away from the user's location.

Once you pick the paths that are close enough to the user, request the full path data for only that small set of paths.

 

[xArtx]

Sounds like a solution.
I was going to say "but path A might wrap around path B",
but you're going to initially catch both of them.

I would suggest creating some sort of location database. Save a center point (or start/end point) of each walking path in lat/long coordinates, plus a radius for each walking path.

When looking for nearby paths, first just download the array of center points/radii (and probably a path ID of some sort)

Then you could do a crude sort of all paths by distance to the user

For every path, calculate
(user_lat-path_lat)^2 + (user_long-path_long)^2

Sort smallest to largest.

That lets find the closest paths with very fast math. (just multiplication and addition)

Then go through the array in smallest to largest order. Calculate the distance in meters between the user's location and the path center (fairly expensive calculation that would allow for the fact that lat/long coordinates are not cartesian), and see if it falls within a certain distance threshold, perhaps using the saved path radius in the decision-making process.

Once you hit the first path that is outside your distance threshold, stop, because each subsequent path will be still further away from the user's location.

Once you pick the paths that are close enough to the user, request the full path data for only that small set of paths.