Как обзорно считают площадь объединения и пересечения многоугольников/прямоугольников?
Встретил задачу: даны несколько прямоугольников (а в более сложной версии — многоугольников), нужна площадь их объединения. Какие есть подходы и какой выбрать на олимпиаде? Интересует общая идея, не обязательно полный код.
2 ответа
Зависит от объектов.
Прямоугольники, площадь объединения — заметающая прямая (sweep line) + дерево отрезков. Двигаем вертикальную прямую слева направо; на левой стороне прямоугольника добавляем его y-интервал, на правой — убираем. Дерево отрезков с «координатным сжатием» хранит, какая суммарная длина по y сейчас покрыта хотя бы одним прямоугольником. Площадь = сумма по горизонтали (покрытая длина × ширина текущей вертикальной полосы). Сложность O(n log n).
Пересечение двух выпуклых многоугольников — клиппинг Сазерленда–Ходжмена. Последовательно «обрезаем» один многоугольник полуплоскостями, заданными рёбрами другого. Результат — выпуклый многоугольник, его площадь считаем шнуровкой. O(n·m) для n и m вершин.
Площадь пересечения через включение-исключение работает только для 2 фигур; для объединения многих — нет, потому что число членов растёт экспоненциально. Поэтому объединение многих фигур решают именно sweep line, а не формулой.
Выбор: прямоугольники → sweep+segtree; пара выпуклых → клиппинг; круги/произвольные → интегрирование/Грин, но это уже редкая и тяжёлая тема.
Пара практических замечаний. Для площади объединения прямоугольников альтернатива sweep line — координатное сжатие обеих осей и подсчёт по элементарным ячейкам: проще кодить (O((n) сеток)), но дороже по памяти/времени при больших n; хорошо для n до пары тысяч.
Для пересечения выпуклых ключевая идея клиппинга: каждое ребро многоугольника-«ножа» задаёт полуплоскость (через знак orient), и мы оставляем только ту часть, что внутри. Точки пересечения рёбер с границей полуплоскости считаем формулой пересечения прямых. Тут уже неизбежен double (координаты пересечений дробные), так что аккуратно с eps при финальной шнуровке.
И совет: если в задаче только прямоугольники со сторонами, параллельными осям — почти всегда имеется в виду sweep line, это «стандартная заготовка», её стоит иметь готовой.