Encuentra al vecino más cercano en un radio

Question

Tengo un conjunto de puntos a en mi espacio (Geo Points, pero puedo asumir que están en un plano 2D).

Tengo otro conjunto de puntos b .

por cada punto en b Quiero encontrar cada punto en a dentro de un radio r con el centro en el punto considerado de B conjunto.

Lo hice con Kdtree, esto me proporcionó un algoritmo muy rápido y fácil para crear la estructura de datos y encontrar a los vecinos pero no encuentran cada punto en un radio porque podría evitar un camino que contiene elemento en mi radio, pero no en el mismo subconjunto del centro de radio.

Ejemplo mínimo de Kdtree Falling :

Mientras está explorando kdtree, el punto de destino (rojo) está debajo de la línea de punto número 1. Esto procederá a explorar el punto debajo de la línea, esto se perderá el punto real dentro del radio del punto rojo.

¿Qué algoritmo o estructura de datos permiten la corrección del 100%?

Sé seguro que lo funcionaré, pero busco un equilibrio entre la velocidad de búsqueda y la corrección completa.

Answer 1

El árbol K-D es una buena estructura de datos para resolver esto.Sin embargo, no puede aplicar ciegamente el procedimiento de búsqueda solo al punto central, debe ser un poco más inteligente.

Mientras busca en el árbol KD para sus puntos, cada vez que debe elegir el niño izquierdo o derecho para buscar, verifique si el plano de división está a la izquierda de su círculo, lo intersó, o está a la derecha del círculo.

Si el plano de división está a la izquierda de su círculo, debe continuar buscando en el niño derecho y viceversa.Sin embargo, cuando el plano de la división se intersecta su círculo, debe buscarlos a los niños.