Найти перекрывающиеся круги

Question

У меня есть прямоугольная область, где есть круги с равным радиусом. Я хочу найти, какие круги накладываются на другие круги (выход представляет собой список из 2-элементных наборов перекрывающихся кругов).

Я знаю, как проверить, перекрываются ли два круга (расстояние между их центрами меньше диаметра). Я могу выполнить эту проверку для каждой пары кругов, но мне было интересно, есть ли лучший алгоритм (быстрее, чем O(n^2)).

EDIT

Количество кругов, как правило, около 100 и перекрытий не будут происходить очень часто.

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

Answer 1

Учитывая новое объяснение заявления о проблеме, я бы рекомендовал другой подход.

Наложение квадратной сетки на поле битвы с шагом сетки, равным одному диаметру круга. Каждый круг может перекрывать не более четырех ячеек. В каждой ячейке сохраните список пересекающихся кругов (и обновите их при каждом перемещении).

Обнаружение потенциальных столкновений теперь займет около четырех тестов на ячейку/круг на круг, т. Е.близко к линейному времени.

Answer 2

Для простого решения вставьте центры в 2d-дерево и выполните запросы круглого диапазона вокруг каждого центра с радиусом запроса 2R. В хороших условиях это может быть O (N Log (N)).

---

В качестве альтернативы, просто отсортировать центры по X и попробовать все круги в своей очереди: по дихотомическому поиску, найти абсциссу Хс и сканировать Хс-2R и Хс + 2R, а затем проверить 2D расстояние.

Стоимость дихотомических поисков будет равна O (N Log (N)). Если круги равномерно распределены в квадрате стороны S, полоса ширины 4R содержит 4RN/S окружности, следовательно, общая стоимость сравнения 4RN²/S. Это хорошая производительность, если S велико (подумайте, что для N плотно упакованных кругов в квадрате S ~ 2R√N, следовательно, сравнение 2N√N).

Answer 3

Прямой ответ: вы не можете стать лучше O (n^2) вообще, так как круги могут потенциально перекрываться, поэтому вам нужно сгенерировать n^2 ответа.

Если вы уточните, вы можете получить более качественные ответы. Например, если то, что вы на самом деле пытаетесь найти, это найти граничные сферы в 2D-моделировании, вы можете извлечь выгоду из того факта, что сущности только перемещаются между кадрами, если круги разрежены, это отличается от того, когда они плотно упакованы и т. Д. Итак, дайте нам знать больше о том, что это такое.

EDIT: Вы редактировали свой вопрос - вы действительно ищете обнаружение столкновения в 2D-моделировании. Если вы посмотрите https://en.wikipedia.org/wiki/Collision_detection, они указывают на несколько алгоритмов именно для вашего случая.

Мне нравится тот, который подробно указан на этой странице, где вы держите один список ограничивающих интервалов на ось (2 в «2D») и нужно «работать» только тогда, когда эти ограничивающие интервалы (которые, по определению, мерное) изменение (т. е. там «состояние перекрытия»). Это удаляет O(n²) для случаев с хорошим поведением. Они не дают оценки сложности, но, поскольку она в основном сводится к сортировке, она выглядит более или менее O(n logn) для меня, и меньше, когда есть только минимальные изменения между кадрами.