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

Question

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

В Какао вы могли легко определить, пересекает ли выбранный объект прямоугольник прямоугольник вашего повернутого кадра 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;
}

Answer 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 прямоугольником A, 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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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

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