Algoritmo para detectar a interseção de dois retângulos?

143

Estou procurando um algoritmo para detectar se dois retângulos se cruzam (um em um ângulo arbitrário, o outro apenas com linhas verticais / horizontais).

Testar se um canto de um está no outro QUASE funciona. Ele falha se os retângulos formarem uma forma de cruz.

Parece uma boa idéia evitar o uso de inclinações das linhas, o que exigiria casos especiais para linhas verticais.

user20493
fonte
e se você adicionar à verificação de canto, uma verificação para ver se o segundo retângulo está dentro dos limites (retangulares) do retângulo angular?
Wes P
Em que idioma você fará isso? Porque em Java existem classes internas que permitem fazer isso.
Martijn
Eu acho que a API gráfica e a maioria das bibliotecas de GUI (como swing) implementou isso.
l_39217_l 22/09/08
que pode perder casos em que se sobrepõem, mas nenhum canto é dentro de qualquer retângulo
Florian Bösch
1
Esta pergunta é quase a mesma que: stackoverflow.com/questions/306316/… . Embora isso esteja procurando uma solução que seja particularmente para C ++. A resposta aceita também é bastante simples e direta.
Silver Gonzales

Respostas:

162

O método padrão seria fazer o teste do eixo de separação (faça uma pesquisa no google sobre isso).

Em resumo:

  • Dois objetos não se cruzam se você puder encontrar uma linha que os separa. por exemplo, os objetos / todos os pontos de um objeto estão em lados diferentes da linha.

O mais divertido é que basta verificar todas as arestas dos dois retângulos. Se os retângulos não se sobrepuserem, uma das arestas será o eixo de separação.

Em 2D, você pode fazer isso sem usar inclinações. Uma aresta é simplesmente definida como a diferença entre dois vértices, por exemplo

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

Você pode obter uma perpendicular a isso girando em 90 °. Em 2D, é fácil como:

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

Portanto, não há trigonometria ou declives envolvidos. A normalização do vetor para o comprimento da unidade também não é necessária.

Se você quiser testar se um ponto está em um ou outro lado da linha, basta usar o produto escalar. o sinal indicará de que lado você está:

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

Agora teste todos os pontos do retângulo A contra as bordas do retângulo B e vice-versa. Se você encontrar uma aresta de separação, os objetos não se cruzam (desde que todos os outros pontos em B estejam do outro lado da aresta sendo testada - veja o desenho abaixo). Se você não encontrar uma aresta de separação, os retângulos estão se cruzando ou um retângulo está contido no outro.

O teste funciona com qualquer polígono convexo entre.

Alteração: para identificar uma aresta de separação, não basta testar todos os pontos de um retângulo em relação a cada aresta da outra. A aresta candidata E (abaixo) seria, como tal, identificada como aresta de separação, pois todos os pontos em A estão no mesmo semiplano de E. No entanto, não é uma aresta de separação porque os vértices Vb1 e Vb2 de B também estão nesse semi-plano. Seria apenas uma aresta de separação se esse não fosse o caso http://www.iassess.com/collision.png

Nils Pipenbrinck
fonte
2
Este algoritmo não funciona para todos os casos. É possível colocar o segundo retângulo girado 45 graus em relação ao primeiro retângulo e deslocar ao longo da diagonal para que ele cumpra os testes de interseção acima, mas não se cruze.
Skizz 22/09/08
6
Skizz, verifique todas as oito arestas. Se os objetos não se cruzarem, uma das oito arestas os separará. Por que você não publica uma imagem mostrando seu caso? Eu posso lhe mostrar o eixo ..
Nils Pipenbrinck 22/09/08
2
Meu erro, ele lida com essa condição.
Skizz 22/09/08
2
A imagem está morta agora (nov 2012)
John Dvorak
2
Como tive problemas para visualizar isso, recriei como era a imagem que estava sendo referenciada. imgur.com/bNwrzsv
Rjdlee
16

Basicamente, observe a seguinte imagem:


Se as duas caixas colidirem, as linhas A e B se sobrepõem.

Observe que isso terá que ser feito nos eixos X e Y, e ambos precisam se sobrepor para que os retângulos colidam.

