Как найти пересечение прямоугольников по координатам
Перейти к содержимому

Как найти пересечение прямоугольников по координатам

  • автор:

Как найти площадь пересечения двух прямоугольников?

Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно: (x1,y1) — левая нижняя точка первого прямоугольника (x2,y2) — правая верхняя точка первого прямоугольника (x3,y3) — левая нижняя точка второго прямоугольника (x4,y4) — правая верхняя точка второго прямоугольника И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.

Отслеживать
13.8k 12 12 золотых знаков 44 44 серебряных знака 77 77 бронзовых знаков
задан 14 дек 2017 в 21:45
user235806 user235806

@Igor просто у меня есть много прямоугольников которие нужно перебирать одни с другими. И не могу понять как найти площадь пересечения каждого с каждим. Как их перебратить и пересекаются ли они я знаю. А вот етого понять не могу. Так как ети прямоугольники могут пересекатся с разних сторон. Если знаете, то помогите пожалуйста

– user235806
14 дек 2017 в 21:52
Можно для обоих найти общий прямоугольник, а затем умножить его ширину на высоту.
14 дек 2017 в 21:56
@VladimirGamalyan да ну как найти нужное нам пересечение.
– user235806
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 растет сверху вниз, то необходимо внести соответствующие поправки).

Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):

Как найти пересечение прямоугольников по координатам

rui_er → Codeforces Round 942 (Div. 1, Div. 2)

Haidora → A general approach to solve subree distinct values queries!

SashaT9 → Codeforces Round 943 (Div. 3)

EnDeRBeaT → [Tool] Graph Debugger

rui_er → Codeforces Round 942 (Div. 1, Div. 2) Editorial

awoo → Разбор Educational Codeforces Round 165

Abito → Who’s going to IIOT 2024?

Некропост

dv.jakhar_ → How to solve this problem, any ideas?

gareeeeeeeeeeeeeeeev → Релиз версии бот 1.2

Zanite → [Photos Dump] Jollybee CP Team, the Luxor WF, and the Indomie Aftermath

wuhudsm → TheForces Round #30 (Good-Forces) Editorial

Некропост

Igor_Kudryashov → Разбор задач Coder-Strike 2014 Финал

h ehezhou → 2024-The 6th Turing Cup Tournament

Некропост

MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces

transfermarket → Report cheater obfuscate code

Asuna_Yuuki → MEME

Loserinlife → Need help

Некропост

Sharon → Who is going to UCF Saturday Practice — November 2nd, 2019 ?

Cipesta. → Beyond CP: What’s Next

tickbird → Been stuck at green almost a year

123gjweq2 → Can someone please help me?

Некропост

Monogon → Codeforces Round #639 Editorial

Некропост

Vladosiya → Codeforces Round 863 (Div. 3) Разбор

MofK → Codeforces Global Round 25 Editorial

Kolyanchick → До скорых встреч

Координаты пересечения двух прямоугольников

Author24 — интернет-сервис помощи студентам

здравствуйте. сегодня наткнулся на такую задачу: определить координаты левого верхнего и правого нижнего углов общей части 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()  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; }

как проверить пересекаются ли два прямоугольника

Часто при разработке различных интерфейсов возникает задача проверки пересекаются ли два заданных прямоугольника. Решение в данном случае очень простое, однако мной нигде не найденное и поэтому в очередной раз пришлось писать свой велосипед. При этом грабли на которые наступают разработчики одни и те же, а решение выдаваемые гуру на форумах работают лишь в частных случаях и не покрывают все варианты расстановки двух прямоугольников на плоскости.

варианты пересечений двух прямоугольников

Функция работает только для прямоугольников, чьи стороны параллельны осям координат. В общем-то задача сведена к проецированию сторон на оси координат и попарной проверке пересечений двух отрезков. Если две пары отрезков пересекаются между собой то значит один из прямоугольников лежит на другом. Однако здесь есть подвох: нужно проверять также случай, когда одна сторона прямоугольника №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.

Оставлять комментарии могут только зарегистрированные пользователи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *