algorithm - kpop - tag de las 20 preguntas

¿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 clasificarlas. Si bien incluso una aplicación Python simple podría hacer eso en menos de un minuto, aún es demasiado larga para una aplicación interactiva.

El cuadro de límite para los puntos será conocido, por lo que sería posible dividir el espacio en una cuadrícula simple. Sin embargo, los puntos se distribuyen de forma algo irregular, por lo que sospecho que la mayoría de los cuadros de la cuadrícula estarían vacíos y, de repente, algunos de ellos contendrían una gran parte de los puntos.

Edición: 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 mejores 2000, por ejemplo.

Edición: conjunto de puntos rara vez cambia.

Answer 1

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

Luego haga una consulta donde para los puntos donde y> = b AND y <= d AND x> = a AND x <= c. esto será rápido suponiendo que tenga índices en las coordenadas x e y por separado. (Suponiendo que el origen es 0,0 en la parte superior izquierda).

Luego 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 una desviación estándar y otros números estadísticos que le ayudará a determinar el tamaño del rectángulo para comenzar. Su programa también puede ajustarse a sí mismo para esto en función de los resultados que obtenga.

Una vez que haya establecido el conjunto de datos, es bastante simple para calcular la distancia entre cada punto y el punto de origen.

Answer 2

¿Qué hay de usar quadtree ?

Si 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 a cuatro rectángulos secundarios hasta que los rectángulos sean lo suficientemente pequeños o contengan pocos puntos suficientes.

Luego puede comenzar a mirar los 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, así que tal vez debería probar primero con la cuadrícula simple y ver si es lo suficientemente rápido.

Answer 3

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

La clave es usar 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 una Zorder, pero estaría más interesado en algo así como una curva de hilbert.

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

No sé de ninguna implementación preempaquetada de este material. Recientemente implementé mi propio RTree en 2 dimensiones que solo admite búsquedas y carga masiva (a través de un cuadro de límite provisto).

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

Answer 4

Los quadtrees son buenos, pero se garantiza que los árboles BSP se ejecutarán en tiempo O (log n). Creo que los quadtrees requieren un volumen de límite finito, y hay algunos casos degenerados en los que los quadtrees fallan miserablemente, como cuando un gran número de puntos ocupan el mismo espacio relativamente pequeño.

Dicho esto, Quadtrees es sin duda más fácil de implementar y bastante eficaz 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 extenderse en la región de interés.

Answer 5

Sé que se dice que no es el más rápido si desea obtener resultados REALMENTE REALMENTE rápidos al ver que encontré esta publicación de Google, pensé que agregaría mi solución SQL que usé hace un tiempo en forma de un proceso almacenado. Busca ubicaciones cercanas a la coordenada a y las devuelve por distancia.

Espero que esto 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 dije que esta no es la mejor solución para esta pregunta, tal vez para alguien que encontró esto en google como yo.

Answer 6

Si el conjunto de puntos rara vez cambia, también podría considerar el uso de un diagrama 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 7

Además de las sugerencias de árbol de QuadTree y BSP, debe buscar la búsqueda de vecinos más cercanos . 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 con frecuencia, las soluciones de árbol son superiores. Si los datos son más estáticos, la búsqueda de vecinos más próximos y los diagramas de voronoi pueden ser mucho más rápidos y escalar mejor.