¿Qué algoritmo de indexación espacial debo usar?

Question

Quiero implementar algunos rey de la estructura de datos de indexación espacial para mi MKAnnotations. Actualmente es terriblemente lento cuando trato de filtrarlos según los criterios de distancia (3-4k de ubicaciones, actualmente extremadamente lento con un simple doble for ...).

Me gustaría crear clusters de MKAnnotations, para decidir si está cerca de otro. Además, estas ubicaciones están en un orden algo (de creación) y se necesitaría una funcionalidad "anterior"/"siguiente" para "saltar" (esto no es obligatorio). He leído acerca de las estructuras kd-tree y r-tree y ambas parecen cumplir con la opción de obtención de distancia/vecindad rápida para filtrar/agrupar, pero no estoy seguro de cuál es la mejor para mí o si también hay otras opciones. ¿Qué algoritmo/estructura de datos debo usar?

Update: Guardo estas ubicaciones en una base de datos Core Data, representan una ruta. Cuando se abre el mapa, se extraen en una matriz y luego solo uso esa matriz para cálculos de distancia y creación de anotaciones. Cuando el usuario mueve/amplía el mapa, lo recorro y decido qué se debe cambiar en el mapa, por lo que es un poco estático todo el material. Como entendí, si estuviera usando un árbol, podría almacenar las ubicaciones allí y cuando ocurre un zoom/movimiento solo busco y obtengo los que están en la nueva región. Es esto cierto ?

Incluso en el caso dinámico, cuando puedo agregar nuevas ubicaciones a esta matriz, sería una sola inserción y está sucediendo con poca frecuencia.

Answer 1

Depende mucho de cuáles sean sus patrones de uso (cómo escribe, por ejemplo, en memoria o en disco) y cómo se ven sus datos (así es como se distribuye).

Los árboles R son buenos porque son equilibrados, y permiten la actualización. El árbol R * en mi experiencia es claramente mejor que las otras variantes debido a la estrategia de división que tiene. El beneficio es que produce más páginas cuadradas que las otras estrategias, por lo que para muchas consultas necesitará escanear menos páginas.

kd-trees son buenos si está en memoria y estático. Actualizarlos es muy malo, tendrá que reconstruir el índice con bastante frecuencia.

Y si sus datos no cambian muy a menudo, la carga masiva para el R-tree funciona muy bien. Puede hacer Sort-Tile-Recursive carga masiva, que esencialmente requiere clasificar (parcialmente) sus datos en X e Y de forma alterna, por lo que se necesita O(n log n) para construir el árbol; muy similar a la carga masiva de un árbol kd, excepto que se divide en múltiples partes en lugar de dividir binariamente. Esto es muy popular

Además, puede realizar un seguimiento de la cantidad de objetos en cada página. Al mostrar cosas en un mapa, es posible que desee detenerse temprano cuando una página se muestre demasiado pequeña en la pantalla (es decir, más pequeña que un marcador). En este punto, no escaneará esa página, solo tomará el número de objetos y lo mostrará como un marcador agrupado hasta que el usuario amplíe.

Para datos 2D, con un dominio de valor limitado, no pase por alto el simple cosas. ¡Quadtrees también puede funcionar muy bien! La simplicidad puede hacer que sea mucho más fácil optimizar las cosas. O un enfoque de grilla clásico. Si los usuarios tienden a extender sus anotaciones en un área (y no a ponerlas todas en un solo lugar), puede calcular las coordenadas de cuadrícula x, y, y luego hacer una lista para cada celda de la cuadrícula.

Answer 2

no soy un desarrollador de iOS, pero me daba la documentación y encontramos este:

MKMapView.annotationsInMapRect:

devuelve los objetos de anotación localizados en el mapa rectángulo especificado.

(NSSet *)annotationsInMapRect:(MKMapRect)mapRect

Parámetros

• mapRect: La porción del mapa que desea buscar anotaciones.

Valor devuelto El conjunto de objetos de anotación ubicadas en mapRect.

Discusión Este método ofrece una forma rápida de recuperar los objetos de anotación en una parte determinada del mapa. Este método es mucho más rápido que hacer una búsqueda lineal de los objetos en la propiedad de anotaciones usted mismo.

Esto sugiere que el NKMapView ya organiza anotaciones en una estructura de índice espacial. ¿Este método satisfaría tus necesidades?

De lo contrario, buscaría las implementaciones de código abierto existentes de cualquier estructura de indexación espacial 2D y elegiría la que tenga la mejor documentación, las interfaces más limpias, etc. en lugar de preocuparme por la eficiencia.Si necesita escribir el código desde cero, creo que un quadtree sería el más fácil de implementar. Por otro lado, the Wikipedia article on R-tree parece más específicamente dirigido al mapeo que el Árbol K-D o Quadtree.