Há um bom artigo no gamasutra.com que responde à pergunta (a imagem é do artigo). Eu fiz um algoritmo semelhante há 5 anos e tenho que encontrar meu snippet de código para publicá-lo aqui mais tarde

Alteração : O Teorema do Eixo Separador afirma que duas formas convexas não se sobrepõem se existir um eixo de separação (ou seja, aquele em que as projeções mostradas não se sobrepõem). Então "Existe um eixo de separação" => "Sem sobreposição". Isso não é uma implicação dupla, portanto você não pode concluir o inverso.

m_pGladiator
fonte
1
Obviamente, como dois quadrados (0,0,1,1) e (0,3,1,4) não se sobrepõem, mas suas projeções no eixo x se sobrepõem completamente. Ambos os testes são necessários, a combinação é suficiente.
MSalters
18
Não é suficiente que as projeções x e y se sobreponham: considere, por exemplo, os retângulos [(0,0), (0,3), (3,3), (3,0)] e [(2,5), (5,2), (7,4), (4,7)].
Joel em Gö
4
Eu concordo com @Joel em Gö. Esse método perde um grande conjunto de casos em que os retângulos não se sobrepõem, mas seus raios projetados se diferenciam em xey.
21711 Scott Scott T
5
Esta resposta não está errada, mas é enganosa. É verdade que: Se as duas caixas colidirem, as linhas A e B se sobrepõem. mas também é verdade que: Se as linhas A e B se sobrepõem, as duas caixas podem ou não ser colidindo
mate queima
7
@ flutuador: Eu diria que não é apenas errado, mas também enganoso, o que é ainda pior.
BlueRaja - Danny Pflughoeft 26/01
4

A resposta do m_pGladiator está certa e eu prefiro. O teste do eixo de separação é o método mais simples e padrão para detectar a sobreposição de retângulos. Uma linha para a qual os intervalos de projeção não se sobrepõem, chamamos de eixo de separação . A solução de Nils Pipenbrinck é muito geral. Ele usa produto de ponto para verificar se uma forma está totalmente de um lado da borda da outra. Esta solução é realmente capaz de induzir polígonos convexos n-edge. No entanto, não é otimizado para dois retângulos.

o ponto crítico da resposta de m_pGladiator é que devemos verificar a projeção de dois retângulos nos dois eixos (x e y). Se duas projeções forem sobrepostas, poderíamos dizer que esses dois retângulos estão sobrepostos. Portanto, os comentários acima para a resposta de m_pGladiator estão errados.

para a situação simples, se dois retângulos não são rotacionados, apresentamos um retângulo com estrutura:

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

nomeamos o retângulo A, B com 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

se qualquer um dos dois retângulos for girado, pode ser necessário algum esforço para determinar a projeção deles nos eixos xey. Defina struct RotatedRect da seguinte maneira:

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

a diferença é como a largura 'agora é um pouco diferente: widthA' para rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB 'para 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

Pode se referir a um PPT da GDC (Game Development Conference 2007) www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Tristan
fonte
Por que você precisa de Math.abs () em "Math.abs (rectA.width + rectB.width)", para lidar com larguras negativas?
21413 AlexWien
O eixo de separação não é necessariamente uma direção da bússola, pode ter qualquer ângulo.
Ben Voigt
Retângulos não rotados rectA (x = 0, y = 0, largura = 1, altura = 1) e rectB (x = 2, y = 0, largura = 100, altura = 1) não se cruzam, mas seu método diz que cruzar. Estou fazendo algo errado?
Kagami Sascha Rosylight
4

No Cocoa, você pode detectar facilmente se o retângulo de Área selecionada cruza o retângulo de quadro do NSView girado. Você nem precisa calcular polígonos, normais como esse. Basta adicionar esses métodos à sua subclasse NSView. Por exemplo, o usuário seleciona uma área na superview do NSView e chama o método DoesThisRectSelectMe passando o rectArea selectedArea. A API convertRect: fará esse trabalho. O mesmo truque funciona quando você clica no NSView para selecioná-lo. Nesse caso, simplesmente substitua o método hitTest como abaixo. A API convertPoint: fará esse trabalho ;-)

