Алгоритм для обнаружения пересечения двух прямоугольников?

143

Я ищу алгоритм, чтобы определить, пересекаются ли два прямоугольника (один под произвольным углом, другой только с вертикальными / горизонтальными линиями).

Тестирование, если угол одного находится в другом, ПОЧТИ работает. Сбой, если прямоугольники образуют крестообразную форму.

Кажется хорошей идеей избегать использования наклонов линий, что потребовало бы особых случаев для вертикальных линий.

user20493
источник
Что если вы добавите к своей угловой проверке проверку, чтобы увидеть, находится ли второй прямоугольник внутри границ (прямоугольника) углового прямоугольника?
Wes P
На каком языке ты собираешься это делать? Потому что в Java есть встроенные классы, которые позволяют вам это делать.
Мартейн
Я думаю, что графический API и большинство библиотек GUI (например, Swing) это реализовано.
l_39217_l
которые могут пропустить случаи, когда они перекрываются, но ни один угол не находится внутри прямоугольника
Florian Bösch
1
Этот вопрос почти такой же, как: stackoverflow.com/questions/306316/… . Хотя, это ищет решение, особенно для C ++. Принятый ответ также довольно прост и понятен.
Серебро Гонсалес

Ответы:

162

Стандартный метод состоит в том, чтобы выполнить тест по разделительной оси (выполните поиск в Google).

Коротко:

  • Два объекта не пересекаются, если вы можете найти линию, которая разделяет два объекта. например, объекты / все точки объекта находятся на разных сторонах линии.

Самое интересное, что достаточно просто проверить все края двух прямоугольников. Если прямоугольники не перекрываются, то одна из кромок будет разделительной осью.

В 2D вы можете сделать это без использования уклонов. Ребро просто определяется как разница между двумя вершинами, например

  edge = v(n) - v(n-1)

Вы можете получить перпендикуляр к этому, повернув его на 90 °. В 2D это просто как:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

Таким образом, нет тригонометрии или склонов. Нормализация вектора на единицу длины также не требуется.

Если вы хотите проверить, находится ли точка на той или иной стороне линии, вы можете просто использовать точечный продукт. знак скажет вам, на какой стороне вы находитесь:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

Теперь проверьте все точки прямоугольника A на краях прямоугольника B и наоборот. Если вы найдете разделяющую кромку, объекты не пересекаются (при условии, что все остальные точки в B находятся на другой стороне проверяемой кромки - см. Рисунок ниже). Если вы не найдете разделительной кромки, либо прямоугольники пересекаются, либо один прямоугольник содержится в другом.

Тест работает с любыми выпуклыми многоугольниками, кстати ..

Поправка: для идентификации разделяющего ребра недостаточно проверить все точки одного прямоугольника на каждом ребре другого. Кром-кандидат E (ниже) будет обозначен как разделительный край, так как все точки в A находятся в одной и той же полуплоскости E. Однако это не разделительный край, потому что вершины Vb1 и Vb2 из B также в этой полуплоскости. Это было бы только разделяющим краем, если бы это было не так http://www.iassess.com/collision.png

Нильс Пипенбринк
источник
2
Этот алгоритм не работает для всех случаев. Можно поместить второй прямоугольник, повернутый на 45 градусов к первому прямоугольнику и смещенный по диагонали, чтобы он удовлетворял вышеуказанным критериям пересечения, но не пересекался.
Skizz
6
Skizz, проверь все восемь граней. Если объекты не пересекаются , один из восьми ребер будет разделять их. Почему бы вам не опубликовать изображение, показывающее ваш случай? Я могу показать вам ось ..
Нильс Пипенбринк
2
Моя ошибка, она справляется с этим условием.
Skizz
2
Изображение уже умерло (ноябрь 2012)
Джон Дворжак
2
У меня было много проблем с визуализацией этого, поэтому я воссоздал то, на что, как мне кажется, выглядело изображение, на которое ссылаются. imgur.com/bNwrzsv
Ридле
16

В основном посмотрите на следующую картину:


Если два блока сталкиваются, линии A и B будут перекрываться.

Обратите внимание, что это должно быть сделано как по оси X, так и по оси Y, и оба должны перекрываться для столкновения прямоугольников.

