What is the fastest way to sort a lot of locations on distance?

Question

I want to sort lots of locations (waypoints) on their distance from the current location. The current location is, of course, a moving target, so for every location update, recomputing the distance for every location is necessary. But only recomputing for close-by locations would by enough.

I currently use core-data, and store the distance to the current location as an attribute in the table (but only update is when it is changed) from within the configurecell: atindexpath: method. That sort of works, but the application is not responding while core-data automagically is updating all distances. This works for 250 locations, but for 5000 it crashes. I need it to work for 10.000 locations, although I probably only need the 1000 closest locations or so.

Ideas that I did not try yet: Store all distances in a separate in-memory array with nothing but record id and distance. Then sort the array on distance. Problem is that then I can not use a FetchedResultsController because there is no sort field in the database.

Filter locations based on their latitude and longitude by using a predicate. Then only present the filtered locations.

Do the recalculation of distances in a separate thread.

None of the ideas seems easy enough to just try it out.

Anybody with suggestions, different ideas, a variation on my ideas?

Answer 1

My final solution is as follows: I select all waypoints within 1 degree latitude and longitude (about 1000 waypoints normally) and then compute and store the distance to the current position in the table. I can then sort on the distance. The slow thing would be the saving in Core Data. But after sorting (and fetching), I simply cancel the changes. The saving was taking more than 90 % of the whole thing, so this worked quite well.

Answer 2

Sounds like you need to convert your locations to positions on a Hilbert curve - then points "near" you are a simple subtraction?

Mapping N-dimensional value to a point on Hilbert curve

Can't say I know the technique inside out, but that's where I'd start to look