Qual é a maneira mais rápida de calcular a interseção de caixas delimitadoras 2D?

62

Suponha que cada objeto Caixa tenha as propriedades x, y, largura, altura e tenha sua origem no centro e que nem os objetos nem as caixas delimitadoras giram.

Iain
fonte
São esses eixos ou caixas delimitadoras alinhadas a objetos?
101310 tenpn em
3
Quando você faz essa pergunta, certamente precisará testar outros tipos de interseções no futuro;). Portanto, sugiro A LISTA sobre a intersecção Objeto / Objeto. A tabela fornece interseções entre todos os tipos de objetos populares (caixas, esferas, triângulos, cilindros, cones, ...) em situações estáticas e dinâmicas.
Dave O.
2
Reformule sua pergunta em recta delimitadora. Do meu ponto de vista, a caixa implica um objeto 3d.
Dave O.

Respostas:

55

(Pseudocódigo C-ish - adapte as otimizações de idioma conforme apropriado)

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));
}

Em inglês: em cada eixo, verifique se os centros das caixas estão próximos o suficiente para se cruzarem. Se eles se cruzam nos dois eixos, as caixas se cruzam. Se não, então não.

Você pode alterar os <'s para <= se desejar contar o toque da borda como interseção. Se você deseja uma fórmula específica apenas para toque na borda, não pode usar == - que informará se os cantos tocam, não se as bordas tocam. Você gostaria de fazer algo logicamente equivalente return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

Vale ressaltar que você pode obter um aumento de velocidade pequeno, mas significativo, armazenando a meia largura e a meia altura, além de (ou em vez de) a largura e a altura completas. Por outro lado, é raro o cruzamento da caixa delimitadora em 2d ser o gargalo de desempenho.

ZorbaTHut
fonte
9
Obviamente, isso pressupõe que as caixas estejam alinhadas ao eixo.
101310 tenpn em
11
O abdômen não deve ser particularmente lento - não mais lento que um condicional, pelo menos, e a única maneira de fazê-lo sem os abdominais (que eu conheço) envolve condicionais extras.
ZorbaTHut
4
Sim, ele assume caixas alinhadas ao eixo. Porém, as estruturas descritas não têm como indicar rotação, então eu senti que era seguro.
ZorbaTHut
3
Aqui estão algumas boas dicas para acelerar as calulações no Actionscript (principalmente número inteiro): lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math Estou postando isso, porque ele também contém um substituto para Math.abs (), que tende a desacelerar as coisas no Actionscript (falando de itens críticos de desempenho, é claro).
bummzack
2
Você está sentindo falta de que eles tenham a origem no centro, não na borda esquerda. Uma caixa que executa de 0 a 10 terá realmente "x = 5", enquanto uma caixa que executa de 8 a 12 terá "x = 10". Você acaba com abs(5 - 10) * 2 < (10 + 4)=> 10 < 14. Você precisará fazer alguns ajustes simples para fazê-lo funcionar com o canto e o tamanho das pessoas.
precisa saber é o seguinte
37

Isso funciona para dois retângulos alinhados com os eixos X e Y.
Cada retângulo possui as propriedades:
"esquerda", a coordenada x do seu lado esquerdo,
"superior", a coordenada y do seu lado superior,
"direita", a coordenada x do seu lado direito,
"inferior", a coordenada y do seu lado inferior,

function IntersectRect(r1:Rectangle, r2:Rectangle):Boolean {
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top);
}

Observe que isso foi projetado para um sistema de coordenadas no qual o eixo + y aponta para baixo e o eixo + x é direcionado para a direita (ou seja, coordenadas típicas da tela / pixel). Para adaptar isso a um sistema cartesiano típico no qual + y é direcionado para cima, as comparações ao longo dos eixos verticais seriam revertidas, por exemplo:

return !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

A idéia é capturar todas as condições possíveis nas quais os retângulos não se sobrepõem e, em seguida, negar a resposta para ver se eles estão sobrepostos. Independentemente da direção dos eixos, é fácil ver que dois retângulos não se sobrepõem se:

  • a borda esquerda de r2 é mais à direita do que a borda direita de r1

     ________     ________
    |        |   |        |
    |   r1   |   |   r2   |
    |        |   |        |
    |________|   |________|
    
  • ou a borda direita de r2 fica mais à esquerda do que a borda esquerda de r1

     ________     ________
    |        |   |        |
    |   r2   |   |   r1   |
    |        |   |        |
    |________|   |________|
    
  • ou a borda superior de r2 está abaixo da borda inferior de r1

     ________ 
    |        |
    |   r1   |
    |        |
    |________|
     ________ 
    |        |
    |   r2   |
    |        |
    |________|
    
  • ou a borda inferior de r2 está acima da borda superior de r1

     ________ 
    |        |
    |   r2   |
    |        |
    |________|
     ________ 
    |        |
    |   r1   |
    |        |
    |________|
    