На gamasutra.com есть хорошая статья, которая отвечает на вопрос (картинка из статьи). Я сделал подобный алгоритм 5 лет назад, и я должен найти свой фрагмент кода, чтобы опубликовать его здесь позже

Поправка : Теорема о разделяющей оси утверждает, что две выпуклые формы не перекрываются, если существует разделяющая ось (то есть та, где проекции, как показано , не перекрываются). Так что «Разделительная ось существует» => «Нет перекрытия». Это не двусмысленность, поэтому вы не можете сделать вывод об обратном.

m_pGladiator
источник
1
Очевидно, что два квадрата (0,0,1,1) и (0,3,1,4) не перекрываются, но их проекции на ось x полностью перекрываются. Оба теста необходимы, комбинация достаточна.
MSalters
18
Недостаточно, чтобы проекции x и y перекрывались: возьмем, например, прямоугольники [(0,0), (0,3), (3,3), (3,0)] и [(2,5), (5,2), (7,4), (4,7)].
Джоэл в Gö
4
Я согласен с @Joel в Gö. Этот метод пропускает большой набор случаев, когда прямоугольники не перекрываются, но их проекционные радиусы имеют значения как x, так и y.
Скотти Т
5
Этот ответ не является неправильным, но он вводит в заблуждение. Это правда, что: если два блока сталкиваются, линии A и B будут перекрываться. но верно также и то, что: если линии A и B перекрываются, две коробки могут или не могут сталкиваться
матовый горит
7
@floater: Я бы сказал, что это не только неправильно, но и вводит в заблуждение, что еще хуже.
BlueRaja - Дэнни Пфлюгофт
4

Ответ m_pGladiator правильный, и я предпочитаю его. Тест с разделительной осью - это самый простой и стандартный метод определения перекрытия прямоугольников. Линия, для которой проекционные интервалы не перекрываются, мы называем разделяющей осью . Решение Нильса Пипенбринка слишком общее. Он использует точечное произведение, чтобы проверить, находится ли одна фигура полностью на одной стороне края другой. Такое решение фактически могло бы привести к n-ребрам выпуклых многоугольников. Тем не менее, он не выбран для двух прямоугольников.

критическая точка ответа m_pGladiator заключается в том, что мы должны проверить проекцию двух прямоугольников на обе оси (x и y). Если две проекции перекрываются, то мы можем сказать, что эти два прямоугольника перекрываются. Так что комментарии выше к ответу m_pGladiator неверны.

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

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

мы называем прямоугольник A, B с помощью rectA, rectB.

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

если любой из двух прямоугольников повернут, может потребоваться некоторое усилие, чтобы определить их проекцию на оси x и y. Определите struct RotatedRect следующим образом:

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

разница в том, что теперь ширина 'немного отличается: widthA' для rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB 'для rectB:Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

