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

https://stackoverflow.com/questions/115426

02-07-2019
|

Pergunta

Eu estou procurando um algoritmo para detectar se dois retângulos interseção (um em um ângulo arbitrário, o outro com apenas linhas verticais / horizontais).

Teste se um canto de um está no outro quase funciona. Ele falha se os retângulos formar uma forma de cross-like.

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

Solução

O método padrão seria fazer o separando eixo test (faça uma pesquisa no Google sobre isso).

Em resumo:

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

A coisa divertida é, que é suficiente para apenas verificar todas as arestas dos dois retângulos. Se os retângulos não se sobrepõem uma das bordas será o eixo separando.

Em 2D você pode fazer isso sem o uso de encostas. 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 esta girando-a em 90 °. Em 2D isso é fácil como:

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

Portanto, não trigonometria ou declives envolvidos. Normalizando o vector de unidade de comprimento não é necessária qualquer.

Se você quiser testar se um ponto está em um ou outro lado da linha você pode apenas usar o produto escalar. o sinal irá dizer-lhe que lado você está em:

  // 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 testar todos os pontos de um rectângulo contra as bordas do rectângulo B e vice-versa. Se você encontrar uma borda que separa os objetos não se cruzam (fornecendo todos os outros pontos em B estão do outro lado da borda que está sendo testado para - veja o desenho abaixo). Se você não encontrar nenhuma margem que separa ambos os retângulos são interseção ou um retângulo está contida na outra.

O teste funciona com qualquer polígono convexo btw ..

Alteração: Para identificar uma borda que separa, não é suficiente para testar todos os pontos de um retângulo contra cada borda do outro. O candidato de ponta E (abaixo) que, como tal, ser identificado como uma aresta de separação, como todos os pontos em A são no mesmo meio-plano de E. No entanto, isso não é uma vantagem, porque a separação dos vértices VB1 e VB2 de B estão também no que semi-plano. Ele só teria sido uma vantagem separar se isso não tivesse sido o caso http://www.iassess.com/collision.png

Outras dicas

Basicamente olhar para a imagem a seguir:

href="https://i.stack.imgur.com/q9fHm.gif" rel="nofollow noreferrer">

Se as duas caixas de colidir, a linhas A e B irá sobrepor-se.

Note que isso terá de ser feito em ambos os X eo eixo Y, e ambos necessidade de sobreposição para os retângulos a colidir.

Há um bom artigo na gamasutra.com que responde à pergunta (a imagem é do artigo). Eu fiz algoritmo semelhante 5 anos atrás e eu tenho que encontrar o meu trecho de código para postar aqui mais tarde

Alteração : o dispositivo de separação do Eixo teorema indica que dois convexa formas não sobreposição se um eixo de separação existe (isto é, um onde as projecções como mostrados não sobreposição). Assim, "a separação de um eixo existe" => "Não sobreposição". Este não é um bi-implicação então você não pode concluir o inverso.

A resposta de m_pGladiator é certo e eu prefiro ele. separadora eixo teste é método mais simples e padrão para detectar sobreposição rectângulo. A linha para o qual os intervalos de projeção não se sobrepõem chamamos de separação eixo . A solução da Nils Pipenbrinck é demasiado geral. Ele usa dot produto para verificar se uma forma é totalmente de um lado da borda do outro. Esta solução é, na verdade, podia induzir a polígono convexo n de ponta. No entanto, não é otimizado para dois retângulos.

o ponto crítico da resposta de m_pGladiator é que devemos verificar projeção dois retângulos em ambas as cambotas (X e Y). Se duas projeções são sobrepostas, então poderíamos dizer que esses dois retângulos são sobrepostas. Portanto, os comentários acima a resposta de m_pGladiator estão errados.

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

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

chamamos Um retângulo, 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 são rodados, Pode precisa de alguns esforços para determinar a projeção deles em x e y axises. Definir struct RotatedRect como a seguir:

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

a diferença é a forma 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

poderia se referir a um GDC (Conferência Game Development 2007) PPT www.realtimecollisiondetection.net/pubs/ GDC07_Ericson_Physics_Tutorial_SAT.ppt

Em Cocoa você pode facilmente detectar se o rect selectedArea cruza seu rodado quadro rect de NSView. Você não precisa mesmo de polígonos calcular, normais de um tal. Basta adicionar esses métodos para sua subclasse NSView. Por exemplo, o usuário seleciona uma área na superview do NSView, em seguida, você chamar o DoesThisRectSelectMe método de passar o rect selectedArea. O convertRect API: vai fazer esse trabalho. O mesmo truque funciona quando você clicar no NSView para selecioná-lo. Nesse caso, basta substituir o método hitTest como abaixo. O convertPoint API: vai fazer 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;
}

Verifique para ver se alguma das linhas de um retângulo Intersect qualquer uma das linhas do outro. Naive intersecção segmento de linha é fácil de código-se.

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

