Comment tester si un cercle et un polygone concave se croisent?

J'ai un polygone (parfois convexe, mais souvent concave), et un tas de cercles avec des rayons différents. Comment savoir si un cercle croise / chevauche le polygone?

Je pouvais diviser mon polygone concave en morceaux convexes. Est-ce que cela aiderait?

il y a deux cas de ce problème. La première est l'intersection et la seconde qui se chevauchent (contenant).

Premier (intersection / polygone à l'intérieur du cercle):

Trouvez le point le plus proche sur chaque arête du polygone au centre du cercle. Si une distance entre le point le plus proche du centre est inférieure au rayon, vous obtenez une intersection ou un chevauchement.

Deuxième (le cercle est entier dans le polygone): tirer le rayon du centre du cercle vers la droite (ou gauche / haut / bas) et compter les intersections rayon / segment (bords du polygone). Si le nombre d'intersections est pair, le cercle est en dehors du polygone. Si c'est un cercle étrange à l'intérieur.

Je vais partager picter de lectue pour ce cas:

Et prenez soin des cas singuliers.

J'espère que cela vous aidera.

edit: Je pense qu'il est juste d'ajouter des crédits à l'image. L'auteur est Petr Felkel, professeur adjoint à l'Université technique tchèque de Prague

Comme vous le devinez, la première étape consiste à diviser le polygone concave en plusieurs polygones convexes. La raison en est que vous utiliserez le théorème de l'axe de séparation , qui ne fonctionne que sur les polygones convexes.

SAT en soi ne fonctionne que sur deux polygones convexes. "L'axe de séparation" dans le nom fait référence aux axes perpendiculaires aux bords du polygone. Les cercles, malheureusement, en ont un nombre infini. Cependant, il s'avère qu'il existe un moyen assez simple de savoir lesquels de ces axes sont pertinents, en regardant ce qui se projette vers l'extérieur pour intersecter les sommets du polygone.

Plutôt que de parcourir l'intégralité de l'algorithme ici, Metanet Software (fabricants de N / N +) a un bon tutoriel sur la détection de collision à l'aide de SAT , dont la troisième section couvre SAT lorsque l'un des objets est un cercle .

Voici ce que je fais.

1. Utilisez le test de ligne horizontale pour détecter si le centre du cercle se trouve à l'intérieur du polygone. Si c'est le cas, alors ils se croisent.
2. Sinon, recherchez le cas suivant. Pour chaque côté du polygone
   1. Trouver la pente du côté du polygone
   2. Calculer la pente perpendiculaire
   3. (LISEZ ATTENTIVEMENT) Trouvez l'intersection entre une ligne avec la pente du côté du polygone coupant l'un ou l'autre sommet qui fait le côté, et la ligne de la pente perpendiculaire à celle du côté qui coupe le centre du cercle.
   4. Si le point d'intersection établi se trouve à l'intérieur du cercle, cela signifie que le cercle à un certain point croise le côté en question, et coupe donc le polygone
3. Enfin, si rien d'autre n'est concluant, vérifiez si des sommets du polygone se trouvent à l'intérieur du cercle (à cause des tests précédents, vous n'avez besoin de vérifier qu'une seule fois). Si c'est le cas, ils se coupent. Sinon, vous pouvez affirmer de façon concluante que non.