Wie teste ich, ob sich ein Kreis und ein konkaves Polygon schneiden?

Ich habe ein Polygon (manchmal konvex, aber oft konkav) und ein paar Kreise mit unterschiedlichen Radien. Wie kann ich herausfinden, ob ein Kreis das Polygon schneidet / überlappt?

Ich konnte mein konkaves Polygon in konvexe Stücke teilen. Würde das helfen?

Es gibt zwei Fälle dieses Problems. Erstens ist die Kreuzung und zweitens, die sich überlappen (enthalten).

Erster (Schnittpunkt / Polygon innerhalb des Kreises):

Suchen Sie an jeder Kante des Polygons den nächstgelegenen Punkt zum Mittelpunkt des Kreises. Wenn der Abstand zwischen dem nächstgelegenen Punkt und dem Mittelpunkt kleiner als der Radius ist, liegt ein Schnittpunkt oder eine Überlappung vor.

Zweite (Kreis ist ganz im Polygon): Nehmen Sie den Strahl von der Kreismitte nach rechts (oder nach links / oben / unten) auf und zählen Sie die Schnittpunkte von Strahl / Segment (Polygonkanten). Wenn die Schnittmenge gerade ist, liegt der Kreis außerhalb des Polygons. Wenn es ein seltsamer Kreis ist, ist er drinnen.

Ich werde picter aus Vortrag für diesen Fall teilen:

Und kümmere dich um die einzelnen Fälle.

Hoffe das wird helfen.

edit: Ich denke, dass es nur fair ist, dem Bild Credits hinzuzufügen. Autor ist Petr Felkel, Assistenzprofessor an der Tschechischen Technischen Universität in Prag

Der erste Schritt besteht darin, das konkave Polygon in mehrere konvexe zu teilen. Der Grund dafür ist, dass Sie den Satz der Trennachse verwenden , der nur für konvexe Polygone gilt.

SAT per se funktioniert nur mit zwei konvexen Polygonen. Die "Trennachse" im Namen bezieht sich auf die Achsen senkrecht zu den Kanten des Polygons. Leider gibt es unendlich viele Kreise. Es stellt sich jedoch heraus, dass es eine ziemlich einfache Möglichkeit gibt, herauszufinden, welche dieser Achsen relevant sind, indem Sie auf diese schauen, die nach außen ragen, um die Eckpunkte des Polygons zu schneiden.

Anstatt hier den gesamten Algorithmus durchzugehen, haben Metanet Software (Hersteller von N / N +) ein gutes Tutorial zur Kollisionserkennung mit SAT , dessen dritter Abschnitt SAT behandelt, wenn eines der Objekte ein Kreis ist .

Hier ist was ich tue.

1. Verwenden Sie den Horizontallinientest, um festzustellen, ob der Mittelpunkt des Kreises innerhalb des Polygons liegt. Wenn ja, dann kreuzen sie sich.
2. Wenn nicht, überprüfen Sie den folgenden Fall. Für jede Seite des Polygons
   1. Ermitteln Sie die Neigung der Polygonseite
   2. Berechnen Sie die senkrechte Neigung
   3. (LESEN SIE DIES SORGFÄLTIG DURCH.) Ermitteln Sie den Schnittpunkt zwischen einer Linie mit der Steigung der Polygonseite, die sich mit einem der Scheitelpunkte schneidet, die die Seite bilden, und der Linie mit der Steigung senkrecht zu der Seite, die den Mittelpunkt des Kreises schneidet.
   4. Liegt der ermittelte Schnittpunkt innerhalb des Kreises, so bedeutet dies, dass der Kreis an einem bestimmten Punkt die betreffende Seite kreuzt und somit das Polygon schneidet
3. Wenn nichts anderes aussagekräftig ist, prüfen Sie schließlich, ob Eckpunkte des Polygons innerhalb des Kreises liegen (aufgrund vorheriger Tests müssen Sie nur einmal prüfen). Wenn ja, schneiden sie sich. Wenn nicht, können Sie abschließend sagen, dass dies nicht der Fall ist.