punto più vicino ad un dato punto

Question

Ho un insieme K di pixel selezionati casualmente in un'immagine 2D. Per tutti gli altri pixel nell'immagine ho bisogno di scoprire quale dei pixel in serie K è il più vicino ad esso (utilizzando lo sqrt standard (dx ^ 2 + dy ^ 2) misura della distanza). Sono consapevole che ci possono essere più di una soluzione per ogni pixel. Ovviamente può essere fatto con la forza bruta contro ogni pixel nel set, ma preferirei evitare questo, perché non è efficiente. Eventuali altri buoni suggerimenti?

Saluti.

Answer 1

Non dimenticare che non c'è bisogno di perdere tempo con la radice quadrata.

Se si desidera solo per trovare quello più vicino (e non si tratta di distanza reale) basta usare dx^2 + dy^2, che vi darà la distanza al quadrato per l'ogni elemento, che è altrettanto utile.

Se non si dispone di dati struttura di confezionamento questo elenco di pixel up, dovrai semplicemente prova contro di loro tutti.

Se si dispone di una certa flessibilità, ci sono un sacco di buoni modi per ridurre il carico di lavoro. Fare un Quadtree , o di tenere elenco ordinato dei pixel (ordinati per x e ordinati per y) restringere la ricerca in modo più rapido.

Answer 2

Io sono d'accordo con jk e Ewan con fare un Voronoi Diagram . Ciò si ripartisce lo spazio in poligoni. Ogni punto K avrà un poligono che descrive tutti i punti che sono più vicini. Ora, quando si ottiene una query di un punto, è necessario trovare in cui poligono si trova. Questo problema si chiama Point Località e può essere risolto con la costruzione di un trapezoidale Mappa .

JK già legata alla creazione del Voronoi Diagram utilizzando Fortune algoritmo che prende O (n log n) passi computazionali e costa O (n) spazio. Questo sito mostra come fare una mappa trapezoidale e come eseguire una query di esso. È inoltre possibile trovare alcuni limiti lì:
Tempo previsto di creazione: O (n log n)
Previsto complessità spaziale: O (n)

Ma, soprattutto, tempo di risposta previsto: O (log n). Questo è (teoricamente) meglio di O (√ n) del KD-albero.

La mia fonte (diversi link qui sopra) è: Geometria computazionale:. algoritmi e applicazioni , capitoli sei e sette

Vi si possono trovare informazioni dettagliate sulle due strutture di dati (tra cui prove dettagliate). I libri versione Google ha solo una parte di ciò che è necessario, ma gli altri collegamenti dovrebbe essere sufficiente per il vostro scopo. Basta acquistare il libro, se siete interessati a questo genere di cose (si tratta di un buon libro).

Answer 3

La costruzione di Diagramma di Voronoi è una branca della Geometria computazionale . La costruzione di Delaunay Triangolazioni comporta considerazioni analoghe. Si può essere in grado di adattare una delle seguenti Delaunay algoritmi base alle proprie esigenze.

• algoritmi di vibrazione
• incrementale
• Divide et impera
• Sweepline

Answer 4

Mettere i punti in un albero di KD, dopo questo è molto veloce per trovare il vicino più prossimo. Vedere questo articolo su wikipedia per ulteriori dettagli.

Answer 5

Questa è chiamata la ricerca vicino più prossimo. Donald Knuth ha definito il problema ufficio postale.

Ci sono una serie di soluzioni:. Ricerca lineare, hashing sensibile località, file vettore di approssimazione e di spazio di partizionamento

Googling chi dovrebbe aiutare.

Answer 6

ciò che si sta cercando di fare è costruire un Voronoi schema questo può essere fatto in O ( n log n) utilizzando un piano spazzata

Answer 7

Un altro suggerimento:. La distanza è sempre maggiore o uguale ad ogni differenza di coordinate, e sempre inferiore o uguale alla loro somma, cioè

d >= dx, d >= dy, d <= dx + dy.

Questo potrebbe aiutare a fare l'ordinamento in modo più efficiente.

Answer 8

A seconda di come densamente questo grafico è pieno di pixel, si potrebbe essere meglio solo la ricerca verso l'esterno dal tuo pixel di origine.

Ho programmato qualcosa di simile per un'emulazione di terminale grafico. Quello che ho finito per fare era la programmazione di un modello di ricerca a forma di una spirale piazza unilaterale che è cresciuto fuori dal punto centrale, e io lasciarlo crescere fino a quando non ha colpito qualcosa. Questo è stato sufficientemente veloce per lo scopo, anche su una vecchia CPU.