Создание графика из двумерного пространства, заполненного кружками

Question

Я заполняю двумерное пространство кружками случайного положения и радиуса.

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

Мой вопрос: Существует ли эффективный способ создания такого рода графиков?

Очевидно, существует метод грубой силы, состоящий только в проверке каждого круга. Я также подумал, что, возможно, я могу наложить сетку на 2-D плоскости и сортировать круги, чтобы легко найти круги в определенной области.

Вот пример того, с чем я работаю:

Answer 1

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

Sort all circles by x coordinate of center
Maintain a list L of circles, sorted by y coordinate of center, initially empty
For each circle C1 in order of x coordinates:
  Drop all elements C2 from L where x2 < x1 - 2*R (or x2 < x1 - r2 - R)
  For each circle C2 in L where |y1 - y2| < r1 + R:
    Check C1, C2 for intersection, possibly add to result
  Add C1 to L, maintaining order by y coordinates

L может быть красно-черным деревом или чем-то подобным, когда выполнение запроса диапазона (а именно y1 - r1 - R < y2 < y1 + r1 + R) просто. Но для эффективного удаления элементов, когда они выходят за пределы диапазона, вам может понадобиться вторая структура, скорее всего, стек (с ослабленным пределом - 2*R) или очередь с приоритетами (с более узким пределом - r2 - R).

Если R близко к типичному размеру ваших кругов, это должно работать хорошо. Если нет, то четырехугольное дерево могло бы быть лучше, если бы вы посещали соседние ячейки только в том случае, если вы действительно столкнулись с большим кругом, вместо того, чтобы тратить работу просто потому, что еще может быть более большой круг.