Como faço para testar se um círculo e um polígono côncavo se cruzam?

19

Eu tenho um polígono (às vezes convexo, mas muitas vezes côncavo) e um monte de círculos com raios diferentes. Como posso descobrir se um círculo se cruza / se sobrepõe ao polígono?

Eu poderia dividir meu polígono côncavo em pedaços convexos. Isso ajudaria?

Adam Harte
fonte

Respostas:

26

Existem dois casos desse problema. Primeiro é a interseção e o segundo está sobreposto (contendo).

Primeiro (interseção / polígono dentro do círculo):

Encontre o ponto mais próximo em todas as arestas do polígono até o centro do círculo. Se qualquer distância entre o ponto mais próximo do centro for menor que o raio, você terá interseção ou sobreposição.

Segundo (o círculo é inteiro em polígono): grave o raio do centro do círculo para a direita (ou esquerda / cima / baixo) e conte as interseções de raio / segmento (arestas do polígono). Se a contagem de interseções for par, o círculo estará fora do polígono. Se é um círculo estranho está dentro.

Vou compartilhar o picter da aula para este caso:

insira a descrição da imagem aqui

E cuide dos casos singulares.

Espero que isso ajude.


editar: acho justo adicionar créditos à imagem. O autor é Petr Felkel, professor assistente da Universidade Técnica Tcheca em Praga

Notabene
fonte
Eu não acho que isso funcionará apenas "disparando" um raio para a direita. Talvez eu tenha interpretado mal sua abordagem, mas, pelo que entendi, ela falharia com uma configuração como descrita aqui: imgur.com/Whg2u
bummzack
2
Sim, mas isso é descrito no primeiro caso. O raio de tiro resolverá apenas o círculo contendo polígono (segundo caso na minha descrição). Você tem que testar os dois casos. É rápido, fácil de implementar e não precisa de memória.
Notabene
1
Sinto muito por ter confundido "borda" com "vértice" e, portanto, ter interpretado mal sua primeira verificação. Ao lê-lo corretamente, ele funciona :)
bummzack
7

O primeiro passo, como você acha, é dividir o polígono côncavo em vários convexos. A razão para isso é que você usará o teorema do eixo separador , que funciona apenas em polígonos convexos.

O SAT por si só funciona em dois polígonos convexos. O "eixo separador" no nome refere-se aos eixos perpendiculares às arestas do polígono. Infelizmente, os círculos têm um número infinito deles. No entanto, verifica-se que há uma maneira muito fácil de descobrir quais desses eixos são relevantes, olhando para esse projeto externo para cruzar os vértices do polígono.

Em vez de revisar todo o algoritmo aqui, o Metanet Software (fabricantes de N / N +) possui um bom tutorial sobre detecção de colisão usando SAT , cuja terceira seção cobre o SAT quando um dos objetos é um círculo .


fonte
Você tem uma referência para dividir um polígono côncavo em polígonos convexos? O link SAT que você forneceu não menciona nada disso.
ehsanul
Na verdade, esse é um problema muito complexo, dependendo da geometria do polígono, mas todos os mecanismos 3D fazem isso, pois o hardware geralmente pode renderizar quads e triângulos coplanares e não polígonos.
SplinterReality
1
@ehsanul: en.wikipedia.org/wiki/Polygon_triangulation descreve algumas abordagens populares.
0

Aqui está o que eu faço.

  1. Use o teste de linha horizontal para detectar se o centro do círculo está dentro do polígono. Se for, eles se cruzam.
  2. Caso contrário, verifique o seguinte caso. Para cada lado do polígono
    1. Encontre a inclinação do lado do polígono
    2. Calcular a inclinação perpendicular
    3. (LEIA ATENTAMENTE) Encontre a interseção entre uma linha com a inclinação do lado do polígono que se cruza com um dos vértices que formam o lado e a linha da inclinação perpendicular à do lado que cruza o centro do círculo.
    4. Se o ponto de interseção estabelecido estiver dentro do círculo, isso significa que em algum momento o círculo cruza o lado em questão e, portanto, cruza o polígono
  3. Por fim, se nada mais for conclusivo, verifique se algum vértice do polígono está dentro do círculo (por causa de testes anteriores, você só precisa verificar uma vez). Nesse caso, eles se cruzam. Caso contrário, você pode dizer conclusivamente que não.
Chiraag Chakravarthy
fonte