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

Question

Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping

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

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

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

Answer 1

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

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