Algoritmo para encontrar puntos cercanos?

Question

Dado un conjunto de varios millones de puntos con coordenadas x, y, ¿cuál es el algoritmo de elección para encontrar rápidamente los primeros 1000 puntos más cercanos de una ubicación? "Rápidamente" aquí significa aproximadamente 100 ms en una computadora hogareña.

Fuerza bruta significaría hacer millones de multiplicaciones y luego ordenarlas. Si bien una simple aplicación de Python podría hacer eso en menos de un minuto, aún es demasiado larga para una aplicación interactiva.

Se conocerá el cuadro delimitador de los puntos, por lo que sería posible dividir el espacio en una cuadrícula simple. Sin embargo, los puntos se distribuyen de forma desigual, así que sospecho que la mayoría de los cuadros de cuadrícula estarán vacíos y, de repente, algunos de ellos contendrán una gran parte de los puntos.

Editar: No tiene que ser exacto, en realidad puede ser bastante inexacto. No sería un gran problema si los primeros 1000 son solo algunos puntos aleatorios de los 2000 principales, por ejemplo.

Editar: El conjunto de puntos rara vez cambia.

Answer 1

¿Qué le parece usar quadtree?

Divide el área en rectángulos, si el área tiene baja densidad de puntos, los rectángulos son grandes y si el área tiene una alta densidad de puntos, los rectángulos serán pequeños. Usted subdivide recursivamente cada rectángulo en cuatro rectángulos sub hasta que los rectángulos sean lo suficientemente pequeños o contengan pocos puntos suficientes.

Luego puede comenzar a buscar puntos en rectángulos cerca de la ubicación, y moverse hacia afuera hasta que encuentre sus 1000 puntos.

El código para esto podría ser algo complejo, así que tal vez deberías probar primero con la grilla simple y ver si es lo suficientemente rápido.

Answer 2

Los Quadtrees son agradables, pero BSP trees se ejecutan en tiempo O (log n). Creo que los cuadrienares requieren un volumen delimitador finito, y hay algunos casos degenerados en los que los cuatriciclos fallan miserablemente, como cuando una gran cantidad de puntos ocupan el mismo espacio relativamente pequeño.

Dicho esto, los Quadtrees son posiblemente más fáciles de implementar y bastante efectivos en la mayoría de las situaciones comunes. Es lo que UPS usa en sus algoritmos de enrutamiento, porque sus inconvenientes no plantean problemas significativos en la práctica, probablemente porque las ciudades tienden a distribuirse en la región de interés.

Answer 3

Supongo que los puntos están en una base de datos o en alguna ubicación indexada de búsqueda? Si es así, debería ser bastante rápido. Desde el punto dado, puede tener un rango en el eje xey y obtener todas las ubicaciones dentro de ese rango (es decir, especifique la esquina superior izquierda x (a) e y (b) y la esquina inferior derecha x (c) y y (re)).

A continuación, realice una consulta donde para los puntos donde y> = b AND y < = d AND x> = a AND x < = c. esto será rápido asumiendo que tiene índices en las coordenadas xey por separado. (suponiendo que el origen es 0,0 en la parte superior izquierda).

Puede aumentar (o disminuir si el resultado es enorme) este rango por z hasta que el número de puntos dentro del conjunto de resultados sea> = 1000. A través de algunas ejecuciones de prueba, podrá obtener una desviación estándar y otros números estadísticos que le ayudarán a determinar el tamaño del rectángulo para comenzar. Su programa también puede sintonizar su auto según los resultados que obtenga.

Una vez que tenga los datos aproximados, su matemática es bastante simple para calcular la distancia entre cada punto y el punto de origen.

Answer 4

Desea utilizar una estructura como un Árbol cuádruple o un RTree. Estas son estructuras de índices multidimensionales.

La clave está utilizando una buena "curva de relleno de espacio", que es lo que ayuda a definir la cercanía de los puntos. Una curva de llenado de espacio simple es un Zorder, pero estaría más interesado en algo así como una curva hilbert.

http://en.wikipedia.org/wiki/Space_filling_curve

no sé de ningún pre-empaquetados implementaciones de estas cosas. Recientemente implementé mi propio RTree en 2 dimensiones que solo admite carga masiva y búsquedas (a través de un cuadro delimitador provisto).

Un inconveniente aquí es que sus puntos deben estar contenidos en una región finita. Sabe que hay curvas de relleno de espacio que funcionan para espacios que no son finitos, pero no sé nada de ellos.

Answer 5

Si el conjunto de puntos rara vez cambia, también podría considerar usar un diagrama voronoi. No estoy seguro de si eso ayuda a encontrar el primer punto más rápido, pero debería ser mucho más fácil encontrar los siguientes 999 puntos.

Answer 6

Además de las sugerencias de árboles QuadTree y BSP, debe buscar nearest neighbour searching. La elección del algoritmo se basa en la frecuencia con la que se agrega a su conjunto de datos base. Si agrega y elimina a menudo, las soluciones de árbol son superiores. Si los datos son más estáticos, los diagramas voronoi y de búsqueda del vecino más cercano pueden ser mucho más rápidos y escalar mejor.

Answer 7

sé que se dice que no es el más rápido si quieres REALMENTE REALMENTE resultados rápidos al ver que encontré esta publicación de google pensé que agregaría mi solución SQL que utilicé hace un tiempo en la forma de un almacenamiento proc. Busca ubicaciones cercanas a la coord y las devuelve por distancia.

espero que ayude a alguien :)

CREATE PROCEDURE [dbo].[getstores] @lat float, @lng float AS 
DECLARE @radius float, @DegToRad float 
SET @DegToRad = 57.29577951 
SET @radius = 25000 
SELECT TOP 10 
    name 
    ,sto_lat 
    ,sto_lng 
    ,postcode 
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance 
FROM store 
WHERE (sto_lat >= @lat - (@radius/111)) 
And (sto_lat <= @lat + (@radius/111)) 
AND (sto_lng >= @lng - (@radius/111)) 
AND (sto_lng <= @lng + (@radius/111)) 
AND (
    ISNUMERIC(sto_lat) = 1 
    AND 
    ISNUMERIC(sto_lat) = 1 
) 
ORDER BY distance 

NOTA: Ya he dicho que esto no es la mejor solución para esta pregunta simplemente tal vez por alguien que encontró esto en google como yo