¿Cómo pruebo si un círculo y un polígono cóncavo se cruzan?

Tengo un polígono (a veces convexo, pero a menudo cóncavo), y un montón de círculos con diferentes radios. ¿Cómo puedo saber si un círculo se cruza / se superpone con el polígono?

Podría dividir mi polígono cóncavo en piezas convexas. ¿Eso ayudaría?

Hay dos casos de este problema. Primero es la intersección y el segundo que se superpone (contiene).

Primero (intersección / polígono dentro del círculo):

Encuentra el punto más cercano en cada borde del polígono al centro del círculo. Si cualquier distancia entre el punto más cercano al centro es menor que el radio, se obtiene una intersección o superposición.

Segundo (el círculo es entero en el polígono): dispare un rayo desde el centro del círculo hacia la derecha (o hacia la izquierda / arriba / abajo) y cuente las intersecciones de rayos / segmentos (bordes del polígono). Si el recuento de intersección es par, el círculo está fuera del polígono. Si es extraño, el círculo está adentro.

Compartiré el picter de la conferencia para este caso:

Y cuida los casos singulares.

Espero que esto ayude.

editar: creo que es justo agregar créditos a la imagen. El autor es Petr Felkel, profesor asistente de la Universidad Técnica Checa de Praga.

El primer paso, como supones, es dividir el polígono cóncavo en múltiples convexos. La razón de esto es que usará el teorema del eje de separación , que solo funciona en polígonos convexos.

SAT per se solo funciona en dos polígonos convexos. El "eje de separación" en el nombre se refiere a los ejes perpendiculares a los bordes del polígono. Los círculos, desafortunadamente, tienen un número infinito de estos. Sin embargo, resulta que hay una manera bastante fácil de descubrir cuáles de esos ejes son relevantes, al observar esto que se proyecta hacia afuera para intersecar los vértices del polígono.

En lugar de repasar todo el algoritmo aquí, Metanet Software (creadores de N / N +) tiene un buen tutorial sobre detección de colisiones usando SAT , cuya tercera sección cubre SAT cuando uno de los objetos es un círculo .

Esto es lo que hago.

1. Use la prueba de línea horizontal para detectar si el centro del círculo está dentro del polígono. Si es así, entonces se cruzan.
2. De lo contrario, verifique el siguiente caso. Para cada lado del polígono
   1. Encuentra la pendiente del lado del polígono
   2. Calcular la pendiente perpendicular
   3. (LEA ESTO CUIDADOSAMENTE) Encuentre la intersección entre una línea con la pendiente del lado del polígono que se cruza con cualquiera de los vértices que forman el lado, y la línea de la pendiente perpendicular a la del lado que interseca el centro del círculo.
   4. Si el punto de intersección establecido se encuentra dentro del círculo, esto significa que el círculo en algún punto cruza sobre el lado en cuestión y, por lo tanto, está intersectando el polígono
3. Por último, si nada más es concluyente, verifique si algún vértice del polígono se encuentra dentro del círculo (debido a pruebas anteriores, solo necesita verificarlo una vez). Si es así, se cruzan. Si no, puedes decir de manera concluyente que no lo hacen.