Search code examples
swiftmathgpsposition

Combine GPS points to speed up calculations

I have an app that will register the GPS coordinates on each check in made by the user. If the user comes back to make a new check in, as a speed saving option, we will show the closest place he had checked in.

Each check in will save the current position of the user, regardless if it is the first or 100th check in.

After some time we have a huge list of coordinates that we need to check each time.

How can I collapse this information? I want to turn a huge list of latitudes and longitudes into one or more polygons so I can speed up distance calculations.

# So this
1:0 100:200 2:0 2:2 2:1 1:1 2:1 0:1

# Could become this
100:200 1:1

# Or this
100:200,100:200 0:0,2:2
Solution

  • This is called the nearest neighbor search problem. You can have a look at the Wiki article which mentions faster algorithms. It seems that space partitioning with an R-Tree is the best approach.