Come funziona algoritmo di partizionamento lo spazio per la ricerca di vicini più prossimi funzionano?

Question

Per trovare il vicino più prossimo, spazio partizionamento è uno degli algoritmi. Come funziona?

Supponiamo di avere un insieme di punti (2D coordinate xey), e sono in un punto (a, b). Come questo algoritmo di scoprire il vicino più prossimo?

Answer 1

partizionamento Spacial è in realtà una famiglia di algoritmi strettamente correlati che lo spazio partizione in modo che le applicazioni in grado di elaborare i punti o poligoni più facile.

Mi sa che ci sono molti modi per risolvere il tuo problema. Non so quanto sia complesso si è disposti a costruire la vostra soluzione. Un modo semplice sarebbe probabilmente per costruire un albero binario tagliando lo spazio in 2. Tutti i punti divisi tra alcuni piano medio. Costruisci il tuo albero suddividendo in modo ricorsivo fino ad esaurimento dei punti.

Alla ricerca del vicino più prossimo sarà poi ottimizzata, perché ogni attraversamento dell'albero restringe l'area di ricerca.

In alcuni la letteratura, lo chiamano questo albero un kd

Answer 2

Questi due video dovrebbero aiutare:

• Spiegando come un albero di KD è costruito: http://www.youtube.com/watch?v=T9h2KKJ_Pl8
• Spiegare come eseguire più vicino Ricerca prossimo: http://www.youtube.com/watch?v=2SbVSxWGtpI