- (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
fonte
2
Esse código funciona apenas para retângulos quadrados à tela. Esse é um caso trivial. A suposição é que estamos lidando com retângulos que não estão em ângulos de 90 graus em relação à tela ou um ao outro.
Duncan C
Como verifiquei e usei em meus aplicativos, esse código funciona em qualquer retângulo girado. Não importa o grau de rotação.
Leonardo
Isso não descreve o algoritmo, no entanto, apenas menciona uma biblioteca que já o utiliza.
Ben Voigt
2

Verifique se alguma das linhas de um retângulo cruza alguma das linhas do outro. A interseção ingênua do segmento de linha é fácil de codificar.

Se você precisar de mais velocidade, existem algoritmos avançados para interseção de segmento de linha (linha de varredura). Veja http://en.wikipedia.org/wiki/Line_segment_intersection

Louis Brandy
fonte
4
Cuidado! Não se esqueça do caso em que um retângulo inclui completamente outro
Pitarou
2

Uma solução é usar algo chamado polígono sem ajuste. Esse polígono é calculado a partir dos dois polígonos (conceitualmente deslizando um ao redor do outro) e define a área pela qual os polígonos se sobrepõem, devido ao seu deslocamento relativo. Depois de ter esse NFP, basta fazer um teste de inclusão com um ponto dado pelo deslocamento relativo dos dois polígonos. Esse teste de inclusão é rápido e fácil, mas você precisa criar o NFP primeiro.

Pesquise o polígono No Fit na Web e veja se consegue encontrar um algoritmo para polígonos convexos (fica muito mais complexo se você tiver polígonos côncavos). Se você não encontrar nada, envie-me um e-mail para howard dot J dot may gmail dot com

Howard May
fonte
1

Aqui está o que eu acho que vai cuidar de todos os casos possíveis. Faça os seguintes testes.

  1. Verifique se algum dos vértices do retângulo 1 reside dentro do retângulo 2 e vice-versa. Sempre que você encontrar um vértice que reside dentro do outro retângulo, poderá concluir que eles se cruzam e param a pesquisa. Isso cuidará de um retângulo residindo completamente dentro do outro.
  2. Se o teste acima for inconclusivo, encontre os pontos de interseção de cada linha de 1 retângulo com cada linha do outro retângulo. Quando um ponto de interseção é encontrado, verifique se ele reside entre o retângulo imaginário criado pelos 4 pontos correspondentes. Sempre que esse ponto for encontrado, conclua que eles se cruzam e interrompem a pesquisa.

Se os 2 testes acima retornarem falsos, esses 2 retângulos não se sobrepõem.

John Smith
fonte
0

Se você estiver usando Java, todas as implementações da interface Shape têm um método de interseção que usa um retângulo.

Brendan Cashman
fonte
Infelizmente estou usando c #. A classe Rectangle possui um método Contains (), mas é apenas para retângulos não rotacionados.
User20493
método intersects () é bastante inútil, pois retorna booleano em vez de interseção, eu acho.
ZZ 5
0

Bem, o método da força bruta é percorrer as bordas do retângulo horizontal e verificar cada ponto ao longo da borda para ver se ele cai sobre ou no outro retângulo.

A resposta matemática é formar equações descrevendo cada aresta dos dois retângulos. Agora você pode simplesmente descobrir se alguma das quatro linhas do retângulo A cruza alguma das linhas do retângulo B, que deve ser um solucionador de equações linear simples (rápido).

-Adão

Adam Davis
fonte
2
O problema com as equações é quando você tem uma linha vertical, que tem inclinação infinita.
User20493
Existem casos extremos para todas as soluções.
Adam Davis
2
e um quadrado envolvendo completamente o outro.
Oliver Hallam
0

Você pode encontrar a interseção de cada lado do retângulo angular com cada lado do retângulo alinhado ao eixo. Faça isso encontrando a equação da linha infinita na qual cada lado se encontra (por exemplo, v1 + t (v2-v1) e v'1 + t '(v'2-v'1) basicamente), encontrando o ponto em que o as linhas se encontram resolvendo t quando essas duas equações são iguais (se forem paralelas, você pode testar isso) e testando se esse ponto está no segmento de linha entre os dois vértices, ou seja, é verdade que 0 <= t <= 1 e 0 <= t '<= 1.

No entanto, isso não cobre o caso quando um retângulo cobre completamente o outro. Isso você pode cobrir testando se todos os quatro pontos de um retângulo estão dentro do outro retângulo.

HenryR
fonte
0

Isto é o que eu faria, para a versão 3D deste problema:

Modele os 2 retângulos como planos descritos pelas equações P1 e P2, depois escreva P1 = P2 e derive a linha de equação de interseção, que não existirá se os planos forem paralelos (sem interseção) ou estiverem no mesmo plano, nesse caso, você obtém 0 = 0. Nesse caso, você precisará empregar um algoritmo de interseção de retângulo 2D.

Então eu veria se essa linha, que está no plano dos dois retângulos, passa por ambos os retângulos. Se isso acontecer, você terá uma interseção de 2 retângulos, caso contrário, você não tem (ou não deveria, talvez eu tenha perdido uma caixa de canto na minha cabeça).

Para descobrir se uma linha passa por um retângulo no mesmo plano, eu encontraria os 2 pontos de interseção da linha e os lados do retângulo (modelando-os usando equações de linha) e, em seguida, verifique se os pontos de interseção estão em alcance.

Essas são as descrições matemáticas, infelizmente não tenho código para fazer o acima.

espaço livre
fonte
Você perdeu a parte em que, se encontrar a linha de interseção plana, precisará garantir que uma parte dela exista nos dois retângulos.
Lee Louviere
0

Outra maneira de fazer o teste um pouco mais rápido do que o teste do eixo de separação é usar o algoritmo dos números de enrolamento (apenas nos quadrantes - não a soma dos ângulos, que é terrivelmente lenta) em cada vértice de qualquer retângulo (escolhido arbitrariamente). Se algum dos vértices tiver um número de corda diferente de zero, os dois retângulos se sobrepõem.

Esse algoritmo é um pouco mais demorado do que o teste do eixo de separação, mas é mais rápido porque exige apenas um teste de meio plano se as arestas estiverem cruzando dois quadrantes (em oposição a até 32 testes usando o método do eixo de separação)

O algoritmo tem a vantagem adicional de poder ser usado para testar a sobreposição de qualquer polígono (convexo ou côncavo). Até onde eu sei, o algoritmo funciona apenas no espaço 2D.

Mads
fonte
3
Posso estar errado, mas isso não verifica apenas se os vértices de um retângulo estão dentro de outro? Se sim, não é suficiente porque os retângulos podem se sobrepor sem nenhum vértice dentro.
sinelaw
Eles podem, com retângulos? Quão? Parece-me que, para que dois retângulos se cruzem, pelo menos um vértice de um dos retângulos deve estar no outro retângulo.
Duncan C
@DuncanC: Sim, eles podem. O contraexemplo é uma cruz e foi listado na pergunta original.
Ben Voigt
@BenVoigt Este é um tópico muito antigo, mas você está absolutamente certo.
Duncan C
0

Ou estou perdendo outra coisa, por que tornar isso tão complicado?

se (x1, y1) e (X1, Y1) são cantos dos retângulos, para encontrar a interseção, faça:

    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
fonte
3
Você está sentindo falta de que ele queira que um seja girado por um ângulo arbitrário.
007 Robotbugs
0

Eu implementei assim:

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

A matriz mB é qualquer matriz de transformação afim que converte pontos no espaço B em pontos no espaço A. Isso inclui rotação e translação simples, rotação mais escala e distorções afins completas, mas não distorções de perspectiva.

Pode não ser o melhor possível. A velocidade não era uma grande preocupação. No entanto, parece funcionar bem para mim.

Robotbugs
fonte
0

Aqui está uma implementação matlab da resposta aceita:

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);
Jed
fonte
0

Este é o método convencional, vá linha por linha e verifique se as linhas estão se cruzando. Este é o código no 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

a função InterX pode ser baixada em: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Siva Srinivas Kolukula
fonte
0

Eu tenho um método mais simples, se tivermos 2 retângulos:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Eles se sobrepõem se e somente se:

Sobreposição = (max_x1> min_x2) e (max_x2> min_x1) e (max_y1> min_y2) e (max_y2> min_y1)

Você também pode fazer isso em caixas 3D, na verdade funciona para qualquer número de dimensões.

BitFarmer
fonte
0

Já foi dito o suficiente em outras respostas, então adicionarei apenas uma linha de pseudocódigo:

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