A função original - e uma descrição alternativa do porquê funciona - podem ser encontradas aqui: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect- um-outro-ou-não /

Ponkadoodle
fonte
11
Surpreendentemente intuitivo e mostra mais uma vez que, quando encontrar a resposta é muito difícil, tentar encontrar a resposta para uma pergunta oposta pode ajudá-lo. Obrigado!
Lodewijk
11
Você deve mencionar que o eixo y aponta para baixo (como em uma imagem). Caso contrário, as desigualdades r2.top> r1.bottom e r2.bottom <r1.top precisam ser revertidas.
precisa saber é o seguinte
@ user1443778 boa captura! Fui em frente e também expliquei a lógica por trás desse algoritmo de uma maneira independente do sistema de coordenadas.
Ponkadoodle
11

Se você deseja caixas delimitadoras alinhadas a objetos, tente este tutorial sobre o teorema do eixo de separação por metanet: http://www.metanetsoftware.com/technique/tutorialA.html

O SAT não é a solução mais rápida, mas é relativamente simples. Você está tentando encontrar uma única linha (ou um avião se 3D) que separará seus objetos. Se essa linha existir, é garantido que fique paralelo à borda de uma de suas caixas; portanto, você percorre todos os testes de bordas para ver se ela separa as caixas.

Isso também funciona para caixas alinhadas ao eixo restringindo apenas o eixo x / y.

tenpn
fonte
Eu não estava pensando em rotação, mas obrigado, esse é um link interessante.
Iain
5

O DoBoxesIntersect acima é uma boa solução emparelhada. No entanto, se você tiver muitas caixas, ainda terá um problema de O (N ^ 2) e poderá achar que precisa fazer algo além disso, como o que Kaj se refere. (Na literatura de detecção de colisão 3D, isso é conhecido por ter um algoritmo de fase ampla e de fase estreita. Faremos algo muito rápido para encontrar todos os pares possíveis de sobreposições e, em seguida, algo mais caro para ver se é possível pares são pares reais.)

O algoritmo de fase ampla que eu usei antes é "varredura e remoção"; para 2D, você manteria duas listas classificadas do início e do fim de cada caixa. Contanto que o movimento da caixa não seja >> escala de caixa de quadro para quadro, a ordem dessas listas não mudará muito e, portanto, você poderá usar a classificação de bolha ou inserção para mantê-lo. O livro "Real-Time Rendering" apresenta um ótimo resumo das otimizações que você pode fazer, mas resume-se ao tempo O (N + K) na fase ampla, para N boxes, K das quais se sobrepõem e com excelente mundo real desempenho, se você puder pagar por booleanos N ^ 2 para acompanhar quais pares de caixas estão cruzando de quadro a quadro. Em seguida, você tem tempo O (N + K ^ 2) geral, que é << O (N ^ 2) se você tiver muitas caixas, mas apenas algumas sobreposições.

Tom Hudson
fonte
5

Muita matemática aqui para um problema muito simples, suponha que temos 4 pontos determinados para um ret, superior, esquerdo, inferior, direito ...

No caso de determinar se 2 rects colidem, precisamos apenas observar que todos os extremos possíveis que impediriam colisões, se nada disso for atingido, então os 2 rects DEVEM colidir, se você quiser incluir colisões de limites, basta substituir o> e < com apropriado> = e = <.

struct aRect{
  float top;
  float left;
  float bottom;
  float right;
};

bool rectCollision(rect a, rect b)
{
  return ! ( b.left > a.right || b.right < a.left || b.top < a.bottom || b.bottom > a.top);
}
user35189
fonte
Sinceramente, não sei por que essa não é a resposta mais votada. É simples, correto e eficiente.
3Dave
3

Versão alternativa da resposta de ZorbaTHut:

bool DoBoxesIntersect(Box a, Box b) {
     return (abs(a.x - b.x) < (a.width + b.width) / 2) &&
     (abs(a.y - b.y) < (a.height + b.height) / 2);
}
Iain
fonte
Na verdade, a aritmética funciona bem de qualquer maneira. Você pode fazer qualquer operação aritmética em qualquer um dos lados de <e isso não a altera (multiplicação por um negativo significa que você deve alterar menos que). Nesse exemplo, as caixas não devem colidir. Se o centro da caixa A estiver em 1, ele se estende de -4 a 6. A caixa b se centra em 10 e se estende de 7,5 a 12,5, não há colisão lá ... Agora, o método que Wallacoloo postou não está apenas correto, mas irá correr mais rápido em línguas que implementam curto-circuito, uma vez que a maioria das verificações retornará falso de qualquer maneira, o curto-circuito pode cortar depois como
Deleter
Sim, eu percebi isso quando acordei esta manhã. Chris me enganou com sua mistura.
Iain
11
Dois problemas: primeiro, a divisão tende a ser significativamente mais lenta que a multiplicação. Segundo, se os valores envolvidos forem inteiros, isso poderá resultar em alguns problemas de truncamento inteiro (ax = 0, bx = 9, a.width = 9, b.width = 10: abs (0-9) <(9 + 10) / 2, 9 <19/2, 9 <9, a função retorna false apesar do fato de que as caixas definitivamente se cruzam).
ZorbaTHut
2

Dependendo do problema que você tenta resolver, é melhor manter o controle de seu objeto enquanto os move, ou seja, mantenha uma lista de x ordenadas x posições inicial e final e uma para as posições inicial e final y. Se você precisar fazer MUITAS verificações de sobreposição e, portanto, precisar otimizar, poderá usar isso a seu favor, pois poderá imediatamente procurar quem está terminando se fecha à sua esquerda, todos os que estão terminando à esquerda podem ser podados imediatamente. O mesmo se aplica às partes superior, inferior e direita.
A contabilidade custa tempo, é claro, por isso é mais adequada para uma situação com poucos objetos em movimento, mas muitas verificações de sobreposição.
Outra opção é o hash espacial, onde você agrupa os objetos com base na posição aproximada (o tamanho pode colocá-los em vários buckets), mas, novamente, somente se houver muitos objetos, com relativamente poucos deles se movendo por iteração devido ao custo da contabilidade.
Basicamente, qualquer coisa que evite (n * n) / 2 (se você marcar o objeto a contra b, não precisará verificar b contra a obviamente) ajuda mais do que otimizar as verificações das caixas delimitadoras. Se as verificações das caixas delimitadoras forem um gargalo, seriamente aconselhável procurar soluções alternativas para o problema.

Kaj
fonte
2

A distância entre os centros não é a mesma que a distância entre os cantos (quando uma caixa está dentro da outra, por exemplo); portanto, EM GERAL, essa solução é a correta (eu acho).

distância entre os centros (por exemplo, x): abs(x1+1/2*w1 - x2+1/2*w2)ou1/2 * abs(2*(x1-x2)+(w1-w2)

A distância mínima é 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). as metades cancelam assim ..

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));
Vladimir Dizhoor
fonte
11
O que há com a declaração "return" lá?
Doppelgreener 23/09/12
1

Aqui está minha implementação em Java, assumindo uma arquitetura de dois complementos . Se você não usa o complemento duplo , use uma chamada de função Math.abs padrão :

boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
    return
        (
            lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
            lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
            lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
        ) == 0;
}

int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
    final int
            leftWidth = leftMax - leftMin,
            rightWidth = rightMax - rightMin,

            leftMid = leftMin + ((leftMax - leftMin) >> 1),
            rightMid = rightMin + ((rightMax - rightMin) >> 1);

    return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
}

int abs(int value) {
    final int mask = value >> (Integer.SIZE - 1);

    value ^= mask;
    value += mask & 1;
    return value;
}

Supondo que um compilador semi-decente / LLVM em linha expanda essas funções para evitar malabarismos de pilha e pesquisas de tabela v. Isso falhará para valores de entrada próximos de extremos de 32 bits (ie Integer.MAX_VALUEe Integer.MIN_VALUE).

MadMartian
fonte
0

A maneira mais rápida é combinar todos os 4 valores em um único registro vetorial.

Armazene as caixas em um vetor com os seguintes valores [ min.x, min.y, -max.x, -max.y ]. Se você armazenar caixas como essa, o teste de interseção leva apenas 3 instruções da CPU:

_mm_shuffle_ps para reordenar a segunda caixa girando as metades min e max.

_mm_xor_pscom número mágico _mm_set1_ps(-0.0f)para inverter os sinais de todos os 4 valores na segunda caixa.

_mm_cmple_ps para comparar todos os 4 valores entre si, comparando os dois registros a seguir:

[ a.min.x, a.min.y, -a.max.x, -a.max.y ] < [ b.max.x, b.max.y, -b.min.x, -b.min.y ]

Finalmente, se necessário, _mm_movemask_pspara obter o resultado da unidade vetorial em um registro escalar. Valor 0 significa as caixas cruzadas. Ou, se você tiver mais de 2 caixas, isso não é necessário, deixe os valores nos registros vetoriais e use operações bit a bit para combinar resultados de várias caixas.

Você não especificou idioma nem plataforma, mas o suporte para SIMD como este, ou muito semelhante, está disponível em todas as plataformas e idiomas. No celular, o ARM possui NEON SIMD com coisas muito semelhantes. O .NET possui o Vector128 no espaço para nome System.Runtime.Intrinsics e assim por diante.

Soonts
fonte