Я хочу симулировать стадо, как описано здесь.
Для этого мне нужно искать ближайших соседей каждой из моих 2D точек. Однако я не могу использовать статическую структуру данных, такую как дерево k-d, потому что точки всегда перемещаются...
Какая хорошая (простая) структура данных/библиотека способна достичь этого? Я работаю с С++...
Может быть, вы хотите попробовать дерево квадрантов или пространственный индекс? В чем проблема с деревом k-d? В основном, когда у края стадо/точки, вы можете пропустить проверку столкновения с краями далеко. Пространственный индекс может быть деревом квадрантов, r-деревом, kd-деревом или гильбертовым r-деревом. Лучший ответ можно прочитать здесь: Приблизительный инкрементный алгоритм ближайшего соседа для движущиеся тела
«То есть рекурсивно разбить «мир» на граф с четырьмя подузлами в каждом. Затем дерево может быстро проверить, какие объекты находятся внутри определенного квадрата мира, и отбросить остальные. Очень эффективный метод отбраковки, часто используемый для повышения производительности обнаружение столкновений в играх».
Люди имеют изучение эта проблема. Важным ключевым словом при поиске работы в этой сфере является кинетика.
