TexxTyRe
@TexxTyRe
Software Developer

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

Я правда не понимаю как решить данную задачу.
Найти общу площадь всех прямоугольников - это легко, очевидный алгоритм. Но как быть, если они пересекаются?
К примеру, у меня 5 прямоугольников. 5 прямоугольник лежит на 3 и 4. От какого из них мне рассчитывать общую площадь? А если их 100? Если использовать условия, то получится только последовательность. 2-ой будет рассчитываться от 1-го, 3-ий от 2-го, 4-ый от 3-го. Если использовать цикл, то 5-ый может вообще сразу же от 1-го рассчитываться.
  • Вопрос задан
  • 3040 просмотров
Решения вопроса 1
@hoha
Уточнение.
Общей площади (накрываемой)?
или общей площади пересечения?
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Mrrl
@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)) не знаю.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы