Necesito encontrar para cada punto del conjunto de datos todos sus vecinos más cercanos. El conjunto de datos contiene aprox. 10 millones de puntos 2D. Los datos están cerca de la cuadrícula, pero no forman una cuadrícula precisa ...Todos los k vecinos más cercanos en 2D, C++
Esta opción excluye (en mi opinión) el uso de árboles KD, donde la suposición básica es que ningún punto tiene la misma coordenada xy la coordenada y .
Necesito un algoritmo rápido O (n) o mejor (pero no demasiado difícil para la implementación :-))) para resolver este problema ... Debido a que el impulso no está estandarizado, no quiero usar que ...
Gracias por sus respuestas o ejemplos de código ...
¿Podría darnos un ejemplo de lo que está buscando? –
posible duplicado de [Selección adecuada de la estructura de datos y el algoritmo para la búsqueda rápida de Vecino-vecino más cercano en 2D] (http://stackoverflow.com/questions/3944649/suitable-choice-of-data-structure-and-algorithm-for -fast-k-neighbor-neighbor-searc) – ybungalobill
No entiendo por qué no puedes usar kd-trees. Resumiré lo que creo que estás diciendo: dime dónde me estoy equivocando. Tienes un conjunto de puntos distintos de 10M. No se encuentran en una cuadrícula entera, pero están cerca, por ejemplo, hay un punto (2.01, 1.05) y otro (1.99,1.03).¿No podrías escalar los puntos para que todos estén en una cuadrícula entera y luego usar kd-trees? por ejemplo, los 2 puntos anteriores podrían ser (201, 105) y (199, 103). – corriganjc