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

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

http://stackoverflow.com/questions/499166/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

Answer 2

If what's important is the order (as opposed to having accurate distances), you could sort slices of the waypoint sequence in a moving window (that is, sort items i to i+n, where i changes). Start at the beginning of the waypoint sequence. Sort n items (n = 10 is a good place to start). If any items changed position, move the window forward by n/2 (experiment with different offsets or algorithms to choose an offset) and repeat. Depending on how dense the waypoint are near the current location, I would expect this to stop after only a few sorts.

Note that I haven't thought about this long enough to say whether or not this will actually work.

Of the three options you mention, I like using threads the most. That's the classical way of handling a non-responsive UI when it's blocked by heavy computation.