Uma solução é usar algo chamado de Sem Fit Polygon. Este polígono é calculado a partir dos dois polígonos (conceptualmente por deslizamento uma em torno da outra) e que define a superfície para a qual os polígonos se sobrepõem dado o seu deslocamento relativo. Depois de ter este NFP então você simplesmente tem que fazer um teste de inclusão com um ponto dado pelo deslocamento relativo dos dois polígonos. Este teste inclusão é rápido e fácil, mas você tem que criar o NFP primeiro.

Tenha uma pesquisa Não Fit Polygon na web e veja se você pode encontrar um algoritmo para polígonos convexos (ele fica muito mais complexo se você tem polígonos côncavos). Se você não consegue encontrar nada, então email mim em howard ponto J dot pode gmail dot com

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

Verificar qualquer dos vértices do rectângulo uma residem dentro de rectângulo 2 e vice-versa. Sempre que você encontrar um vértice que reside dentro de outro retângulo você pode concluir que eles se cruzam e parar a pesquisa. Isto irá cuidar de um retângulo que reside completamente dentro do outro.
Se o teste acima é inconclusiva encontrar os pontos de interseção de cada linha de um retângulo com cada linha do outro retângulo. Uma vez que um ponto de intersecção é encontrado verificação se reside entre o interior do rectângulo imaginário criado pelos correspondentes 4 pontos. Sempre que tal um ponto é encontrado concluir que eles se cruzam e parar a pesquisa.

Se o acima de 2 testes retornar false, em seguida, estes 2 retângulos não se sobrepõem.

Se você estiver usando Java, todas as implementações da interface Forma ter um cruza método que tomar um retângulo.

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

A resposta matemática é formar equações que descrevem cada aresta dos dois retângulos. Agora você pode simplesmente encontrar se qualquer uma das quatro linhas de retângulo A intersecção qualquer uma das linhas de rectângulo B, que deve ser um simples (rápido) linear equação solver.

-Adam

Você pode encontrar a interseção de cada lado do retângulo angular com cada lado do um eixo alinhado. Para fazer isso, encontrar a equação da linha infinita em que cada mentiras laterais (isto é, V1 + t (V2-V1) e V'1 + t '(V? 2-V'1) basicamente), para encontrar o ponto no qual o linhas se encontram por resolver para t quando essas duas equações são iguais (se eles são paralelos, você pode testar para isso) e, em seguida, testando se que as mentiras ponto 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. Que você pode cobrir testando se os quatro pontos de qualquer mentira retângulo dentro do outro retângulo.

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

Modelo 2 os rectângulos como aviões descritos pela equação P1 e P2, em seguida, escrever P1 = P2 e derivam de que a linha de intersecção equação, que não existirá se os planos são paralelos (não intersecção), ou está na mesmo plano, caso em que você começa 0 = 0. Nesse caso, você precisará empregar um algoritmo retângulo interseção 2D.

Então eu iria ver se essa linha, que está no plano dos dois retângulos, passa por dois retângulos. Se isso acontecer, então você tem uma intersecção de 2 retângulos, caso contrário você não fazer (ou não deveria, eu poderia ter perdido um caso de canto na minha cabeça).

Para saber se uma linha passa por um retângulo no mesmo plano, eu iria encontrar os 2 pontos de interseção da linha e os lados do retângulo (modelagem-los usando equações de linha), e certifique-se os pontos de cruzamentos estão com no intervalo.

Essa é a descrições matemáticas, infelizmente, eu não tenho nenhum código para fazer o descrito acima.

Outra maneira de fazer o teste que é ligeiramente mais rápido do que usando o teste do eixo de separação, é usar o algoritmo de números de enrolamento (em quadrantes única - não ângulo somatório que é terrivelmente lento) em cada vértice de qualquer retângulo (escolhido arbitrariamente). Se qualquer um dos vértices tem um zero não-número de enrolamento, os dois retângulos se sobrepõem.

Este algoritmo é um pouco mais longo fôlego do que o teste do eixo de separação, mas é mais rápido porque apenas necessita de um teste semi-plano se bordas estão cruzando dois quadrantes (em oposição a um máximo de 32 ensaios utilizando a separação eixo método)

O algoritmo tem ainda a vantagem de que ele pode ser usado para ensaio de sobreposição qualquer polígono (convexa ou côncava). Tanto quanto eu sei, o algoritmo só funciona no espaço 2D.

Ou eu estou faltando alguma coisa por que fazer isso tão complicado?

if (x1, y1) e (X1, Y1) são cantos dos retângulos, em seguida, para encontrar intersecção fazer:

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

Eu implementado 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 transformação afim de matriz que converte pontos no espaço B de pontos no espaço A. Isto inclui simples rotação e translação, rotação mais dimensionamento, e urdiduras afins completo, mas não teias de perspectiva.

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

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

Este é o método convencional, linha movimento pela linha e verifique se as linhas são de interseção. Este é o código em 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 focada = 5165138 & tab = função

Eu tenho um método simplier do meu próprio, se temos 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ê pode fazer isso por caixas 3D também, na verdade ele funciona para qualquer número de dimensões.

muito já foi dito em outras respostas, então eu vou apenas acrescentar pseudocódigo one-liner:

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

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow