Проверьте на сталкивающиеся круги

Question

У меня есть несколько кругов, я знаю их X, Y и r. Я хочу проверить, не сталкиваются ли ЛЮБОЕ из них с ЛЮБОМ другим ... Способ проверки прост:

r ₁ + r ₂ 1 -x ₂ ) ² + (у ₁ -й ₂ ) ² )

но я должен проверить все со всеми? Это дает мне сложность O (n ² ), и я хочу избежать этого: /

Answer 1

Попробуйте взглянуть на KD-дерево в соответствии со структурой.сначала вы должны рассматривать круги как квадраты, намного меньшие сложности для вычисления пересечения, чем помещать эти квадраты в модифицированное дерево KD, это потребует некоторого размышления, но, надеюсь, ничего экстремального ... Способ работы дерева kd состоит в том, что он отменяетполовина возможных совпадений на основе некоторых критериев для каждого уровня дерева.Ищите это на вики.Удачи в вашей проблеме :)

Answer 2

Используйте квадратные ограничительные рамки в качестве простого начального теста.Только затем переходите к кругу.

Также

r1+r2 < sqrt((x1-x2)² + (y1-y2)²)

можно переписать в виде:

(r1+r2)² < (x1-x2)² + (y1-y2)²

, который удаляет этот неприятный sqrt ()

Answer 3

Вы можете разделить свое пространство на регионы, например:

1. Вычислить 2D AABB - ограничивающий прямоугольник для всех окружностей
2. Разделите его на четыре подполя
3. Каждому из вложенных блоков назначается круг, если круг даже слегка пересекает такой блок, то он должен быть помещен в такой блок. Это означает, что круг может быть назначен нескольким клеткам.
4. Выполните итерацию каждого круга, затем отметьте, какому блоку он был назначен, и вычислите столкновение только с кругами из этого блока.

В 2. вы можете сделать много подразделений, в зависимости от размера вашего пространства, а также, если одному кругу назначено много кругов, то подразделите его дальше.

Answer 4

Есть много кругов?Лучшее, на мой взгляд, это устанавливать круги в массивах.Поэтому у вас будет массив кругов, который не только облегчит их инициализацию, но и все в одном месте.

Следующая часть - взять круг и дать ему функцию для проверки столкновения.например,

void isCol (Массив [круги], текущие векторы, в которых находится этот круг и т. д.);

Если много кругов

цикл for, который проходит через массив, проверяя все значения X, Y и радиуса и проверяет, находятся ли они в определенной пустоте круга.Однако вы всегда должны проверять, является ли круг, на который вы смотрите, именно вами, если это так, то пропустите этот круг.если они находятся в каком-либо регионе, то рассчитайте, сталкиваются ли они с вами или нет, и (укажите здесь, если столкновение имеет последствия).

Если есть только несколько кругов, пропустите право на проверку на столкновение.

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

Надеюсь, это поможет.