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

Question

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

Хорошее объяснение, Гарет. Я пытаюсь понять, как добиться обратного решения, то есть как начать с набора прямоугольников и привести к многоугольнику.

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

Как мне избавиться от точек, которые составляют перекрывающиеся края?

Answer 1

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

Разделите горизонтальные сегменты на y. Для каждого y каждый сегмент вызывает два события: событие начала для хвоста и событие остановки для головы. Сортируйте события по x (обратите внимание, что событие остановки для сегмента, ориентированного слева, предшествует соответствующему событию запуска). Инициализировать переменную sign = 0, затем перебрать, выполняя sign += 1 на каждом стартовом событии и sign -= 1 на каждой остановке. Всякий раз, когда sign идет от 0 в 1, начать ориентированный сегмент с хвостом в текущем месте развертки. Всякий раз, когда sign идет от 1 в 0, конец этого сегмента с его головой в текущем месте развертки, отбрасывая его, если он вырожден. Точно так же всякий раз, когда sign идет от 0 в -1, начать ориентированный сегмент с головой в текущем месте развертки. Всякий раз, когда sign идет от -1 в 0, конец этого сегмента с хвостом в текущем месте развертки, отбрасывая его, если он вырожден.