移動ポイントの2D最近傍検索

Question

hereと記載されているように、いくつかの植毛シミュレーションを行います。

このためには、私の2D点のそれぞれの最近傍を検索する必要があります。しかし、ポイントは常に動いているので、私はk-dツリーのような静的なデータ構造を使うことができません。

これを達成するのに良い（簡単な）データ構造/ライブラリはありますか？私はC++で作業しています...

Answer 1

多分、四分木または空間インデックスを試したいですか？ k-dツリーの問題は何ですか？基本的にフロック/ポイントのエッジを持っている場合、遠くのエッジとの衝突をチェックすることはできません。空間インデックスは、クォード・ツリー、rツリー、kdツリーまたはヒルベルトrツリーにすることができます。より良い答えはここで読むことができます：Approximate, incremental nearest-neighbour algorithm for moving bodies

"つまり、再帰的に4つのサブノードを持つグラフに分割します。ツリーは、どのオブジェクトが世界の特定の四角形内にあるかを素早くチェックし、休止。ゲームでの衝突検出のパフォーマンスを改善するためによく使用される非常に効果的なカリング技術。

Answer 2

人々はstudiedこの問題があります。重要なキーワードは、このアレスで仕事を探しているときに運動です。