Algoritmo per trovare punti vicini?

Question

Dato un insieme di diversi milioni di punti con coordinate x, y, qual è l'algoritmo di scelta per trovare rapidamente i primi 1000 punti più vicini da una posizione? & Quot; quot rapidamente &; qui significa circa 100 ms su un computer di casa.

Forza bruta significherebbe fare milioni di moltiplicazioni e poi ordinarle. Anche se una semplice app Python potrebbe farlo in meno di un minuto, è ancora troppo lunga per un'applicazione interattiva.

Il riquadro di delimitazione per i punti sarà noto, quindi sarebbe possibile partizionare lo spazio in una griglia semplice. Tuttavia, i punti sono distribuiti in modo un po 'irregolare, quindi sospetto che la maggior parte dei quadrati della griglia sarebbe vuota e quindi improvvisamente alcuni di essi conterrebbero una grande parte dei punti.

Modifica: non deve essere esatto, in realtà può essere abbastanza impreciso. Non sarebbe un grosso problema se i primi 1000 fossero in realtà solo alcuni punti casuali dai primi 2000 ad esempio.

Modifica: il set di punti cambia raramente.

Answer 1

Che ne dici di usare quadtree ?

Dividi l'area in rettangoli, se l'area ha una bassa densità di punti, i rettangoli sono grandi e se l'area ha un'alta densità di punti, i rettangoli saranno piccoli. Suddividi in modo ricorsivo ogni rettangolo in quattro rettangoli secondari fino a quando i rettangoli non sono abbastanza piccoli o contengono pochi punti sufficienti.

Puoi quindi iniziare a guardare i punti nei rettangoli vicino alla posizione e spostarti verso l'esterno fino a quando non hai trovato i tuoi 1000 punti.

Il codice per questo potrebbe diventare un po 'complesso, quindi forse dovresti provare prima con la griglia semplice e vedere se è abbastanza veloce.

Answer 2

I quadrifici sono belli, ma alberi BSP sono garantiti per essere eseguiti in O (log n) time . Penso che i quadrifici richiedano un volume limite limitato, e ci sono alcuni casi degeneri in cui i quadrifogli falliscono miseramente, come quando un gran numero di punti occupa lo stesso spazio relativamente piccolo.

Detto questo, i Quadtrees sono probabilmente più facili da implementare e abbastanza efficaci nelle situazioni più comuni. È ciò che UPS utilizza nei suoi algoritmi di routing, perché gli svantaggi non presentano problemi significativi nella pratica, probabilmente perché le città tendono ad essere distribuite sulla regione di interesse.

Answer 3

Vuoi usare una struttura come un albero Quad o un RTree. Queste sono strutture di indice multidimensionali.

La chiave sta usando un buon " curva di riempimento dello spazio " ;, che è ciò che aiuta a definire la vicinanza dei punti. Una semplice curva di riempimento dello spazio è una Zorder, ma saresti più interessato a qualcosa come una curva di Hilbert.

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

Non conosco implementazioni preconfezionate di questa roba. Di recente ho implementato il mio RTree in 2 dimensioni che supporta solo il caricamento di massa e le ricerche (tramite un riquadro di delimitazione fornito).

Uno svantaggio qui è che i tuoi punti devono essere contenuti in una regione finita. Ci sono curve di riempimento dello spazio che funzionano per spazi che non sono finiti, ma non ne so nulla.

Answer 4

Oltre ai suggerimenti dell'albero QuadTree e BSP, dovresti cercare ricerca del vicino più vicino . La scelta dell'algoritmo si basa sulla frequenza con cui si aggiunge al set di dati di base. Se si aggiungono e rimuovono spesso, le soluzioni ad albero sono superiori. Se i dati sono più statici, la ricerca del vicino più vicino e i diagrammi di voronoi possono essere molto più veloci e scalare meglio.

Answer 5

Se l'insieme di punti cambia raramente, potresti anche prendere in considerazione l'uso di un diagramma voronoi. Non sono sicuro se questo aiuta a trovare il primo più veloce, ma dovrebbe rendere molto più facile trovare i successivi 999 punti.

Answer 6

Suppongo che i punti si trovino in un database o in una posizione indicizzata ricercabile? Se è così, dovrebbe essere abbastanza veloce. Da un determinato punto puoi avere un intervallo sull'asse xey e ottenere tutte le posizioni all'interno di quell'intervallo (ad es. Specificare l'angolo più in alto a sinistra x (a) e y (b) e l'angolo in basso a destra x (c) e y (d)).

Quindi esegui una query in cui per i punti in cui y > = b AND y < = d AND x > = a AND x < = c. questo sarà veloce supponendo che tu abbia gli indici sulle coordinate xey separatamente. (supponendo che l'origine sia 0,0 in alto a sinistra).

Puoi quindi aumentare (o diminuire se il risultato è enorme) di questo intervallo di z fino a quando il numero di punti all'interno del set di risultati è > = 1000. Attraverso alcune prove dovresti riuscire a trovare un deviazione standard e altri numeri statistici che ti aiuteranno a determinare la dimensione del rettangolo con cui iniziare. Il tuo programma può anche sintonizzarsi per questo in base ai risultati che ottiene.

Dopo aver impostato i dati approssimativi, i suoi calcoli matematici sono piuttosto semplici per calcolare la distanza tra ciascun punto e il punto di origine.

Answer 7

So che è stato detto che non è il più veloce se vuoi risultati davvero VERAMENTE veloci visto che ho trovato questo post da google, ho pensato di aggiungere la mia soluzione SQL che ho usato qualche tempo fa sotto forma di un proc memorizzato . Cerca posizioni vicino al a coord e le restituisce a distanza.

Spero che aiuti qualcuno :)

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: ho già dichiarato che questa non è la soluzione migliore per questa domanda semplicemente per qualcuno che l'ha trovato su Google come me