Нахождение общей площади, образованной объединением прямоугольников?

Question

[Ульян Романов]

Я правда не понимаю как решить данную задачу.
Найти общу площадь всех прямоугольников - это легко, очевидный алгоритм. Но как быть, если они пересекаются?
К примеру, у меня 5 прямоугольников. 5 прямоугольник лежит на 3 и 4. От какого из них мне рассчитывать общую площадь? А если их 100? Если использовать условия, то получится только последовательность. 2-ой будет рассчитываться от 1-го, 3-ий от 2-го, 4-ый от 3-го. Если использовать цикл, то 5-ый может вообще сразу же от 1-го рассчитываться.

Answer 1

[hoha]

Уточнение.
Общей площади (накрываемой)?
или общей площади пересечения?

Comments

[Ульян Романов]

Например, есть 2 прямоугольника - часть 2-го прямоугольника в части 1-го прямоугольника, нужна их общая площадь.

[hoha]

habrahabr.ru/sandbox/88849

очень простой алгоритм

[Ульян Романов]

hoha: Спасибо

[Mrrl]

hoha: Похоже, что этот алгоритм работает только для целых координат. Причём, для небольших - чтобы можно было успеть перебрать все клетки за разумное время.

[hoha]

Дык, плюсы и минусы - очерчены. :)

[Mrrl]

hoha: Так того, что я написал, нет ни в плюсах, ни в минусах... Про целые координаты - вообще ни слова.

[Ульян Романов]

Mrrl: а почему не будет работать с действительными координатами?

[Mrrl]

Ульян Романов:
Следом, мы проецируем прямоугольники на область А, т.е. координаты прямоугольников будут эквивалентны номерам некоторым элементам массива со смещением.

Затем начинаем заполнять этот массив. Элементы этого массива могут принимать два значения: 0 и 1. 0 означает, что это «клеточка» не принадлежит ни одному прямоугольнику, 1- принадлежит. Проверяем элементы области А на принадлежность прямоугольнику для каждого отдельного прямоугольника.

Эти фразы имеют смысл только если прямоугольник состоит из "клеточек", площадь которых равна 1. А это может быть только при целых координатах. Причём, если координаты будут хотя бы порядка миллиона, вы не дождётесь результата даже для двух прямоугольников (а массив не влезет в память).

Answer 2

[Mrrl]

Довольно просто решить за O(N^3).
Пусть координаты k-го прямоугольника - (x1[k],x2[k],y1[k],y2[k]).
Берёте все x1,x2 (их 2*N штук), сортируете, выкидываете одинаковые. Это проекции вершин на ось X. Обозначим полученный массив A.
Аналогично с y1,y2 - получается массив B (тоже длиной не больше 2*N).
Теперь перебираем прямоугольники C=[A[p],A[p+1]]*[B[q],B[q+1]] для всех p,q. Ни один из них не пересекается сторонами исходных прямоугольников, так что если центр C лежит в одном из исходных прямоугольников, то весь прямоугольник принадлежит объединению, если нет - то не имеет с ним общих внутренних точек. Суммируем площади всех прямоугольников, принадлежащих объединению, и пишем ответ.
Можно соптимизировать до O(N^2). Насчёт O(N*log(N)) не знаю.

Comments

[Mrrl]

mellinare: Координаты. Вершинами прямоугольника будут (x1,y1), (x1,y2), (x2,y2), (x2,y1). Сортируются только числа - отдельно иксы, отдельно игреки.
Если стороны не параллельны осям, задача заметно усложняется.

[Ульян Романов]

Mrrl: Можно вам на почту скинуть свое решение?

[Artem]

Mrrl: для параллельных осям этож не задача вообще. 100% речь идет про случайно расположенные прямоугольники

[Mrrl]

Artem: И за сколько вы её можете решить? За O(N*log(N)) справитесь? (для случая параллельных осям).

[Artem]

Mrrl: за O(infinity) решу. главное что решение есть и в вопросе вроде спрашивалось про решение вообще а не решение за оределенную скорость.
хз, мне задача "с параллельные осям" показалась до ужаса тривиальной

[Mrrl]

Artem: Как знаете. Мне эта задача встречалась в реальном проекте, и написанное там решение не нравится до сих пор - громоздкое и неэффективное. С тривиальными задачами такого обычно не бывает.