Todos los k vecinos más cercanos en 2D, C++

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 ...

Fuente

2010-11-13 Ian

¿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

yo haría lo siguiente:

crear una cuadrícula más grande en la parte superior de los puntos.
Revise los puntos de forma lineal, y para cada uno de ellos, descubra a qué "celda" grande pertenece (y agregue los puntos a una lista asociada con esa celda).

(Esto se puede hacer en un tiempo constante para cada punto, acaba de hacer una división entera de las coordenadas de los puntos.)
Ahora ve a través de los puntos linealmente de nuevo. Para encontrar los 10 vecinos más cercanos solo necesita mirar los puntos en las celdas más grandes adyacentes.

Dado que sus puntos están distribuidos bastante uniformemente, puede hacerlo a tiempo proporcional al número de puntos en cada celda (grande).

Aquí es un pic (feo) que describe la situación:

enter image description here

Las células deben ser lo suficientemente grande para (el centro) y las células adyacentes para contener los 10 puntos más cercanos, pero lo suficientemente pequeño como para acelerar el cálculo. Podría verlo como una "función hash" donde encontrará los puntos más cercanos en el mismo cubo.

(Tenga en cuenta que en sentido estricto no O (n) pero por ajustar el tamaño de las células más grandes, usted debe acercarse lo suficiente. :-)

Fuente

2010-11-13 11:57:03 aioobe

No solo adyacente, desafortunadamente (considere que los puntos en la celda dos al este pueden estar más cerca que los puntos en la celda directamente al noreste , por ejemplo, este problema empeora en dimensiones más altas). Además, ¿qué sucede si las celdas vecinas tienen menos de 10 puntos en ellas? En la práctica, tendrá que "salir en espiral". –

No en este caso particular: * Los datos están cerca de la cuadrícula, pero no forman una cuadrícula precisa ... *. Al elegir celdas lo suficientemente grandes, puedes resolverlo así. – aioobe

¿Y qué hay de LSH? – Ian

He utilizado una biblioteca llamada ANN (aproximados más cercano es Vecino) con gran éxito. Utiliza un enfoque de árbol KD, aunque hubo más de un algoritmo para probar. Lo usé para la ubicación de puntos en una superficie triangulada. Puede tener algo de suerte con eso. Es mínimo y fue fácil de incluir en mi biblioteca simplemente al incluir su fuente.

¡Buena suerte con esta interesante tarea!

Fuente

2010-11-16 11:13:20

Todos los k vecinos más cercanos en 2D, C++

Respuesta

Cuestiones relacionadas