Il miglior algoritmo critico per le prestazioni per risolvere il vicino più vicino

Question

Abbiamo un elenco di coppie x, y. Ogni coppia rappresenta un punto su uno spazio 2D. Voglio trovare il punto più vicino da questo elenco, a un punto specifico xq, yq. Qual è il miglior algoritmo critico per le prestazioni di questo problema? Il Lisp di punti non cambierà; il che significa che non ho bisogno di eseguire inserimenti ed eliminazioni. Voglio solo trovare il vicino più vicino di un target xq, yq point in questo set.

Modifica 1: grazie a tutti! Come Stephan202 ha indovinato correttamente, voglio farlo ripetutamente; come una funzione. Una lista non è necessariamente ordinata (In effetti non capisco come possa essere ordinata? Come una tabella con una chiave primaria di 2 colonne a e y? Se questo aiuta, allora lo ordinerò).

Costruirò una volta la struttura dei dati in base all'elenco, quindi userò questa struttura di dati generati nella funzione (se questo processo è rilevante).

Grazie Jacob; Sembra che la struttura dei dati di KD-Tree sia un buon candidato per essere la risposta (E lo sento. Lo aggiornerò quando avrò alcuni risultati pertinenti).

Modifica 2: ho scoperto che questo problema si chiama "prossimo più vicino"!

Modifica 3: il primo titolo era " Alla ricerca di un algoritmo (per query spaziali e indicizzazione spaziale) (vicino più vicino) " ;; Ho scelto un nuovo titolo: "Migliore algoritmo critico per le prestazioni per risolvere il prossimo più vicino". Dal momento che non voglio eseguire operazioni di inserimento ed eliminazione sui miei dati iniziali e voglio solo quello più vicino da loro a un nuovo punto (che non verrà inserito), ho scelto di (attualmente) lavorare su KD-Trees. Grazie a tutti!

Answer 1

Come notato da Stephan202, se hai intenzione di trovare la corrispondenza più vicina per più di un punto, dovresti usare un albero.

Vorrei raccomandare un albero KD, la cui implementazione può essere facilmente trovata in diversi pacchetti come OpenCV 2.0 . Oppure potresti implementarne uno tu stesso!

EDIT: avevo posto una domanda sulle implementazioni di kd-tree qui - potrebbe essere utile.

EDIT: gli alberi KD sono stati ampiamente utilizzati con successo per le ricerche NN :) - Inoltre, se sei disposto ad accettare corrispondenze approssimative, puoi utilizzare Libreria veloce per Neigbor approssimativo più vicino (FLANN) . L'implementazione FLANN è presente in OpenCV 2.0 .

Se non si desidera una risposta approssimativa, è possibile modificare i parametri FLANN per effettuare ricerche nell'intero albero.

Answer 2

Se il punto di query (xq, yq) varia e l'elenco no, è necessario calcolare Diagramma di Voronoi dell'elenco di punti. Questo ti darà una serie di poligoni o "celle" (alcuni dei quali sono infiniti); ogni poligono corrisponde a un punto dell'elenco originale, chiamato "sito" di quella cella. Qualsiasi punto che si trova interamente all'interno di un poligono è più vicino al sito di quel poligono che non agli altri siti dell'elenco originale. Qualsiasi punto su un confine tra due poligoni si trova ugualmente distante da ciascun sito.

Una volta arrivati ??così lontano, hai bisogno di un modo semplice per capire in quale poligono ti trovi. Questo è noto come problema di localizzazione dei punti .

Un libro davvero valido per questo genere di cose è Geometria computazionale: algoritmi e applicazioni . Discutono in dettaglio sia il calcolo del diagramma di Voronoi sia il metodo della lastra trapezoidale di localizzazione dei punti.

Se non vuoi scrivere tu stesso il codice e non dovresti, prova a ottenere una libreria come CGAL che farà la maggior parte del lavoro per te. Questo probabilmente si applica anche alla risposta dell'albero KD, ma non lo so specificamente.

Answer 3

È necessario un indice spaziale .

Se ottieni il tuo, puoi fare molto peggio che scegliere R-Tree o algoritmi Quad-tree .

Answer 4

Vorrei andare con un quadrifoglio. È la struttura spaziale più semplice. In 2 dimensioni raccomanderei generalmente quadtree invece di kd-tree, perché è più semplice, più veloce. Il suo svantaggio è un maggiore consumo di memoria se il numero di dimensioni è elevato, ma in caso di 2 dimensioni la differenza non è significativa.

C'è un bel trucco di ottimizzazione se le tue coordinate sono in virgola mobile: In una query dovrai prima trovare il nodo foglia che contiene il punto a cui viene chiesto il punto più vicino. Per fare questo dovrai andare nell'albero dalla radice alla foglia - in ogni iterazione decidere quale nodo figlio su cui fare un passo. Memorizza gli identificatori / indirizzi dei nodi figlio in un array di 4 dimensioni nella struttura Nodo. Digitalizza le coordinate del punto nell'algoritmo della query. Quindi sarai in grado di trovare il sotto-nodo corretto semplicemente indicizzando l'array con 2 bit corretti delle coordinate dei punti digitalizzati. La digitalizzazione è veloce: implementala con un semplice static_cast.

Ma prima implementa il quadtree senza ottimizzazione perché è facile fare un bug con le operazioni bit. Anche senza questa ottimizzazione, sarà comunque la soluzione più veloce.

Answer 5

Scorrere tutti gli altri punti usando la formula della distanza per trovare la distanza minima da Q (xq, yq).

Tuttavia, non hai fornito informazioni sufficienti per una risposta critica per le prestazioni.

Ad esempio, se Q è un punto MOLTO comune, potresti voler calcolare la distanza da Q e memorizzarla con ciascun punto.

Secondo esempio, se si dispone di un numero enorme di punti, è possibile organizzare i punti in sezioni e iniziare con punti solo nella stessa sezione e sezioni adiacenti alla sezione contenente Q.