Как найти площадь пересечения двух прямоугольников?
Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно: (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 растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
Координаты пересечения двух прямоугольников
здравствуйте. сегодня наткнулся на такую задачу: определить координаты левого верхнего и правого нижнего углов общей части 2-х прямоугольников, которые задаются так же координатами левого верхнего и правого нижнего углов. стороны прямоугольников параллельны координатным осям. случаев получается чуть больше чем дофига и как их все учесть? написать нужно на с++. может есть уже готовый алгоритм(знаю что есть для площади, а для координат что-то не видел).
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Площадь пересечения двух прямоугольников
Помогите пожалуйста, не могу написать код. Вот условие. Напишите класс, который позволит.
Площадь пересечения двух прямоугольников
Даны 4 координаты: 2 из них — координаты противоположных вершин первого прямоугольника (не.
Найти точки пересечения двух прямоугольников
Всем привет, очень интересует метод решения следующей задачи: Имеется 2.
Координаты пересечения двух окружностей
На вход даются целочисленные координаты двух окружностей и целочисленные их радиусы, которые не.
Регистрация: 06.05.2009
Сообщений: 34
Сообщение было отмечено Agent Smith как решение
Решение
Попробуйте так:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
//пересекающиеся прямоугольники #include struct point { int x,y; } struct rectangle { point lt; //left top point rb; //right bottom } int min(int a, int b); int max(int a, int b); int main() setlocale(NULL,"rus"); rectangle a,b,c; cout"Введите координаты первого прямоугольника:"endl; cout"верхний левый угол:\tx = "; cin>>a.lt.x; cout"\ty = "; cin>>a.lt.y; coutendl"правый нижний угол:\tx = "; cin>>a.rb.x; cout"\ty = "; cin>>a.rb.y; coutendl"Введите координаты второго прямоугольника:"endl; cout"верхний левый угол:\tx = "; cin>>b.lt.x; cout"\ty = "; cin>>b.lt.y; coutendl"правый нижний угол:\tx = "; cin>>b.rb.x; cout"\ty = "; cin>>b.rb.y; // варианты пересечения прямоугольников if(a.rb.y>b.lt.y else { c.lt.y=min(a.lt.y,b.lt.y); c.lt.x=max(a.lt.x,b.lt.x); c.rb.y=max(a.rb.y,b.rb.y); c.rb.x=min(a.rb.x,b.rb.x); cout"Координаты пересечения:"endl; cout"левый верхний угол: x = "c.lt.x"\t y = "c.lt.yendl; cout"правый нижний угол: x = "c.rb.x"\t y = "c.rb.yendl; } return 0; } int min(int a, int b) { if(ab) return a; else return b; } int max(int a, int b) { if(a>b) return a; else return b; }
Как найти пересечение прямоугольников по координатам
Imakf → Codeforces Round 906 Editorial
whynesspower → [URGENT] Codeforces need anti-scrapping
_Firdavs_Aminov_ → Dark theme Codeforces
whynesspower → Reverse check the questions: ChatGPT
-arma- → SQRT decomposition for beginners
elshiko → Квалификационный раунд Yandex Cup 2023
atcoder_official → Panasonic Programming Contest 2023（AtCoder Beginner Contest 326） Announcement
MercilesslyMan → Vim for competitive programming
AquaMoon → Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) Editorial
74TrAkToR → Codeforces Round #904 (Div. 2) Editorial
Imakf → Codeforces Round 906 (Div. 1, Div. 2)
Sokol080808 → Codeforces Round #881 (Div. 3) Разбор
127.0.0.1 → Codeforces Round 907 (Div. 2)
arpit_aditya → Cherry Pickup Leetcode 741 — Why is this approach giving wrong Answer?
yrhiba → I think tomorrow is the day!
Loserinlife → Sum of kth smallest distances.
nor → [Feature Request/Informational Content] Consider adding the Boost C++ library on Codeforces
chenjb → Rescheduling of World Finals 22&23
SkippedSolution → DP bitmask or DNC ?
purp4ever → Teams Qualified for Africa and Arab Collegiate Programming Championship — ACPC 2023 (+teens)
awoo → Разбор Educational Codeforces Round 115
nagitaosu → Codeforces rating distribution
-kirito- → Invitation to TheForces #25 (5^2-Forces, TheForces-Rated, Prizes!)
Esomer → Math and informatics competition, with prizes!
74TrAkToR → Codeforces Round #905 (Div. 1, Div. 2, Div. 3) Editorial
как проверить пересекаются ли два прямоугольника
Часто при разработке различных интерфейсов возникает задача проверки пересекаются ли два заданных прямоугольника. Решение в данном случае очень простое, однако мной нигде не найденное и поэтому в очередной раз пришлось писать свой велосипед. При этом грабли на которые наступают разработчики одни и те же, а решение выдаваемые гуру на форумах работают лишь в частных случаях и не покрывают все варианты расстановки двух прямоугольников на плоскости.
Функция работает только для прямоугольников, чьи стороны параллельны осям координат. В общем-то задача сведена к проецированию сторон на оси координат и попарной проверке пересечений двух отрезков. Если две пары отрезков пересекаются между собой то значит один из прямоугольников лежит на другом. Однако здесь есть подвох: нужно проверять также случай, когда одна сторона прямоугольника №1 лежит внутри той же стороны прямоугольника №2, а другая, сторона у №2 сама лежит внутри такой же в №1. Этот случай представлен на рисунке выше, под номером 1.
Пусть есть два прямоугольника A и B.
(a.x,a.y)--------------| | | | | | | |---------------(a.x1,a.y1) (b.x,b.y)---------------------| | | | | | | |---------------------(b.x1,b.y1)
тогда проверку на пересечение двух этих прямоугольников произведет следующая функция
var intersect = function(a,b)< return( ( ( ( a.x>=b.x && a.x=b.x && a.x1=b.y && a.y=b.y && a.y1=a.x && b.x=a.x && b.x1=a.y && b.y=a.y && b.y1=b.x && a.x=b.x && a.x1=a.y && b.y=a.y && b.y1=a.x && b.x=a.x && b.x1=b.y && a.y=b.y && a.y1
а Вы думали все просто. Я тоже так думал, пока не поймал ряд вариантов, которые не подходят под решения названные на форумах. Первая половина этой «многоэтажки» проверяет все случаи, кроме первого, вторая создана специально для случая №1.
UPD
Благодаря пользователю с ником Ruslan и его комментарию узнаем, что есть еще один достаточно просто способ проверить. Нужно действовать от обратного, проверять не 1,3,4 а только 2
var intersects = function ( a, b ) < return ( a.y < b.y1 || a.y1 >b.y || a.x1 < b.x || a.x >b.x1 ); >
Просто, как дважды два. Проверяем если верхняя грань первого прямоугольника находится ниже второго, или нижняя выше верхней грани первого. Тоже самое и для оси X.
Оставлять комментарии могут только зарегистрированные пользователи