¿Cuál es la manera más rápida de ordenar muchas ubicaciones a distancia?

Question

Quiero ordenar muchas ubicaciones (puntos de ruta) en su distancia desde la ubicación actual. La ubicación actual es, por supuesto, un objetivo en movimiento, por lo que para cada actualización de ubicación, es necesario volver a calcular la distancia para cada ubicación. Pero solo volver a calcular para ubicaciones cercanas sería suficiente.

Actualmente uso Core-Data, y almaceno la distancia a la ubicación actual como un atributo en la tabla (pero solo la actualización es cuando se cambia) desde el método de configurecell: atindexpath :. Ese tipo de trabajo funciona, pero la aplicación no responde mientras que core-data automágicamente está actualizando todas las distancias. Esto funciona para 250 ubicaciones, pero para 5000 se bloquea. Lo necesito para trabajar en 10.000 ubicaciones, aunque probablemente solo necesite las 1000 ubicaciones más cercanas.

Ideas que aún no probé: Almacene todas las distancias en una matriz en memoria separada con nada más que la id. De registro y la distancia. Luego ordena la matriz en la distancia. El problema es que no puedo usar FetchedResultsController porque no hay ningún campo de ordenación en la base de datos.

Filtre las ubicaciones en función de su latitud y longitud mediante el uso de un predicado. Entonces solo presente las ubicaciones filtradas.

Haga el recálculo de distancias en una secuencia separada.

Ninguna de las ideas parece tan fácil de probar.

¿Alguien con sugerencias, ideas diferentes, una variación de mis ideas?

Answer 1

Mi solución final es la siguiente: Selecciono todos los puntos de referencia dentro de 1 grado de latitud y longitud (aproximadamente 1000 puntos de referencia normalmente) y luego calculo y almaceno la distancia a la posición actual en la tabla. Puedo ordenar la distancia. Lo lento sería el ahorro en Core Data. Pero después de ordenar (y recuperar), simplemente cancelo los cambios. El ahorro suponía más del 90% del total, por lo que funcionó bastante bien.

Answer 2

Parece que necesita convertir sus ubicaciones en posiciones en una curva de Hilbert. Entonces, señala que "cerca" de usted es una simple sustracción.

Mapping N-dimensional value to a point on Hilbert curve

No se puede decir que conozca la técnica de adentro hacia afuera, pero ahí es donde me gustaría empezar a buscar

Answer 3

Si lo que importa es el orden (en lugar de tener distancias exactas), usted podría ordenar las divisiones de la secuencia de waypoint en una ventana en movimiento (es decir, ordenar elementos i a i + n, donde i cambios). Comience al comienzo de la secuencia del punto de referencia. Ordenar n elementos (n = 10 es un buen lugar para comenzar). Si alguno de los elementos cambió de posición, mueva la ventana hacia adelante por n/2 (experimente con diferentes desplazamientos o algoritmos para elegir un desplazamiento) y repita. Dependiendo de qué tan denso sea el punto de ruta cerca de la ubicación actual, esperaría que esto se detenga después de solo unos pocos géneros.

Tenga en cuenta que no he pensado en esto el tiempo suficiente para decir si esto realmente funcionará o no.

De las tres opciones que menciona, me gusta usar hilos más. Esa es la forma clásica de manejar una IU que no responde cuando está bloqueada por cálculos pesados.

Answer 4

Almaceno mis ubicaciones en el modelo de datos como coordenadas de latitud/longitud. Luego escribí algunas extensiones de ayuda para encontrar una región semirrectangular de coordenadas de latitud/longitud y consultar por eso. Aquí está el código que estoy usando. Sé que la pregunta era para Objective-C, pero la pregunta es antigua y es probable que la mayoría de la gente esté buscando una respuesta Swift de todos modos ahora.

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) 
     } 
    }