Quiero hacer algo de simulación de flocado, como se describe here.Búsqueda del vecino más cercano 2D para mover puntos
Para esto necesito buscar los vecinos más cercanos de cada uno de mis puntos 2D. Sin embargo, no puedo usar una estructura de datos estática como un árbol k-d porque los puntos siempre se están moviendo ...
¿Qué es una buena (fácil) estructura de datos/biblioteca que puede lograrlo? Estoy trabajando con C++ ...
¿Quizás quieras probar un quadtree o un índice espacial? ¿Cuál es el problema con un árbol k-d? Básicamente, cuando tienes el borde de la bandada/puntos, puedes omitir la colisión de chequeo con bordes muy alejados. Un índice espacial puede ser un quadtree, r-tree, kd-tree o hilbert r-tree. Se puede leer una mejor respuesta aquí: Approximate, incremental nearest-neighbour algorithm for moving bodies
"Es decir, partición recursiva del" mundo "en un gráfico con cuatro subnodos cada uno. El árbol puede verificar rápidamente qué objetos están dentro de un cuadrado particular del mundo y descartar el descanso. Una técnica de sacrificio muy efectiva que se usa a menudo para mejorar el rendimiento de la detección de colisiones en los juegos ".
No es un árbol kd (o un quadtree, para el caso) ¿estático? ¿Quiere decir que tiene que reconstruirlo en cada paso, después de que se hayan movido todos los puntos? –
La idea de un quadtree es reducir la complejidad 2d a una complejidad 1d. Cuando recursivley recorre el árbol en profundidad primero o ancho primero se convierte en una tarea simple para completar el árbol completo? – Bytemain
Supongo que un quadtree funcionaría, más o menos. Sin embargo, simplemente iterar a través de todos los vecinos parecía ser lo suficientemente rápido para mí ... –
Las personas tienen studied este problema. La palabra clave importante es cinética, cuando se busca trabajo en esta área.
Puede obtener algunas ideas de http://stackoverflow.com/questions/6871682/approximate-nearest-neighbour-algorithm-for-moving-bodies –