Может ссылаться на GDC (Конференция по разработке игр 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Тристан
источник
Зачем вам нужен Math.abs () в «Math.abs (rectA.width + rectB.width)», для обработки отрицательной ширины?
AlexWien
Разделительная ось не обязательно является направлением компаса, она может иметь любой угол.
Бен Фойгт
Не повернутые прямоугольники rectA (x = 0, y = 0, width = 1, height = 1) и rectB (x = 2, y = 0, width = 100, height = 1) не пересекаются, но ваш метод говорит, что они пересекаются. Я делаю что-то неправильно?
Кагами Саша Розайлайт
4

В Какао вы могли легко определить, пересекает ли выбранный прямоугольник прямоугольник повернутого кадра NSView. Вам даже не нужно вычислять полигоны, нормали такие. Просто добавьте эти методы в ваш подкласс NSView. Например, пользователь выбирает область в суперпредставлении NSView, затем вы вызываете метод DoesThisRectSelectMe, передавая прямоугольник selectedArea. API convertRect: сделает эту работу. Тот же трюк работает, когда вы нажимаете на NSView, чтобы выбрать его. В этом случае просто переопределите метод hitTest, как показано ниже. API convertPoint: сделает эту работу ;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
Leonardo
источник
2
Этот код работает только для прямоугольников, которые расположены прямо на экране. Это тривиальный случай. Предполагается, что мы имеем дело с прямоугольниками, которые не расположены под углом 90 градусов к экрану или друг к другу.
Дункан C
Как я уже проверял и использовал в своих приложениях, этот код работает с любым повернутым прямоугольником. Независимо от степени вращения.
Леонардо
Это не описывает алгоритм, но упоминает библиотеку, которая уже использует его.
Бен Фойгт
2

Проверьте, не пересекаются ли какие-либо линии из одного прямоугольника с какой-либо из линий другого. Наивное пересечение отрезка линии легко закодировать.

Если вам нужна большая скорость, существуют усовершенствованные алгоритмы пересечения отрезков (sweep-line). Смотрите http://en.wikipedia.org/wiki/Line_segment_intersection

Луи Бренди
источник
4
Осторожный! Не забывайте случай, когда один прямоугольник полностью закрывает другой
Pitarou
2

Одним из решений является использование того, что называется полигоном No Fit. Этот многоугольник рассчитывается из двух многоугольников (концептуально путем скольжения одного вокруг другого) и определяет область, для которой многоугольники перекрываются, учитывая их относительное смещение. Получив этот NFP, вы просто должны выполнить тест на включение с точкой, заданной относительным смещением двух полигонов. Этот тест на включение является быстрым и легким, но вы должны сначала создать NFP.

Поищите в сети «Не подходит многоугольник» и посмотрите, сможете ли вы найти алгоритм для выпуклых многоугольников (он становится намного сложнее, если у вас есть вогнутые многоугольники). Если вы не можете ничего найти, напишите мне на Говард точка J точка может Gmail точка ком

Говард Мэй
источник
1

Вот что я думаю позаботится обо всех возможных случаях. Сделайте следующие тесты.

  1. Проверьте, чтобы любая из вершин прямоугольника 1 находилась внутри прямоугольника 2, и наоборот. Каждый раз, когда вы находите вершину, которая находится внутри другого прямоугольника, вы можете сделать вывод, что они пересекаются, и остановить поиск. Это позаботится о том, чтобы один прямоугольник полностью находился внутри другого.
  2. Если приведенный выше тест не дает результатов, найдите точки пересечения каждой линии одного прямоугольника с каждой линией другого прямоугольника. Как только точка пересечения найдена, проверьте, находится ли она внутри воображаемого прямоугольника, созданного соответствующими 4 точками. Когда такая точка найдена, сделайте вывод, что они пересекаются, и остановите поиск.

Если вышеупомянутые 2 теста возвращают false, то эти 2 прямоугольника не перекрываются.

Джон Смит
источник
0

Если вы используете Java, все реализации интерфейса Shape имеют метод пересечений, который принимает прямоугольник.

Брендан Кэшман
источник
К сожалению, я использую C #. Класс Rectangle имеет метод Contains (), но он предназначен только для не повернутых прямоугольников.
user20493
Метод intersects () довольно бесполезен, так как, я думаю, он возвращает логическое значение вместо пересечения.
ZZ 5
0

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

Математический ответ - сформировать уравнения, описывающие каждое ребро обоих прямоугольников. Теперь вы можете просто найти, пересекаются ли какие-либо из четырех линий из прямоугольника A с любой из линий прямоугольника B, который должен быть простым (быстрым) решателем линейных уравнений.

-Адам

Адам Дэвис
источник
2
Проблема с уравнениями, когда у вас есть вертикальная линия, которая имеет бесконечный наклон.
user20493
Есть угловые случаи для каждого решения.
Адам Дэвис
2
и один квадрат полностью окружает другой.
Оливер Хэллам
0

Вы можете найти пересечение каждой стороны углового прямоугольника с каждой стороной выровненного по оси. Сделайте это, найдя уравнение бесконечной линии, на которой лежит каждая сторона (т.е. v1 + t (v2-v1) и v'1 + t '(v'2-v'1) в основном), найдя точку, в которой линии встречаются путем решения для t, когда эти два уравнения равны (если они параллельны, вы можете проверить это), а затем проверяете, лежит ли эта точка на отрезке между двумя вершинами, т.е. верно ли, что 0 <= t <= 1 и 0 <= t '<= 1.

Однако это не относится к случаю, когда один прямоугольник полностью покрывает другой. Это можно проверить, проверив, все ли четыре точки одного прямоугольника лежат внутри другого прямоугольника.

HenryR
источник
0

Вот что я бы сделал для 3D- версии этой проблемы:

Смоделируйте 2 прямоугольника как плоскости, описываемые уравнениями P1 и P2, затем напишите P1 = P2 и выведите из этого линию уравнения пересечения, которая не будет существовать, если плоскости параллельны (нет пересечений) или находятся в одной плоскости, в этом случае вы получите 0 = 0. В этом случае вам нужно будет использовать алгоритм пересечения 2D-прямоугольника.

Тогда я бы посмотрел, проходит ли эта линия, которая находится в плоскости обоих прямоугольников, через оба прямоугольника. Если это так, то у вас есть пересечение 2-х прямоугольников, иначе вы этого не сделаете (или не должны, я мог пропустить угловой случай в моей голове).

Чтобы определить, проходит ли линия через прямоугольник в той же плоскости, я бы нашел 2 точки пересечения линии и стороны прямоугольника (моделируя их с помощью линейных уравнений), а затем убедившись, что точки пересечения находятся в ассортимент.

Это математические описания, к сожалению, у меня нет кода, чтобы сделать выше.

свободное место
источник
Вы пропустили ту часть, где, если вы найдете плоскую линию пересечения, вы должны убедиться, что ее часть существует в обоих прямоугольниках.
Ли Лувьер
0

Другой способ сделать тест, который немного быстрее, чем тест с разделительной осью, состоит в использовании алгоритма чисел намотки (только на квадрантах, а не суммировании углов, которое ужасно медленно) в каждой вершине любого прямоугольника (произвольно выбранного). Если какая-либо из вершин имеет ненулевое число обмоток, два прямоугольника перекрываются.

Этот алгоритм несколько длиннее, чем тест с разделительной осью, но он быстрее, потому что он требует только теста полуплоскости, если ребра пересекают два квадранта (в отличие от до 32 тестов с использованием метода разделительной оси)

Алгоритм имеет дополнительное преимущество в том, что его можно использовать для проверки перекрытия любого многоугольника (выпуклого или вогнутого). Насколько я знаю, алгоритм работает только в 2D пространстве.

Мадс
источник
3
Я могу ошибаться, но разве это не просто проверить, находятся ли вершины одного прямоугольника внутри другого? Если да, этого недостаточно, потому что прямоугольники могут перекрываться без каких-либо вершин внутри.
Синелав
Могут ли они с прямоугольниками? Как? Мне кажется, что для пересечения двух прямоугольников хотя бы одна вершина одного из прямоугольников должна лежать на другом прямоугольнике.
Дункан C
@DuncanC: Да, они могут. Контрпример - это крест, и он даже был указан в исходном вопросе.
Бен Фойгт
@BenVoigt Это очень старая тема, но вы абсолютно правы.
Дункан C
0

Либо я что-то упускаю, зачем делать это так сложно?

если (x1, y1) и (X1, Y1) являются углами прямоугольников, то для поиска пересечения выполните:

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}
user1517108
источник
3
Вам не хватает того, что он хочет, чтобы один был повернут на произвольный угол.
Robotbugs
0

