Группы пар пересекающихся прямоугольников

Question

У меня есть коллекция пересекающихся прямоугольников. Используя алгоритм развертки линии, я вычислил пары всех пересекающихся прямоугольников. Теперь я хотел бы, чтобы эффективный алгоритм группировал все пересекающиеся прямоугольники, что-то похожее на поиск островов. Вход: (1,2) (2,3) (3,4) (5,6) (6,7) -> Пары, рассчитанные по алгоритму развертки линии. Ouput: (1.2.3.4) (5,6,7)

Для линии развертки я называюсь axis‐aligned rectangles intersection

Answer 1

Чтобы сделать набор союзного для всех связанных прямоугольников с использованием пары пересекающихся единиц, вы можете использовать очень эффективный алгоритмический подход с disjoint-set/union–find data structure.