7

I want do do some flocking simulation, as described here.

For this I need to search for the nearest neighbours of each of my 2D points. However, I cannot use a static data structure like a k-d tree because the points are always moving...

What's a good (easy) datastructure/library that is able to achieve this? I'm working with C++...

Yakov Galka
  • 70,775
  • 16
  • 139
  • 220
Jan Rüegg
  • 9,587
  • 8
  • 63
  • 105
  • You might get some ideas from http://stackoverflow.com/questions/6871682/approximate-nearest-neighbour-algorithm-for-moving-bodies – Don Reba Aug 07 '11 at 09:14

2 Answers2

6

People have studied this problem. The important keyword is kinetic, when looking for work in this ares.

carlosdc
  • 12,022
  • 4
  • 45
  • 62
2

Maybe you want to try a quadtree or a spatial index? What's the problem with a k-d tree? Basically when have the edge the flock/points you can skip checking collision with edges far away. A spatial index can be a quadtree, r-tree, kd-tree or hilbert r-tree. A better answer can be read here: Approximate, incremental nearest-neighbour algorithm for moving bodies

"That is, recursively partition the "world" into a graph with four subnodes each. The tree can then quickly check which objects are inside a particular square of the world and discard the rest. A very effective culling technique often used for improving performance of collision detection in games."

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
  • Isn't a k-d tree (or a quadtree, for that matter) static? Meaning you have to rebuild it in each step, after all the points have moved? – Jan Rüegg Aug 07 '11 at 10:01
  • The idea of a quadtree is to reduce the 2d complexity to a 1d complexity. When you recursivley traverse the tree depth-first or breadth-first it becomes a simple task to fill the full tree? – Micromega Aug 07 '11 at 10:08
  • I guess a quadtree would work, sort of. However, simply iterating through all neighbours seemed to be fast enough for me... – Jan Rüegg Nov 28 '12 at 11:29