Я реализовал это так:

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

Матрица mB - это любая матрица аффинного преобразования, которая преобразует точки в пространстве B в точки в пространстве A. Это включает в себя простое вращение и перемещение, вращение с масштабированием и полные аффинные деформации, но не перспективные деформации.

Это может быть не так оптимально, как это возможно. Скорость не была большой проблемой. Однако, похоже, у меня все в порядке.

Robotbugs
источник
0

Вот математическая реализация принятого ответа:

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);
Джед
источник
0

Это обычный метод, переходите строка за строкой и проверяйте, пересекаются ли линии. Это код в MATLAB.

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf('Given rectangles intersect at %d points:\n',size(P,2))
    plot(P(1,:),P(2,:),'*k')
end

Функцию InterX можно загрузить по адресу : https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Шива Сринивас Колукула
источник
0

У меня есть более простой метод, если у нас есть 2 прямоугольника:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Они перекрываются, если и только если:

Перекрытие = (max_x1> min_x2) и (max_x2> min_x1) и (max_y1> min_y2) и (max_y2> min_y1)

Вы можете сделать это и для 3D-блоков, на самом деле это работает для любого количества измерений.

BitFarmer
источник
0

В других ответах было сказано достаточно, поэтому я просто добавлю псевдокод в одну строку:

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
Przemek
источник