@daniil14056

Как выглядит алгоритм нахождения пересечения 1000 объектов?

Как обрабатывать проверку пересечения 100-1000 объектов(окружностей в моем случае).
Есть область на которой хаотично появляются и движутся кто куда окружности, затем врезаются, как проверять пересечения этих окружностей. А то вышло что делаю O(n^2) операций проверки, каждую 1 секунду.

Нужен эффективный алгоритм. Или хоть на словах, порядок действий.

Читал про метод разделяющих плоскостей но не понял как там плоскости проекций находится.
  • Вопрос задан
  • 886 просмотров
Решения вопроса 1
FlashManiac
@FlashManiac
I am from Krypton!
Была такая же проблема в игре было много кораблей и снарядов. И надо было найти все пересечения снарядов со всеми кораблями. Алгоритм с простым перебором был жутко медленный. Поэтому мы сделали так:
Разбили пространство на виртуальные квадраты с размером size
Для этого мы создаем map и для каждой окружности мы ищем ее key.
key = Math.floor(circle.x / size) + "_" + Math.floor(circle.y / size)
if(!map[key]) map[key] = [];
map[key].push(circle);

Далее мы просто проходимся по ключам map и проверяем пересечения окружностей внутри квадрата. Получается, что проверок становится намного меньше благодаря группировки кругов в квадраты.

Так же можно оптимизировать проверку пересечений кругов. Для круга мы должны знать его радиус.
function isCollided(circle0, circle1)
{
      var maxDistanceSquared = circle0.radius + circle1.radius;
      maxDistanceSquared *= maxDistanceSquared;
      
      var dx = circle0.x - circle1.x;
      var dy = circle0.y - circle1.y;
      
      var currentDistanceSquared = dx * dx + dy * dy;
      
      return currentDistanceSquared < maxDistanceSquared;
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
GavriKos
@GavriKos
Вариантов на самом деле немало.

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

Ну и для проверки пересечений используйте не расстояние, а квадраты расстояний/радиусов - будет быстрее (хоть на сложность алгоритма и не повлияет)
Ответ написан
xmoonlight
@xmoonlight Куратор тега JavaScript
https://sitecoder.blogspot.com
Вариант 1:
Нужно, чтобы каждая окружность сама проверяла своё состояние и сообщала слушателю.
Как только создаётся окружность - вешаете на неё обработчик события столкновения.

Вариант 2:
Следите за центрами всех окружностей, чтобы контролировать столкновение.
Столкновение (касание): когда расстояние между двумя центрами окружностей равно сумме радиусов окружностей вокруг этих центров. И, соответственно, проверка на пересечение: расстояние - меньше или равно.
Проверка - итеративная:
1. После первой проверки - сортируем все пары центров с зазорами между кругами от самого близкого к самому дальнему.
2. При второй - проверяем, начиная с самого близкого и сразу рассчитываем скорость и вектор смещения. Теперь, добавляем скорость: сортируем от максимальной скорости с минимальным зазором к минимальной скорости с максимальным зазором.
3. При последующих используем информацию предыдущего шага для определения порога зоны "отсечения хвоста" при проверке по отсортированному списку: threshold.
Т.е., если мы видим, что ускорение или линейная скорость за заданное время не позволят им пересечься на этом фрейме, то мы их просто не проверяем и ставим метку: через сколько итераций мы будем проверять каждую из них (резервируем их для исключения на нескольких последующих итерационных проверках).

Таким образом, мы экономим "пустые" циклы при просчёте столкновений.
Ответ написан
leahch
@leahch
Я мастер на все руки, я козлик Элек Мэк :-)
Посмотрите в сторону r-tree/r-tree++ алгоритмов, но не совсем уверен, что это будет по скорости. Реализация для явы есть в mvstore, как раз ей пользуюсь, но у меня в основном статика и объектов на миллионы. Вам же наверное нужно строить дерево на все перемещения www.h2database.com/html/mvstore.html
И еще, только в памяти https://github.com/davidmoten/rtree
https://github.com/conversant/rtree
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
Элерон Москва
от 100 000 до 170 000 ₽
КУРС Москва
от 80 000 до 150 000 ₽
Gaskar Group Москва
от 100 000 ₽