Как найти площадь пересечения двух прямоугольников?
Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно: (x1,y1) — левая нижняя точка первого прямоугольника (x2,y2) — правая верхняя точка первого прямоугольника (x3,y3) — левая нижняя точка второго прямоугольника (x4,y4) — правая верхняя точка второго прямоугольника И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.
Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 14 дек 2017 в 21:45
Oleksii Havryshkiv Oleksii Havryshkiv
111 1 1 золотой знак 1 1 серебряный знак 12 12 бронзовых знаков
@Igor просто у меня есть много прямоугольников которие нужно перебирать одни с другими. И не могу понять как найти площадь пересечения каждого с каждим. Как их перебратить и пересекаются ли они я знаю. А вот етого понять не могу. Так как ети прямоугольники могут пересекатся с разних сторон. Если знаете, то помогите пожалуйста
14 дек 2017 в 21:52
Можно для обоих найти общий прямоугольник, а затем умножить его ширину на высоту.
14 дек 2017 в 21:56
@VladimirGamalyan да ну как найти нужное нам пересечение.
14 дек 2017 в 21:58
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
#include /* x1, y1 - левая нижняя точка первого прямоугольника x2, y2 - правая верхняя точка первого прямоугольника x3, y3 - левая нижняя точка второго прямоугольника x4, y4 - правая верхняя точка второго прямоугольника */ int f(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
Алгоритм нахождения площади пересечения
Вот задача, но мне не нужен код, помогите с алгоритмом нахождения площади пересечения.
Напишите программу, которая находит площадь пересечения, то есть общей части двух прямоугольников. Каждый прямоугольник задается координатами двух произвольных противоположных углов. Стороны прямоугольников параллельны осям координат.
Ваша программа должна вводить с клавиатуры числа x1, y1, x2, y2, x3, y3, x4, y4. Числа xi, yi будут вводиться в i-строке (1≤i≤4) и разделяться одним пробелом. Точки (x1, y1) и (x2, y2) – координаты двух противоположных углов первого прямоугольника. Точки (x3, y3) и (x4, y4) – координаты двух противоположных углов второго прямоугольника.
Числа xi, yi – целые; 0≤xi, yi≤30000; оба прямоугольника имеют ненулевую площадь.
Ваша программа должна вывести на экран одно число S – площадь общей части двух введенных прямоугольников. Если введенные прямоугольники не имеют общих точек, то ваша программа должна вывести на экран число 0.
Голосование за лучший ответ
собственно, всё сводится к нахождению пересечений отрезков (x1, x2) ∩ (x3, x4) и отрезков (y1,y2) ∩ (y3, y4)
а пересечение отрезков (a, b)∩(c, d) посчитать легко: это (max(a,c), min(b,d)).
если max(a,c) > min(b,d), то пересечение пустое
так что программа простая:
1) приводишь прямоугольники (xi, yi) — (xj, yj) к «нормальному» виду
xi < xj, yi < yj
2) находишь пересечения отрезков
(x1, x2) ∩ (x3, x4) = (xA, xB)
(y1, y2) ∩ (y3, y4) = (yA, yB)
3) если пересечения не пустые, считаешь площадь прямоугольника (xA, yA) — (xB, yB)
aGGa7 / Rectangles
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| using System; |
| namespace Rectangles |
| public static class RectanglesTask |
| // Пересекаются ли два прямоугольника (пересечение только по границе также считается пересечением) |
| // работает от обратного, если значения стороны одного прямоугольник больше чем значение прямо противоположной стороны другого прямоугольника |
| // значит они не пересекаются. |
| public static bool AreIntersected(Rectangle r1, Rectangle r2) => r1.Top > r2.Bottom || r1.Left > r2.Right || r2.Top > r1.Bottom || r2.Left > r1.Right ? false : true; |
| // Площадь пересечения прямоугольников |
| // решение почерпнуто из https://ru.stackoverflow.com/questions/758529 |
| // вкратце: по оси Х: берется наибольшое значение от левой точки двух прямоугольников, |
| // берется наименьшее значение от правой точки двух прямоугольников, из правой точки вычитаем левую и если это значение больше 0 |
| // прямоугольники пересекаются, и эта вычисленная величина равно длинне необходимой площади пересечения. По оси У аналогично. |
| public static int IntersectionSquare(Rectangle r1, Rectangle r2) |
| int leftIntersection = Math.Max(r1.Left, r2.Left); |
| int topIntersection = Math.Min(r1.Bottom, r2.Bottom); |
| int rightIntersction = Math.Min(r1.Right, r2.Right); |
| int bottonIntersection = Math.Max(r1.Top, r2.Top); |
| int widhtIntersection = rightIntersction — leftIntersection; |
| int heightIntersection = topIntersection — bottonIntersection; |
| if (widhtIntersection < 0 || heightIntersection < 0) |
| return 0; |
| else return widhtIntersection * heightIntersection; |
| > |
| // Если один из прямоугольников целиком находится внутри другого — вернуть номер (с нуля) внутреннего. |
| // Иначе вернуть -1 |
| // Первый прямоугольник находится во втором, если во втором находятся две противоположные вершины (по диагонали) первого, для другого прямоугольника все тоже самое но наоборот. |
| public static int IndexOfInnerRectangle(Rectangle r1, Rectangle r2) => r1.Left = r1.Top && r2.Bottom = r2.Top && r1.Bottom |
| > |
| > |
Как найти площадь пересечения двух прямоугольников
-kirito- → TheForces Round #25 Editorial
elshiko → Квалификационный раунд Yandex Cup 2023
plourde27 → California Informatics Competition (CALICO) Fall ’23
Yhlas_Y → Favourite problem
islamicTerrorist69 → Facing problem in dynamic programming
SilverSurge → CSES Range Queries: Polynomial Queries
127.0.0.1 → Codeforces Round 907 (Div. 2)
_thor__ → Codeloop 2023: A Knockout Tournament Based Coding Contest
Yhlas_Y → IDE for cp
MikeMirzayanov → Please, read this
Imakf → Codeforces Round 906 Editorial
noomaK → IEEEXtreme 17.0 Problems Discussion
chenjb → Rescheduling of World Finals 22&23
anmolsainiii23 → Confused Regarding Cses 2nd DP Question
stdfloat → Is CF enough for IZHO, IOI?
DeadPixel99 → Help needed!
Vladosiya → Codeforces Command Lines (2023-10-06)
-kirito- → Invitation to TheForces #25 (5^2-Forces, TheForces-Rated, Prizes!)
one_autum_leaf → Find the number of rectangles of same color in a matrix
ryuukumar → What to learn to solve 1300 rated questions?
Imakf → Codeforces Round 906 (Div. 1, Div. 2)
74TrAkToR → Codeforces Round #904 (Div. 2) Editorial
whynesspower → Reverse check the questions: ChatGPT
aryang22 → Perhaps you should wait a little before giving up.
Alpha_Info → Listen to music?
Блог пользователя serproc
Автор serproc, 11 лет назад ,
Долгое время не могу решить задачу. Дано 100 000 прямоугольников. Стороны параллельны осям координат. Все координаты целые и убираются в 4 байта. Нужно найти на сколько замкнутых фигур разбивают плоскость эти прямоугольники и найти площадь наибольшей фигуры. за N^2 не катит. Думал над деревом отрезков, но не могу придумать, как его применить.
дерево отрезков, прямоугольники
Комментарии (11)
Показать архивные | Написать комментарий?
11 лет назад , # |
Что подразумевается под замкнутой фигурой?
11 лет назад , # ^ |
Подразумевается область, ограниченная сторонами некоторых прямоугольников, внутри которой не проходят другие прямые, я полагаю
11 лет назад , # |
Так или иначе, видимо, сканирующая прямая должна помочь.
11 лет назад , # |
А можно ссылку на задачу? Если, конечно, ссылка существует.
11 лет назад , # ^ |
Не думаю. Эта задача была позавчера на корпоративном контесте компании Samsung (только для сотрудников). Я так полагаю, автор блога в нем участвовал, как и я=). Ссылка-то существует, но она приватна и зайти по ней можно, только если ты зарегистрирован в системе. Так что, если корейцы, конечно, не взяли эту задачу с топкодера, ссылку на задачу получить не удасться. Да я и не понимаю зачем она, если человек написал её условие, предварительно еще и переведя на русский язык=). Могу, если хочешь, написать оригинал условия на корейском или английском=).
11 лет назад , # |
← Rev. 2 → 
+7 
UPD: решение неверно, прошу прощения
Я не вдавался в детали, но сканлайн действительно помогает.
- Давайте проведем вертикальные прямые через все вертикальные стороны прямоугольников.
- Тогда вся плоскость поделится на слои, каждый слой будет разделен горизонтальными отрезками.
- Происходит два типа событий: появился новый прямоугольник и исчез прямоугольник.
- В каждый момент мы работаем с каким-то слоем. Слой будем представлять в виде нескольких блоков (прямоугольников, на которые делится этот слой). Для каждого блока можно поддерживать его площадь (включая ту, которая лежит вне текущего слоя).
- При добавлении нового прямоугольника часть блоков закрывается (из их площадей нужно взять максимум и к ответу-количеству прибавить, собственно, их количество), и появляются новые. Часть из них по x-координатам границ совпадают со старыми и еще четыре появляются по краям добавленного прямоугольника. Их площадь тоже посчитать несложно.
- При закрытии прямоугольника удаляются две границы, соответственно, площади кусков, которые они разделяли складываются.
Все операции умеет делать декартово дерево (максимум на отрезке, добавить элемент в середину, удалить элемент). Еще надо очень аккуратно смотреть на совпадающие y-координаты. Возможно, я где-то ошибся, извините, если так.
11 лет назад , # ^ |
Маловато информации поддерживаешь. Как обрабатывать замкнутые компоненты с дырками внутри (например, бублик, получающийся из двух кнцентрических квадратов)? Тебе как-то нужно помнить информацию о связности тех фрагментов, которые у тебя сейчас есть.
11 лет назад , # ^ |
Да, ты прав, я чушь написал. Надо как-то поддерживать какой отрезок в какой компоненте, но это пока непонятно как, потому что компонент может быть квадрат и при открытии-закрытии прямоугольника куча всего меняется.
11 лет назад , # |
← Rev. 5 → -13
Сегодня на межфакультетской в КПИ была упрощенная версия. Надо было найти количество пар прямоугольников, которые имеют хоть одну общую точку.
10 лет назад , # |
← Rev. 2 → 0
А это не задача на раскраску? Мы принимаем на вход координаты прямоугольника (х1,у1), (х2,у2), красим область плоскости, ограниченную этими точками, в цвет равный номеру запроса, храним все полученные покраски в дереве отрезков, потом каким-то образом определяем число различных сочетаний цветов на одном участке плоскости(сканлайном, видимо) и пытаемся параллельно считать площадь каждой новой найденной области и хранить максимальную площадь.
10 лет назад , # |
Поясните, пожалуйста, что именно имеется в виду под разбиением плоскости. Прямоугольник считается закрашенным или нет? Иными словами, на тесте
0 0 2 2 1 1 3 3 количество областей будет 1 или 3 (не считая внешней грани)?
0 0 3 1 0 0 1 3 2 0 3 3 0 2 3 3 2, 9 или еще сколько-то? (тест — четыре прямоугольника, опоясывающих квадрат 1 1 2 2).
Если правильное понимание — то, в котором прямоугольники закрашены, то задача сводится к тому, чтобы понять, какие связные компоненты образуют прямоугольники (легко делается сканлайном), а потом отдельно посчитать площадь каждой из них, а также всех внутренних частей (их уже может быть квадрат, это я еще не знаю, как делать быстро).