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


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

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

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

18 132

18 ответов:

стандартный метод будет делать разделительный тест оси (сделайте поиск 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

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


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

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

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

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

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

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

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

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

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

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

назовем прямоугольник A, B с Квадра, 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

может относиться к Кри(конференция разработчиков компьютерных игр 2007) файл ppt www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

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

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

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

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

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

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

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

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

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

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

Адам

вы можете найти пересечение каждой стороны углового прямоугольника с каждой стороной выровненной по оси. Сделать это путем нахождения уравнения на бесконечной линии, по которой каждой стороне лежит (т. е. v1 + Т(В2-В1) и V'1 + Т'(У'2-у'1) в основном), найти точку, в которой сходятся линии, решая для T, когда эти два уравнения равны (если они не параллельны, вы можете протестировать для этого) и затем проверки того, что точка лежит на прямой отрезок между двумя вершинами, т. е. это правда, что 0

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

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

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

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

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

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

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

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

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

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

если (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");}

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

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

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

вот реализация 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);

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

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

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

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