Часто при разработке различных интерфейсов возникает задача проверки пересекаются ли два заданных прямоугольника. Решение в данном случае очень простое, однако мной нигде не найденное и поэтому в очередной раз пришлось писать свой велосипед. При этом грабли на которые наступают разработчики одни и те же, а решение выдаваемые гуру на форумах работают лишь в частных случаях и не покрывают все варианты расстановки двух прямоугольников на плоскости.
Функция работает только для прямоугольников, чьи стороны параллельны осям координат. В общем-то задача сведена к проецированию сторон на оси координат и попарной проверке пересечений двух отрезков. Если две пары отрезков пересекаются между собой то значит один из прямоугольников лежит на другом. Однако здесь есть подвох: нужно проверять также случай, когда одна сторона прямоугольника №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.x1 )||( a.x1>=b.x && a.x1<=b.x1 )
) && (
( a.y>=b.y && a.y<=b.y1 )||( a.y1>=b.y && a.y1<=b.y1 )
)
)||(
(
( b.x>=a.x && b.x<=a.x1 )||( b.x1>=a.x && b.x1<=a.x1 )
) && (
( b.y>=a.y && b.y<=a.y1 )||( b.y1>=a.y && b.y1<=a.y1 )
)
)
)||(
(
(
( a.x>=b.x && a.x<=b.x1 )||( a.x1>=b.x && a.x1<=b.x1 )
) && (
( b.y>=a.y && b.y<=a.y1 )||( b.y1>=a.y && b.y1<=a.y1 )
)
)||(
(
( b.x>=a.x && b.x<=a.x1 )||( b.x1>=a.x && b.x1<=a.x1 )
) && (
( a.y>=b.y && a.y<=b.y1 )||( a.y1>=b.y && a.y1<=b.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.
$begingroup$
Given the coordinates of two rectangles on a coordinate plane, what would be the easiest way to find the coordinates of the intersecting rectangle of the two?
I am trying to do this programatically.
asked Oct 20, 2010 at 21:23
serhatozgelserhatozgel
1711 gold badge1 silver badge4 bronze badges
$endgroup$
3
$begingroup$
Working from Zwarmapapa’s solution, you probably want to check that the rectangles actually overlap, and optionally that the overlap has a non-zero area.
When there is no overlap, the two coordinates will be reversed (top left will actually be bottom right and vice-versa).
If you want the rectangles with zero area (edge/corner intersection), change the two less than checks to less than or equal.
Rectangle r1 = rect1;
Rectangle r2 = rect2;
Rectangle intersectionRect = null;
int leftX = Math.max( r1.getX(), r2.getX() );
int rightX = Math.min( r1.getX() + r1.getWidth(), r2.getX() + r2.getWidth() );
int topY = Math.max( r1.getY(), r2.getY() );
int bottomY = Math.min( r1.getY() + r1.getHeight(), r2.getY() + r2.getHeight() );
if ( leftX < rightX && topY < bottomY ) {
intersectionRect = new Rectangle( leftX, topY, rightX-leftX, bottomY-topY );
} else {
// Rectangles do not overlap, or overlap has an area of zero (edge/corner overlap)
}
answered Oct 17, 2017 at 20:01
WillWill
511 silver badge2 bronze badges
$endgroup$
$begingroup$
Just think logically, draw it in mspaint or something. I got the answer in less than 15 minutes.
Rectangle r1 = rect1; Rectangle r2 = rect2; int leftX = Math.max( r1.getX(), r2.getX() ); int rightX = Math.min( r1.getX()+r1.getWidth(), r2.getX()+r2.getWidth() ); int topY = Math.max( r1.getY(), r2.getY() ); int bottomY = Math.min( r1.getY()+r1.getHeight(), r2.getY()+r2.getHeight() ); Rectangle intersectionRect = new Rectangle( leftX, topY, rightX-leftX, bottomY-topY );
answered Jul 14, 2012 at 16:47
$endgroup$
$begingroup$
In order to simplify the problem, I will assume that the rectangles are orientated “straight up and down.” By this I mean that each of the rectangles has an edge which is parallel to the x (or y) axis. Judging by the context, this should be a fair assumption. Let me know if this is not the case (in other words, what class is this for?) It might help to first graph the two rectangles whose coordinates are given. In the “simplest” case they will intersect in exactly two places.
The coordinates for some intersection will just be the point where “edge a” of “rectangle 1” intersects “edge x” of “rectangle 2.” That is, the intersection point will have the x value of (edge a or x), and the y value of the other edge (since these rectangles are parallel to the axis the x or y value of an edge will be constant across that edge.) You know the values of these edges by the coordinates given for the corners of your original rectangles.
After drawing the rectangles this should be a fairly easy and straight-forward process to work through. If you are trying to write a computer program to do this for you it is slightly more complicated but follows the same logic. Hope this helps!
answered Oct 20, 2010 at 22:21
jericsonjericson
8718 silver badges16 bronze badges
$endgroup$
1
You must log in to answer this question.
Not the answer you’re looking for? Browse other questions tagged
.
Not the answer you’re looking for? Browse other questions tagged
.
Как найти площадь пересечения двух прямоугольников?
Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно:
(x1,y1) — левая нижняя точка первого прямоугольника
(x2,y2) — правая верхняя точка первого прямоугольника
(x3,y3) — левая нижняя точка второго прямоугольника
(x4,y4) — правая верхняя точка второго прямоугольника
И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.
Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
Всё ещё ищете ответ? Посмотрите другие вопросы с метками c++ математика геометрия прямоугольники или задайте свой вопрос.
Site design / logo © 2022 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2022.6.10.42345
Нажимая «Принять все файлы cookie», вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
геометрия — Пересечение прямоугольников
Как вывести общую формулу для построения пересечения прямоугольников? Ведь бывает, что один прямоугольник находится внутри другого или координаты первого прямоугольника по х больше, чем у второго и при этом меньше по у, чем у второго. Как свести разные случаи в один?
задан 30 Май ’17 20:59
1 ответ
Задача для прямоугольников сводится к аналогичной задаче для отрезков. По каждой оси смотрим на пересечения отрезков, а потом берём получившийся прямоугольник (как декартово произведение). Если хотя одно пересечение отрезков окажется пустым, то и пересечение прямоугольников пусто.
По определению, отрезок [a,b] есть множество решений двойного неравенства a<=x<=b. Для двух отрезков имеем систему неравенств a<=x, c<=x, x<=b, x<=d. Она равносильна системе max(a,c)<=x, x<=min(b,d). То есть надо взять максимум левых концов и минимум правых. Получится отрезок [max(a,c),min(b,d)]. Если первое число больше второго, то это пустое множество.
отвечен 30 Май ’17 21:15
@falcao: Я уж сороковой год использую неравенство $%max(a,c)le min(b,d)$% в для проверки пересечения отрезков. Проверять пересечение прямоугольников не приходилось. Это я о программировании.
@EdwardTurJ: я вспомнил по ходу дела, что вопрос о прямоугольниках уже звучал здесь. Там площадь надо было найти. Наверное, на практике такое редко требуется, а в тренировочных задачах частенько встречается.
Получить точки пересечения из 2 прямоугольников
Допустим, у нас есть два прямоугольника, определенные их нижним левым и верхним правым углами. Например: rect1 (x1, y1) (x2, y2) а также rect2 (x3, y3) (x4, y4).
Я пытаюсь найти координаты (внизу слева и вверху справа) пересеченного прямоугольника.
Любые идеи, алгоритм, псевдокод, будет принята с благодарностью.
постскриптум Я нашел похожие вопросы, но они проверяют, только если 2 прямоугольника пересекаются.
Решение
Если входные прямоугольники нормализованы, то есть вы уже знаете, что x1 < x2 , y1 < y2 (и то же самое для второго прямоугольника), тогда все, что вам нужно сделать, это рассчитать
и это даст вам ваше пересечение в виде прямоугольника (x5, y5)-(x6, y6) , Если исходные прямоугольники не пересекаются, результатом будет «вырожденный» прямоугольник (с x5 >= x6 и / или y5 >= y6 ), который вы можете легко проверить.
Постскриптум Как обычно, мелкие детали будут зависеть от того, нужно ли учитывать трогательный прямоугольники как пересекающиеся.
Другие решения
Чтобы найти пересечение, вам нужно сделать несколько простых сравнений точек:
Итак, как мы можем видеть из изображения, если x3, y3 больше или равно x1, y1 и меньше или равно x2, y2, то оно находится внутри первого прямоугольника, аналогично вам нужно будет проверить, попадает ли x4, y4 внутрь диапазон от х1, у1 до х2, у2, а также.
если оба условия оказываются верными, то вы можете быть уверены, что второй прямоугольник полностью охватывается первым. 
Вам нужно будет проверить и обратное, если узнаете, что внутри, что важно для вас.
Также необходимо, чтобы прямоугольники были выровнены по оси, иначе это не будет работать надежно.
Дайте мне знать, если вам нужно больше подробностей, хотя я думаю, что быстрый поиск в Google очень легко раскроет для вас более подробную информацию, но дайте мне знать, и я могу сделать учебник по столкновению с прямоугольником, если хотите.
Более подробно:
Чтобы выяснить, имеют ли прямоугольники пересечения, вы можете проверить координаты их определяющих точек, для наших целей мы будем использовать координаты верхнего левого и нижнего правого углов.
Мы можем использовать класс, чтобы сделать это проще для нас, и для максимального удобства использования кода мы можем использовать 2d Vector и 2d Point:
2dVectorPoint.h
Используемый код адаптирован из Вот чтобы сохранить мои пальцы.
Тогда мы можем использовать это, чтобы легко сравнить:
мы можем определить прямоугольник 1 как имеющий P1 и P2 как его границы и прямоугольник 2 как имеющий P3 и P4 как его границы, давая нам следующее сравнение:
Это вернет истинное значение для любого экземпляра пересечения или для прямоугольника 1, полностью охватывающего прямоугольник 2.
Чтобы проверить только пересечения, просто удалите проверку на равенство (возьмите все = из вышеприведенного уравнения), и вы будете проверять только на пересечения. Если у вас есть пересечение, вы можете использовать линейную алгебру для оценки точных координат.
Скажем, у блока есть радиус X и радиус Y (я знаю, что его нет, но этот термин здесь полезен).
Вы будете иметь:
Теперь, если прямоугольные средние точки находятся дальше, чем сумма их радиусов в соответствующем направлении — они не сталкиваются.
В противном случае они делают — этого намека должно хватить.
Теперь вы должны быть в состоянии выполнить задание.
ОБНОВИТЬ:
Хорошо — давайте решим это для 1D — позже вы решите это для 2D. Посмотрите на этот кусок … искусства
Вы видите 2 сегмента — теперь некоторые расчеты:
Теперь, как проверить, происходит ли столкновение? Как я уже сказал, если сумма «радиусов» меньше расстояния сегментов — столкновения нет:
Теперь ваша задача — вычислить пересечение / общую часть в 1D и 2D. Теперь все зависит от вас (вы можете прочитать ответ Андрея).
Здесь та же самая ситуация, но в 2D — две одномерные ситуации:
Вы можете иметь дело с x а также y Направление отдельно.
Предположим, что x1 <= x3 (первая коробка как минимум так же далеко, как и вторая). Тогда есть совпадение, если и только если x1 <= x3 <= x2 ,
Аналогично предположим y1 <= y3 (первая коробка, по крайней мере, так же далеко, как и вторая). Тогда есть совпадение, если и только если y1 <= y3 <= y2 ,
Если в обоих направлениях перекрытие, то перекрытие прямоугольника. Вы можете найти координаты, отсортировав x а также y координаты и выбрав два средних.
Как проверить, пересекаются ли два прямоугольника?
Александр
Гуру
(3871),
закрыт
11 лет назад
Стороны прямоугольников параллельны осям координат. Прямоугольник определяется двумя точками, левой верхней и правой нижней: (x1,y1) и (x2,y2). Ось Ox направлена направо, ось Oy направлена вниз (как на мониторе).
Jurii
Высший разум
(175090)
11 лет назад
Нарисуй на листочке бумаги:
– оси координат
– 2 прямоугольника, которые пересекаются (2-ой левее, правее, выше, ниже)
– прямоугольник, а в нём второй
– прямоугольники, которые не пересекаются
– обозначь на прямоугольниках точки (левую верхнюю и правую нижнюю)
И выведи нужные тебе условия!
+ случай когда координаты совпадают.
=Serge=
Просветленный
(35963)
11 лет назад
Элементарно. Вот фрагмент условий. Так как координаты уже упорядочены по возрастанию.
If b.x1 >a.x1 then
If b.x1>a.x2 then writeln(“Не входит”);
(иначе проверяем по y).
АлександрГуру (3871)
11 лет назад
У меня вышло вот так (при условии, что ширина и высота прямоугольника b не меньше чем i):
if ((i.x1>=b.x1) and (i.x1<=b.x2) and (i.y1>=b.y1) and (i.y1<=b.y2))
or ((i.x2>=b.x1) and (i.x2<=b.x2) and (i.y2>=b.y1) and (i.y2<=b.y2))
or ((i.x2>=b.x1) and (i.x2<=b.x2) and (i.y1>=b.y1) and (i.y1<=b.y2))
or ((i.x1>=b.x1) and (i.x1<=b.x2) and (i.y2>=b.y1) and (i.y2<=b.y2)) then
=Serge=
Просветленный
(35963)
Ты слишком усложняешь.Не вхождение проверяется проще,как я уже писал.И без всяких дополнительных условий.
Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
#include <algorithm>
/*
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)
{
int left = std::max(x1, x3);
int top = std::min(y2, y4);
int right = std::min(x2, x4);
int bottom = std::max(y1, y3);
int width = right - left;
int height = top - bottom;
if (width < 0 || height < 0)
return 0;
return width * height;
}
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
