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 1000 puntos más cercanos desde una ubicación? " Rápidamente " aquí significa unos 100 ms en una computadora doméstica.

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

Se conocerá el cuadro delimitador para los puntos, por lo que sería posible dividir el espacio en una cuadrícula simple. Sin embargo, los puntos se distribuyen de manera desigual, por lo que sospecho que la mayoría de los cuadrados de la cuadrícula estarían vacíos y, de repente, algunos de ellos contendrían 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 1000 principales son en realidad solo algunos puntos aleatorios de los 2000 principales, por ejemplo.

Editar: el conjunto de puntos rara vez cambia.

Answer 1

¿Qué tal 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 alta densidad de puntos, los rectángulos serán pequeños. Usted subdivide recursivamente cada rectángulo en cuatro sub-rectángulos hasta que los rectángulos sean lo suficientemente pequeños o contengan pocos puntos suficientes.

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

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

Answer 2

Los

Quadtrees son agradables, pero árboles BSP están garantizados para ejecutarse en tiempo O (log n) . Creo que los cuadrúteros requieren un volumen límite finito, y hay algunos casos degenerados en los que los cuadrúles 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 importantes en la práctica, probablemente porque las ciudades tienden a extenderse por la región de interés.

Answer 3

Desea usar una estructura como un árbol Quad o un RTree. Estas son estructuras de índice multidimensional.

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

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

No conozco ninguna implementación preempaquetada 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 proporcionado).

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

Answer 4

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

Answer 5

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

Answer 6

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

Luego haga una consulta donde 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 X e Y por separado. (suponiendo que el origen es 0,0 en la parte superior izquierda).

A continuación, puede aumentar (o disminuir si el resultado es enorme) este rango en z hasta que el número de puntos dentro del conjunto de resultados sea > = 1000. A través de algunas ejecuciones de prueba, debería poder obtener un desviación estándar y otros números estadísticos que lo ayudarán a determinar el tamaño del rectángulo para comenzar. Su programa también puede ajustarse a sí mismo en función de los resultados que obtiene.

Una vez que tenga los datos aproximados, establezca sus matemáticas bastante simples para calcular la distancia entre cada punto y el punto de origen.

Answer 7

Sé que se dice que no es el más rápido si quieres resultados REALMENTE REALMENTE rápidos al ver que encontré esta publicación de Google y pensé que agregaría mi solución SQL que usé hace un tiempo en forma de un proceso almacenado . Busca ubicaciones cercanas al 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 declarado que esta no es la mejor solución para esta pregunta simplemente para alguien que encontró esto en Google como yo