Algoritmo best-performance per la risoluzione del prossimo più prossimo

Question

Abbiamo una lista di coppie x, y. Ogni coppia rappresenta un punto su uno spazio 2D. Voglio trovare il punto più vicino da questa lista, a un punto specifico xq, yq. Qual è il miglior algoritmo per le prestazioni critiche per questo problema? Lisp di punti non cambierà; il che significa che non è necessario eseguire l'inserimento e la cancellazione. Voglio solo trovare il vicino più prossimo di un target xq, punto yq in questo set.

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

Costruirò la struttura dati basata sull'elenco una sola volta, quindi userò questa struttura dati generata 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 credo che lo sia. Aggiornerò quando avrò dei risultati rilevanti).

Modifica 2: Ho scoperto che questo problema è denominato "prossimo più vicino"!

Modifica 3: il primo titolo era "Alla ricerca di un algoritmo (per ricerca spaziale e indicizzazione spaziale) (vicino più vicino)"; Ho scelto un nuovo titolo: "Miglior algoritmo critico delle prestazioni per risolvere il vicino più vicino". Dato che non voglio eseguire operazioni di inserimento e cancellazione sui miei dati iniziali e voglio solo il 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 osservato Stephan202, se hai intenzione di trovare l'incontro più vicino 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. O potresti implementarne uno tu stesso!

EDIT: Ho fatto una domanda sulle implementazioni di kd-tree here - potrebbe essere utile.

EDIT: KD-alberi sono stati ampiamente utilizzati con successo per le ricerche NN :) - Inoltre, se siete disposti ad accettare corrispondenze approssimative, è possibile utilizzare Fast Library for Approximate Nearest Neigbor (FLANN). L'implementazione FLANN è presente in OpenCV 2.0.

Se non si desidera ottenere risposte approssimative, è possibile modificare i parametri FLANN per cercare l'intero albero.

Answer 2

Iterate attraverso ogni altro punto utilizzando la formula della distanza per trovare la distanza minima da Q (xq, yq).

Tuttavia, non sono state fornite informazioni sufficienti per una risposta critica dal punto di vista delle prestazioni.

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

Secondo esempio, se si dispone di un gran numero di punti, si potrebbe organizzare i punti in sezioni e iniziare con i punti solo nella stessa sezione e le sezioni adiacenti alla sezione contenente D.

Answer 3

Se il punto di interrogazione (xq, yq) varia e l'elenco no, è necessario calcolare lo Voronoi diagram dell'elenco di punti.Questo ti darà un insieme di poligoni o "celle" (alcune delle quali sono infinite); 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 nell'elenco originale. Qualsiasi punto su un confine tra due poligoni si trova ugualmente distante da ciascun sito.

Una volta che sei arrivato così lontano, hai bisogno di un modo semplice per capire quale poligono ti trovi. Questo è noto come point location problem.

Un libro davvero molto buono per questo genere di cose è Computational Geometry: Algorithms and Applications. Discutono sia il calcolo del diagramma di Voronoi che il metodo della lastra trapezoidale della posizione del punto in dettaglio.

Se non si desidera eseguire il codice da soli, e non si dovrebbe, quindi provare a ottenere una libreria come CGAL che farà la maggior parte del lavoro per voi. Questo probabilmente si applica anche alla risposta dell'albero KD, ma non lo so in modo specifico.

Answer 4

È necessario un spatial index.

Se si rotola il proprio, si può fare molto peggio di scegliere gli algoritmi R-Tree o Quad-tree.

Answer 5

Vorrei andare con un quadrifoglio. È la struttura spaziale più semplice. In 2 dimensioni consiglio generalmente quadtree invece di kd-tree, perché è più semplice, più veloce. Il suo svantaggio è 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 coordinate sono a virgola mobile digitate: In una query devi 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 decidendo quale nodo figlio fare il passo. Memorizza gli identificatori/indirizzi dei nodi figli in un array di 4 dimensioni nella struttura del nodo. Digitalizza le coordinate del punto nell'algoritmo della query. Quindi sarai in grado di trovare il sub-nodo corretto semplicemente indicizzando l'array di 2 bit appropriati delle coordinate del punto digitalizzate. La digitalizzazione è veloce: implementala con un semplice static_cast.

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