Trova il vicino più vicino in un raggio

Question

Ho un set di punti A nel mio spazio (punti geo ma posso supporre che siano su un piano 2D).

Ho un altro set di punti B .

Per ogni punto in B Voglio trovare ogni punto in A all'interno di un raggio R con il centro nel punto considerato da B Set.

L'ho fatto con Kdtree, questo mi fornisce un algoritmo molto veloce e facile per creare la struttura dei dati e trovare i vicini ma Non trova tutto il punto in un raggio perché potrebbe evitare un percorso che contiene elemento nel mio raggio ma non nello stesso sottoinsieme del centro del raggio.

Esempio minimo di kdtree fallimento :

Durante l'esplorazione di Kdtree il punto di destinazione (rosso) è sotto la linea del punto numero 1. Ciò procederà all'esplorazione del punto sotto la linea, questo mancherà il punto reale all'interno del raggio del punto rosso.

Quale algoritmo o struttura dei dati consentono la correttezza del 100%?

Lo so per certo che andremo peggio ma cercherò un equilibrio tra la velocità di ricerca e la piena correttezza.

Answer 1

L'albero K-D è una buona struttura dei dati per risolvere questo.Tuttavia non è possibile applicare ciecamente la procedura di ricerca solo al punto centrale, è necessario essere un po 'più intelligente.

Durante la ricerca dell'albero KD per i tuoi punti, ogni volta che devi scegliere il bambino sinistro o destro per cercare, verificare se il piano di divisione è a sinistra del cerchio, intersecarlo, o è a destra del cerchio.

Se il piano diviso è a sinistra del cerchio, devi continuare a cercare nel bambino giusto e viceversa.Tuttavia, quando il piano diviso interseca il tuo cerchio è necessario cercare entrambi bambini.