2D Nearest Neighbor Search for Moving Points

Question

I want to do some flocking simulations as described here .

To do this, I need to find the nearest neighbors of each of my 2D points. However, I cannot use a static data structure such as the kd tree, because points always move ...

What is a good (simple) data structure / library capable of achieving this? I work with C ++ ...

Answer 1

Perhaps you want to try the quadrant or spatial index? What is the problem with the kd tree? Basically, when there is a herd / point edge, you can skip checking for collisions with the edges far away. The spatial index can be a quadrant, an r-tree, a kd-tree, or a Hilbert r-tree. A more convenient answer can be found here: Approximate, incremental nearest neighbor algorithm for moving bodies

“That is, recursively divide the world into a graph with four pillows each. The tree can then quickly check which objects are inside a certain square of the world and discard the rest. A very effective selection technique that is often used to improve collision detection performance in games.” .

Answer 2

People have studied this problem. An important keyword is kinetic when you are looking for work in this area.