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

Ответ 1

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

Короче:

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

http://www.gamasutra.com/features/20000330/bobic_08.gif

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

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

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

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

Ответ 3

В Cocoa вы можете легко определить, пересекает ли выбранный прямоугольник прямой вращающийся NSView frame rect. Вам даже не нужно вычислять полигоны, нормали такие. Просто добавьте эти методы в подкласс NSView. Например, пользователь выбирает область в супервизоре NSView, затем вы вызываете метод DoThisRectSelectMe, который передает выбранный прямоугольник. 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;
}

Ответ 4

m_pGladiator правильный, и я предпочитаю его. Тест разделительной оси - самый простой и стандартный метод обнаружения перекрытия прямоугольника. Линия, для которой интервалы проекции не пересекаются, мы называем разделительной осью. Решение Nils Pipenbrinck слишком общее. Он использует dot product, чтобы проверить, полностью ли одна форма находится на одной стороне края другой. Это решение на самом деле могло бы привести к выпуклым многоугольям n-edge. Однако он не выбирается для двух прямоугольников.

критическая точка ответа 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 'для прямоугольника: 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 (Conference Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Ответ 5

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

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

Ответ 6

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

У вас есть поиск No Fit Polygon в Интернете и посмотрите, можно ли найти алгоритм для выпуклых многоугольников (он становится намного сложнее, если у вас есть вогнутые полигоны). Если вы не можете найти что-либо, напишите мне по адресу howard dot J dot gmail dot com

Ответ 7

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

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

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

Ответ 8

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

Ответ 9

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

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

-Adam

Ответ 10

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

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

Ответ 11

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

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

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

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

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

Ответ 12

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

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

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

Ответ 13

Либо мне не хватает чего-то другого, почему так сложно?

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

    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");}

Ответ 14

Я реализовал его следующим образом:

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. Это включает в себя простое вращение и перевод, вращение плюс масштабирование и полные аффинные перекосы, но не перспективные перекосы.

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

Ответ 15

Вот воплощение принятого ответа в Matlab:

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);

Ответ 16

Это обычный метод, зайдите последовательно и проверьте, пересекаются ли линии. Это код в 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

Ответ 17

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

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

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

Overlap = (max_x1 > min_x2) и (max_x2 > min_x1) и (max_y1 > min_y2) и (max_y2 > min_y1)

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

Ответ 18

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

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);