Как написать алгоритм поиска соседних элементов?

Есть анимация, в которой присутствует около 200 объектов, у которых в каждом кадре постепенно (довольно медленно) изменяются координаты. Нужен алгоритм, который будет очень оптимально выполнять поиск новых связей. Связь должна устанавливаться, когда расстояние между объектами меньше определённого числа ( при этом не обязательно устанавливать связь прямо в том же кадре, в котором расстояние становится достаточно близким, меня устроит и вариант, когда связь будет установлена через несколько кадров после того, как расстояние стало достаточно маленьким).

Если банально перебирать расстояния для каждой пары точек, то на каждом кадре будет цикл на 40000 пар. Довольно большая нагрузка вообще говоря. Необходимо сохранив равномерность нагрузки на кадр сократить кол-во вычислений в одном кадре минимум в 10-20 раз (а лучше больше). У меня есть определённые идеи, но всё же хотел послушать мнения других.
  • Вопрос задан
  • 1530 просмотров
Решения вопроса 1
@maxfox
Если хранить координаты в отсортированном массиве (X и Y отдельно), то проверять нужно будет только ближайших соседей, до тех пор, пока разница координат не превысит вашего минимального расстояния. Такая оптимизация тем эффективнее, чем меньше данное расстояние относительно размеров поля. Плюс кэшировать результаты сравнений, чтобы не проверять уже проверенные пары. Далее можно убивать кэш не каждый кадр, можно в четных кадрах искать вверх по массиву, а в нечетных - вниз и т.п. Но это уже по факту, если потребуется.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
sergiks
@sergiks Куратор тега JavaScript
♬♬
Идея с отдельной работой по X и по Y неплохо работает. На каждом кадре проверяем каждую из 200 точек (это совсем не много).

Сортируем массив точек по их X-координате. Двигаемся слева направо, выбирая очередную точку.

Смотрим от неё влево (чтобы не проверять одну связь дважды, выбираем полуплоскость от точки) и отбираем только те точки, чей X отличается не более, чем на radius.

Из них смотрим только на те, у которых Y не более, чем на radius отличается (уже в любую сторону: и вверх и вниз).

У них проверяем уже евклидово расстояние – корень из суммы квадратов расстояний по X и по Y – чтобы было не больше radius. У таких есть «связь» – рисуем им ребро.

Работающий fiddle (неминифицированный исходник на github)
538264abb31847baa28fe05e015ac13c.png

На компе даёт около 60 fps, на мобильнике от 40 до 55, т.е. совершенно приемлемая скорость при 200 точках.

Первая версия ответа

Интересна ситуация, наихудшая для оптимизации: когда за 1 кадр может поменяться максимальное число связей. Предположу, что это сетка из равносторонних треугольников, где длина ребра равна «триггерной» дистанции:
картинка треугольной сетки
5297fe1c584f4551aca5b77a2a987549.jpg
Тут большинство точек, кроме крайних, взаимосвязаны. У каждой по 6 ближайших соседей. Примерно 200 * 6 / 2 = 600 связей (чуть меньше из-за краёв).

Если такую сетку пропорционально увеличить на любую малую величину, сразу все связи порвутся, их станет ноль. Пусть на месте останется, скажем, левый верхний угол сетки. Тогда наибольший путь проделает нижний правый угол. Тут вопросы к особенностям вашей задачи:
  1. округляются ли координаты до целых или до какой-то точности?
  2. какой наибольший путь может проделать за один кадр точка?

В идеальном мире всем достаточно проделать бесконечно малый шаг, и, вуаля!, было 600 связей, стало 0. Такой же шажок назад – не было связей, и вот их 600. Т.е. надо бы в каждый кадр проверять 600 ребер. Считать это за теоретический предел оптимизации?

Сущности
Точки и рёбра. Ребро ссылается на две точки. Точка ссылается на рёбра. Ребро имеет длину и, в зависимости от длины, может быть «видимым».

Важнее всего следить за рёбрами, длина которых близка к пороговой – и с меньшей и с большей стороны. Такие стоит проверять почти каждый кадр, т.к. статус ребра может поменяться за один кадр. Прочие рёбра и кандидаты в рёбра проверять можно изредка.

Можно давать рёбрам веса, пропорциональные желаемой частоте их обновления. Скажем, от 0 до 1. Вес равный 1 значит, что нужно проверять каждый кадр. Например, вес W = Math.max(0, D - Math.abs( length - D))/D, где D – пороговая дистанция.

Остаётся сделать механизм, отбирающий рёбра в работу на очередном кадре, исходя из их весов. Запоминать время, когда ребро было обновлено. Приоритет его попадания в обработку равен W * (time - timeUpdated)
Ответ написан
ThunderCat
@ThunderCat Куратор тега JavaScript
{PHP, MySql, HTML, JS, CSS} developer
Кластерный анализ?
Если учились в вузе должны были проходить, это как раз тот случай когда академические знания могут пригодиться.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы