开发者

2D nearest neighbour search for moving points

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 开发者_如何学Pythonbecause the points are always moving...

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


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


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