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.
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.
Respostas:
(Pseudocódigo C-ish - adapte as otimizações de idioma conforme apropriado)
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.
fonte
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.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,
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:
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
ou a borda direita de r2 fica mais à esquerda do que a borda esquerda de r1
ou a borda superior de r2 está abaixo da borda inferior de r1
ou a borda inferior de r2 está acima da borda superior de 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 /
fonte
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.
fonte
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.
fonte
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 = <.
fonte
Versão alternativa da resposta de ZorbaTHut:
fonte
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.
fonte
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 ..fonte
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 :
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_VALUE
eInteger.MIN_VALUE
).fonte
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_ps
com 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:Finalmente, se necessário,
_mm_movemask_ps
para 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.
fonte