Алгоритм нахождения сплошного многоугольника из пересекающихся прямоугольников?

Question

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

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

Многоугольник будет просто списком вершин, где последняя совпадает с первой

Вот изображение того, о чем я говорю:

Спасибо!

Answer 1

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

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

Редактировать: есть еще один вопрос, в котором есть код, который, кажется, решает вашу проблему:

Алгоритм объединения смежных прямоугольников в многоугольник