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

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?

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:

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

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 .

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.