Como faço para determinar se dois polígonos convexos se cruzam?

Question

Suponha que há um número de polígonos convexos em um avião, talvez um mapa. Estes polígonos pode colidir uns contra os outros e compartilhar uma vantagem, mas não pode se sobrepõem.

Para testar se dois polígonos P e Q sobreposição, em primeiro lugar pode testar cada aresta em P para ver se ele intersecta com qualquer de as bordas em Q . Se uma interseção for encontrado, eu declaro que P e Q Intersect. Se nenhum intersectam, que depois têm de teste para o caso em que P está completamente contido por Q , e vice-versa. Em seguida, há o caso que P == Q . Finalmente, há o caso que compartilham algumas arestas, mas não todos eles. (Estes dois últimos casos provavelmente pode ser pensado como o mesmo caso geral, mas que pode não ser importante.)

Eu tenho um algoritmo que detecta onde dois segmentos de linha se cruzam. Se os dois segmentos são co-linear, eles não são considerados para cruzar para os meus propósitos.

Já enumerei adequadamente os casos? Todas as sugestões para testar para estes casos?

Note que não estou olhando para encontrar o novo polígono convexo que é a interseção, eu só quero saber se existe uma interseção. Há muitos algoritmos bem documentados para encontrar o cruzamento, mas não precisa passar por todo o esforço.

Answer 1

Você pode usar este algoritmo de colisão :

Para poder decidir se dois polígonos convexos são interseção (tocar uns aos outros), podemos usar o Axis Teorema de separação. Essencialmente:

• Se dois polígonos convexos não são interseção, existe uma linha que passa entre eles.
• Uma tal linha só existe se um dos lados de uma das formas de polígonos uma tal linha.

A primeira declaração é fácil. Desde os polígonos são ambas convexas, você será capaz de desenhar uma linha com um polígono de um lado e do outro polígono do outro lado a menos que sejam interseção. A segunda é ligeiramente menos intuitivo. Olhada na figura 1. Salvo o mais próximo do lado dos polígonos são paralelas entre si, o ponto onde eles ficam mais próximos entre si é o ponto onde um canto de um polígono fica mais próxima de um lado do outro polígono. Este lado vai então formar um eixo de separação entre os polígonos. Se os lados são paralelos, ambos são separando eixos.

Então, como isso ajuda concretamente nos decidir se polígono A e B se cruzam? Bem, nós apenas passar por cima de cada lado de cada polígono e verificar se ele forma um eixo separando. Para fazer isso vamos usar um pouco de matemática básica vetor para esmagar todos os pontos de ambos os polígonos em uma linha que é perpendicular ao potencial de linha de separação (ver figura 2). Agora, todo o problema é convenientemente 1-dimensional. Podemos determinar uma região em que os pontos para cada mentira polígono, e esta linha é um eixo separando se estas regiões não se sobreponham.

Se, depois de verificar cada linha de ambos os polígonos, nenhum eixo separando foi encontrado, ficou provado que os polígonos se cruzam e algo tem de ser feito sobre isso.

Answer 2

• Se os polígonos são sempre convexo, primeiro calcular o ângulo de uma linha traçada de centro a centro dos polígonos. então você pode eliminar a necessidade de segmentos de ponta de teste na metade do polígono (s) 180 graus de distância do outro polígono (s).

• para eliminar as bordas, comece com o polígono no lado esquerdo. levar o segmento de linha do centro do polígono que é perpendicular ao segmento de linha a partir do ponto anterior, e toca ambos os lados do polígono. chamar este segmento de linha p, com vértices P1 e P2. Então, para todos os vértices se a coordenada x é inferior a p1.x e p2.x esse vértice pode ir no "balde seguro".

• Se isso não acontecer, você tem que verificar para ter certeza que está no lado "seguro" da linha (basta verificar as coordenadas y também)

-se um segmento de linha no polígono tem todos os vértices do "balde seguro" você pode ignorá-lo.

-Reverse a polaridade de modo que você está "certo orientada" para o segundo polígono.

Answer 3

Seus casos de teste deve funcionar, desde que você está verificando o caso em que os polígonos não se cruzam em tudo (completamente fora ou completamente dentro), bem como onde há qualquer forma de intersecção parcial (bordas se cruzam sempre se houver é sobreposição).

Para os testes, gostaria apenas certifique-se de testar todas as combinações potencial. O que está faltando acima do que eu vejo é uma vantagem única compartilhada, mas um poli contido no outro. Gostaria de acrescentar também testes para algumas formas poli mais complexas, de tri -.> Muitos lados, apenas como precaução

Além disso, se você tivesse uma forma de U poli que cercava completamente o poli, mas não se sobrepõem, eu acredito que o seu caso iria lidar com isso, mas gostaria de acrescentar que, como um cheque, também.

Answer 4

Desde altCognito já lhe deu uma solução, eu só vai apontar um excelente livro sobre geometria computacional que lhe possam interessar.

Answer 5

GJK colisão detecção deve trabalho .

Answer 6

Aqui está uma idéia:

• Encontre o ponto central de cada polígono

• Encontre os dois pontos de cada polígono mais próximo do ponto central da outra. Eles serão pontos adjacentes em polígono convexo. Estes definem a extremidade mais próxima de cada polígono, vamos chamar os pontos {A, B} e {Y, Z}

• Encontre o cruzamento de linhas AB e YZ. Se os segmentos de linha cruzar (a interseção em mentiras AB entre A e B), os polígonos se cruzam. Se AB e XY são paralelas ignorar esta condição, a próxima armadilha passo será o problema.

• Há mais um caso, você precisa verificar se há, que é quando os polígonos cruzam fortemente o suficiente para que AB e XY são completamente umas sobre as outras e não realmente se cruzam. Para interceptar este caso, calcular as distâncias perpendiculares de AB e XY para cada um dos pontos de centro polígonos. Se qualquer ponto central está mais perto de segmento de linha o oposto do polígono seu polígono sobreposição pesadamente.

Answer 7

Existem várias maneiras de detectar cruzamento e / ou contenção entre polígonos convexos. Tudo depende de quão eficiente você deseja que o algoritmo para ser. Considere dois polígonos convexos R e B com r e b vértices, respectivamente:

1. linha de varredura algoritmo baseado. Como você mencionou, você pode realizar um procedimento de linha de varredura e manter os intervalos resultantes da intersecção dos polígonos com a linha de varredura. Se a qualquer momento os intervalos se sobrepõem, então os polígonos se cruzam. A complexidade é O ((r + b) log (r + b)) tempo.
2. Rotating Calibrador algoritmo baseado. Consulte aqui e aqui para mais detalhes. A complexidade é O tempo (r + b).
3. Os métodos mais eficientes pode ser encontrada aqui e aqui . Estes algoritmos tomar O (log r + log b) tempo.