2D поиск ближайшего соседа для движущихся точек

Question

Я хочу сделать симуляцию скопления, как описано здесь .

Для этого мне нужно найти ближайших соседей каждой из моих 2D точек.Однако я не могу использовать статическую структуру данных, такую ​​как дерево kd, потому что точки всегда движутся ...

Какая хорошая (простая) структура данных / библиотека, способная достичь этого?Я работаю с C ++ ...

Answer 1

Люди изучили эту проблему. Важным ключевым словом является кинетика, при поиске работы в этой области.

Answer 2

Может быть, вы хотите попробовать квадродерево или пространственный индекс?В чем проблема с деревом кд?В основном, когда у края есть стая / точки, вы можете пропустить проверку столкновения с краями далеко.Пространственный индекс может быть квадродеревом, r-деревом, kd-деревом или гильбертовым r-деревом.Лучший ответ можно прочитать здесь: Приближенный, инкрементный алгоритм ближайшего соседа для движущихся тел

"То есть рекурсивное разбиение" мира "на граф с четырьмя подузлами в каждом. Деревозатем можно быстро проверить, какие объекты находятся в определенном квадрате мира, и отбросить остальные. Очень эффективная техника отбора, часто используемая для повышения производительности обнаружения столкновений в играх. "