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

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

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

Рассказать друзьям

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


Защитный код
Обновить

Комментарии   

0
Вася
# Вася 13.11.2012 20:08
Спасибо, отличная функция
0
Олег_123
# Олег_123 22.02.2013 03:48
Функция хороша, жаль только что справедлива лишь для параллельных осям прямоугольникам.
0
Alex
# Alex 21.03.2013 00:59

var intersect = function(a, b) {
var s1 = ( a.x>=b.x && a.x<=b.x1 )||( a.x1>=b.x && a.x1<=b.x1 ),
s2 = ( a.y>=b.y && a.y<=b.y1 )||( a.y1>=b.y && a.y1<=b.y1 ),
s3 = ( b.x>=a.x && b.x<=a.x1 )||( b.x1>=a.x && b.x1<=a.x1 ),
s4 = ( b.y>=a.y && b.y<=a.y1 )||( b.y1>=a.y && b.y1<=a.y1 );

return ((s1 && s2) || (s3 && s4)) || ((s1 && s4) || (s3 && s2));
};
0
Megan
# Megan 24.03.2013 06:41
Отличный пример!!! Спасибо!!!
0
Megan
# Megan 24.03.2013 07:06
А зачем проводить эту проверку?





( b.x>=a.x && b.x=a.x && b.x1=a.y && b.y=a.y && b.y1
0
Leroy
# Leroy 24.03.2013 16:10
откуда вы ее взяли?
0
Ruslan
# Ruslan 26.06.2013 19:48
Так проще:

boolean intersects(Box box1, Box box2) {

//Y not intersects

if (box1.getY() < box2.getY1() || box1.getY1() > box2.getY()) {

return false;

}

//X not intersects

if (box1.getX1() < box2.getX() || box1.getX() > box2.getX1()) {

return false;

}

return true;

}
-1
Leroy
# Leroy 27.06.2013 02:47
все гениальное просто) нужно было проверять не 1,3,4 а только 2. Спасибо, очень лаконично
0
Frukts
# Frukts 01.07.2013 18:11
Лучи добра Вам за эту статью.

П.С. упрощенный вариант у меня почему-то не заработал:(
+1
isxaker
# isxaker 18.02.2014 18:03
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 && RectA.Y1 < RectB.Y2 && RectA.Y2 > RectB.Y1)



http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other



http://silentmatt.com/rectangle-intersection/
0
Zuenf
# Zuenf 27.01.2014 08:47
Поменять знаки некоторые правильно было бы:

var intersects = function ( a, b ) {

return !( a.y > b.y1 || a.y1 b.x1 );

}
0
Zuenf
# Zuenf 27.01.2014 08:49
Сорри, странный парсер тегов в комментах.

Вот как хотел написать:

var intersects = function ( a, b ) {

return !( a.y > b.y1 || a.y1 < b.y || a.x1 < b.x || a.x > b.x1 );

}
0
Gudwin
# Gudwin 07.05.2014 21:43
Было бы неплохо всё же вариант для прямоугольников, стороны которых не параллельны осям, увидеть.

С одинаковыми прямоугольниками довольно просто, там можно проверять пересечение граней или их совпадение, а вот с прямоугольниками произвольных размеров ума не приложу что делать
0
Leroy
# Leroy 08.05.2014 13:36
теоретически можно свести задачу к проверке пересечения отрезков. Т.е. попарно проверить все 16 вариантов пересечений. Если хотя бы один есть то прямоугольники пересекаются. Вот нашел функцию проверки отрезков
function Intersection(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2){
var v1,v2,v3,v4;
v1=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);
v2=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);
v3=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);
v4=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);
return (v1*v2<0) && (v3*v4<0);
}


Т.е. в коде надо будет прогнать циклом все стороны одного прямоугольника со сторонами другого.
0
Gudwin
# Gudwin 15.05.2014 16:32
Несправедливо для случая один полностью внутри другого.

Я решил задачу немного по другому. Сначала описываю вокруг заданных многоугольников прямоугольники, параллельные осям, потом проверяю попадания вершин многоугольника 1 в описаный вокруг многоугольника 2 прямоугольник простым способом, описанным здесь. Далее, для полученных точек методом трассировки луча узнаю принадлежит ли вершина многоугольника 1 многоугольнику 2. Можно и без описаных прямоугольников обойтись, но тогда все вершины по более сложному алгоритму нужно считать.

Реализацию на javascript описал здесь http://geekpage.ru/posts/29 (сюда код не вставляю так как довольно много получилось).

Метод конечно требует доработок и добавления всевозможных проверок входных данных, но он работает.
0
Leroy
# Leroy 15.05.2014 20:26
Может быть github?!
0
Gudwin
# Gudwin 15.05.2014 23:21
На bitbucket сейчас лежит, но оно ещё не в том виде чтобы публиковать (проверок нет, в том посте описал только сам принцип, стыдно мне такое на github класть), неделю или две и приведу в порядок и открою доступ, либо перенесу на github
0
Gudwin
# Gudwin 15.05.2014 23:22
Раньше не получится (сессия)
0
arch
# arch 15.12.2015 16:33
а если не известен элемент(ы), которые перекрывают?
0
Данила Летуновский
# Данила Летуновский 06.08.2016 16:31
Печально что первой ссылкой в интернете выподает сайт "веб программиста" а не нормального программиста.

вот простейшее решение, никаких операторов "или" не нужно
всеволиш нунжно проверить пересечение по x и по y

function rectIntersect(a, b){
// interval intersection
function ii(a1, a2, b1, b2){ return a1
0
Данила Летуновский
# Данила Летуновский 06.08.2016 16:31
function rectIntersect(a, b){
function ii(a1, a2, b1, b2){ return a1
0
Данила Летуновский
# Данила Летуновский 06.08.2016 16:32
function rectIntersect(a, b){
// interval intersection
function ii(a1, a2, b1, b2){ return a1 <= b2 && b1 <= a2; }

return ii(a.x, a.x + a.w, b.x, b.x + b.w) && ii(a.y - a.h, a.y, b.y - b.h, b.y);
}
0
Данила Летуновский
# Данила Летуновский 06.08.2016 17:45
и для оконных координат

function rectIntersect(a, b){
// interval intersection
function ii(a1, a2, b1, b2){ return a1
0
Данила Летуновский
# Данила Летуновский 06.08.2016 17:46
<= b2 && b1 <= a2; }

return ii(a.x, a.x + a.w, b.x, b.x + b.w) && ii(a.y, a.y + a.h, b.y, b.y + b.h);
}