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

Answer 3

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.

Answer 4

I store my locations in the data model as latitude/longitude coordinates. Then I wrote some helper extensions to find a semirectangular region of lat/lon coordinates and query by that. Here's the code I'm using. I know the question was for Objective-C but the question is old and likely most people are looking for a Swift answer anyway now.

Swift 3

   extension CLLocationDistance {
        var feet: Double {
            return self * 3.28084
        }
        var miles: Double {
            return self.feet / 5280.0
        }
    }

    extension CLLocationDegrees {
        static var north: CLLocationDegrees {
            return 90.0
        }
        static var south: CLLocationDegrees {
            return -90.0
        }
        static var east: CLLocationDegrees {
            return 180.0
        }
        static var west: CLLocationDegrees {
            return -180.0
        }

        var radians: Double {
            return Double.pi * self / 180.0
        }
    }

    extension CLLocationCoordinate2D {
        static var origin: CLLocationCoordinate2D {
            return CLLocationCoordinate2D(latitude: 0.0, longitude: 0.0)
        }

        static var northPole: CLLocationCoordinate2D {
            return CLLocationCoordinate2D(latitude: 90.0, longitude: 0.0)
        }

        static var southPole: CLLocationCoordinate2D {
            return CLLocationCoordinate2D(latitude: 90.0, longitude: 0.0)
        }

        var metersPerDegreeLatitude: CLLocationDistance {
            return 111319.4907932736
        }
        var metersPerDegreeLongitude: CLLocationDistance {
            return max(0.0, cos(self.latitude.radians) * self.metersPerDegreeLatitude)
        }
    }

    extension CLCircularRegion {
        var northernmostLatitude: CLLocationDegrees {
            let longitude = self.center.latitude + self.radius / self.center.metersPerDegreeLatitude
            return min(longitude, .north)
        }

        var southernmostLatitude: CLLocationDegrees {
            let longitude = self.center.latitude - self.radius / self.center.metersPerDegreeLatitude
            return max(longitude, .south)
        }

        var easternmostLongitude: CLLocationDegrees {
            guard self.northernmostLatitude <= .north else {
                return .east
            }
            guard self.southernmostLatitude >= .south else {
                return .east
            }
            return min(.east, self.center.longitude + self.radius / (self.center.metersPerDegreeLongitude + 0.0001))
        }

        var westernmostLongitude: CLLocationDegrees {
            guard self.northernmostLatitude <= .north else {
                return .west
            }
            guard self.southernmostLatitude >= .south else {
                return .west
            }
            return max(.west, self.center.longitude - self.radius / (self.center.metersPerDegreeLongitude + 0.0001))
        }

        func buildPredicate(latitudeName: String = "latitude", longitudeName: String = "longitude") -> NSPredicate {
            let args = [self.southernmostLatitude, self.northernmostLatitude, self.westernmostLongitude, self.easternmostLongitude]
            return NSPredicate(format: "\(latitudeName) >= %@ && \(latitudeName) <= %@ && \(longitudeName) >= %@ && \(longitudeName) <= %@", argumentArray: args)
        }
    }