¿Algo mejor que las cajas delimitadoras?

Question

Tengo un escenario, donde tengo x millones de puntos de latitud de longitud.

Cuando se agrega un nuevo punto Long/LAT, quiero saber eficientemente Qué otros puntos están dentro de un parámetro de distancia configurado por el usuario, por lo que puedo agregarlos a una lista.

¿Tienes algo mejor que las cajas delimitadoras?

Me encantaría ver algoritmos, referencias y algunas implementaciones;) ¡Gracias amablemente!

Answer 1

Hay bastantes opciones que son mejores, principalmente basadas en división espacial.

Una opción común y, a menudo, muy buena (que no es demasiado difícil de implementar) es usar un Árbol kd. Cuádruple son más fáciles de implementar, pero más lento para buscar. Dependiendo de la distribución de sus datos y sus requisitos, otros algoritmos de partición espacial pueden funcionar mejor, tener requisitos de memoria más bajos u otros problemas relacionados.

Answer 2

Un colega me dijo que tenía buena experiencia con el uso Código mortón Como índice espacial en los datos SIG, tal vez eso sea algo que valga la pena investigar.

Answer 3

Este enfoque rápido y sucio puede ahorrarle algo de dolor: divida la superficie de la tierra en cajas de 1 grado. Luego tendrá una matriz de elementos de 180x360 y solo necesitará buscar en una pequeña cantidad de cajas, incluida la caja que contiene el nuevo punto y todas las cajas a su alrededor para las cuales una de las esquinas está dentro de la distancia especificada por el usuario. Encontrará que hay algunos trucos que puede usar para descubrir rápidamente qué cajas usar sin considerarlos todos. Simplemente no olvide la latitud y la longitud envolvente.

Si su "solo" tiene millones de puntos, y no están agrupados en puntos calientes, eso podría hacer que lo haga pasar.

Una forma teóricamente superior: puede mapear cada punto en un espacio tridimensional y luego almacenarlos en un octree, que le permitiría encontrar rápidamente puntos cercanos a una distancia arbitraria. Por supuesto, la distancia en el espacio tridimensional será ligeramente diferente a la distancia del círculo grande en el mundo, por lo que tendrá que calcular un factor de conversión. Sin embargo, eso debería ser simple. No menciona un lenguaje de implementación, pero seguramente habrá una implementación de Octree bien probada para cualquier lenguaje en el que esté trabajando. Si no le importa insertar el código de terceros, esta solución es la forma de Vamos.