Часто при разработке различных интерфейсов возникает задача проверки пересекаются ли два заданных прямоугольника. Решение в данном случае очень простое, однако мной нигде не найденное и поэтому в очередной раз пришлось писать свой велосипед. При этом грабли на которые наступают разработчики одни и те же, а решение выдаваемые гуру на форумах работают лишь в частных случаях и не покрывают все варианты расстановки двух прямоугольников на плоскости.
Функция работает только для прямоугольников, чьи стороны параллельны осям координат. В общем-то задача сведена к проецированию сторон на оси координат и попарной проверке пересечений двух отрезков. Если две пары отрезков пересекаются между собой то значит один из прямоугольников лежит на другом. Однако здесь есть подвох: нужно проверять также случай, когда одна сторона прямоугольника №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.
Комментарии
( b.x>=a.x && b.x=a.x && b.x1=a.y && b.y=a.y && b.y1
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;
}
П.С. упрощенный вариант у меня почему-то не заработал:(
http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other
http://silentmatt.com/rectangle-intersection/
var intersects = function ( a, b ) {
return !( a.y > b.y1 || a.y1 b.x1 );
}
Вот как хотел написать:
var intersects = function ( a, b ) {
return !( a.y > b.y1 || a.y1 < b.y || a.x1 < b.x || a.x > b.x1 );
}
С одинаковыми прямоугольниками довольно просто, там можно проверять пересечение граней или их совпадение, а вот с прямоугольниками произвольных размеров ума не приложу что делать
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);
}
Т.е. в коде надо будет прогнать циклом все стороны одного прямоугольника со сторонами другого.
Я решил задачу немного по другому. Сначала описываю вокруг заданных многоугольников прямоугольники, параллельные осям, потом проверяю попадания вершин многоугольника 1 в описаный вокруг многоугольника 2 прямоугольник простым способом, описанным здесь. Далее, для полученных точек методом трассировки луча узнаю принадлежит ли вершина многоугольника 1 многоугольнику 2. Можно и без описаных прямоугольников обойтись, но тогда все вершины по более сложному алгоритму нужно считать.
Реализацию на javascript описал здесь http://geekpage.ru/posts/29 (сюда код не вставляю так как довольно много получилось).
Метод конечно требует доработок и добавления всевозможных проверок входных данных, но он работает.
вот простейшее решение, никаких операторов "или" не нужно
всеволиш нунжно проверить пересечение по x и по y
function rectIntersect(a, b){
// interval intersection
function ii(a1, a2, b1, b2){ return a1
function ii(a1, a2, b1, b2){ return a1
// 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);
}
function rectIntersect(a, b){
// interval intersection
function ii(a1, a2, b1, b2){ return a1
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);
}