Punto più vicino a un determinato punto

Question

Ho un set K di pixel selezionati casualmente in un'immagine 2D. Per ogni altro pixel dell'immagine ho bisogno di scoprire quale pixel nell'insieme K è più vicino ad esso (usando la misura di distanza standard sqrt (dx^2 + dy^2)). Sono consapevole che potrebbe esserci più di una soluzione per ogni pixel. Ovviamente può essere fatto con la forza bruta contro ogni pixel del set, ma preferirei evitare questo perché non è efficiente. Qualche altro buon suggerimento?

Cheers.

Answer 1

Non dimenticare che non è necessario preoccuparsi della radice quadrata.

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

Se non si dispone di una struttura dati che avvolge questo elenco di pixel, è necessario testarli tutti.

Se si dispone di una certa flessibilità, ci sono molti buoni modi per ridurre il carico di lavoro. Crea un numero Quadtree oppure mantieni l'elenco ordinato dei pixel (ordinato per x e ordinato per y) per restringere la ricerca più rapidamente.

Answer 2

Questo è chiamato il più vicino di ricerca. Donald Knuth l'ha definito il problema dell'ufficio postale.

Esistono diverse soluzioni: ricerca lineare, hashing sensibile alla località, file di approssimazione vettoriale e partizionamento dello spazio.

Googling chi dovrebbe aiutare.

Answer 3

A seconda di quanto densamente questo grafico è pieno di pixel, è meglio cercare solo verso l'esterno dal tuo pixel di origine.

Ho programmato qualcosa di simile per un'emulazione di terminale grafica. Quello che ho finito è stato programmare un modello di ricerca sotto forma di una spirale quadrata che è cresciuta dal punto centrale, e l'ho lasciato crescere fino a quando non ha colpito qualcosa. Era abbastanza veloce per lo scopo, anche su una vecchia CPU.

Answer 4

Un altro suggerimento: La distanza è sempre maggiore o uguale a ogni differenza di coordinare, e sempre minore o uguale alla loro somma, vale a dire

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

Questo potrebbe aiutare a fare la selezione in modo più efficiente.

Answer 5

ciò che si sta cercando di fare è costruire un voronoi diagram questo può essere fatto in O (n log n) utilizzando un plane sweep

Answer 6

La costruzione di Voronoi Diagrams è una branca della Computational Geometry. La costruzione di Delaunay Triangulations implica considerazioni simili. Potrebbe essere possibile adattare uno dei seguenti codici Delaunay algorithms in base alle proprie esigenze.

• algoritmi flip
• incrementale
• divide et impera
• Sweepline

Answer 7

mettere i punti in un albero di KD, dopo questo è molto veloce per trovare il vicino più prossimo.Vedi l'articolo this su wikipedia per i dettagli.

Answer 8

Dovrò concordare con jk ed Ewan con la creazione di Voronoi Diagram. Questo dividerà lo spazio in poligoni. Ogni punto in K avrà un poligono che descrive tutti i punti più vicini ad esso. Ora, quando ottieni una query su un punto, devi trovare in quale poligono si trova. Questo problema si chiama Point Location e può essere risolto creando un Trapezoidal Map.

jk già collegato alla creazione dello Voronoi Diagram utilizzando Fortune's algorithm che richiede O (n log n) passaggi di calcolo e costa O (n) spazio. This website mostra come creare una mappa trapezoidale e come interrogarla. È inoltre possibile trovare alcuni limiti là:
ora di creazione previsto: O (n log n)
prevista complessità spaziale: O (n)

Ma, soprattutto, tempo di risposta previsto: O (log n). Questo è (teoricamente) migliore di O (√ n) dell'albero kD.

La mia fonte (diversa dai collegamenti precedenti) è: Computational Geometry: algorithms and applications, capitoli sei e sette.

Qui sono disponibili informazioni dettagliate sulle due strutture di dati (incluse prove dettagliate). La versione di Google books ha solo una parte di ciò che ti serve, ma gli altri link dovrebbero essere sufficienti per il tuo scopo. Basta comprare il libro se ti interessa questo genere di cose (è un buon libro).