Calculating nearest path

Discussion in 'iOS Programming' started by moonman239, Aug 1, 2013.

  1. moonman239 macrumors 68000

    Mar 27, 2009
    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.
  2. xArtx macrumors 6502a

    Mar 30, 2012
    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!
  3. xArtx macrumors 6502a

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

    There is always some perfectly good explanation from the contributor :D
    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!
  4. chown33 macrumors 604

    Aug 9, 2009
    Sailing beyond the sunset
    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.
  5. xArtx macrumors 6502a

    Mar 30, 2012
    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.
  6. Duncan C macrumors 6502a

    Duncan C

    Jan 21, 2008
    Northern Virginia
    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.
  7. xArtx macrumors 6502a

    Mar 30, 2012
    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.


Share This Page