Konkaves und konvexes Polygon
Wie kann ich diese vier RED-Punkte im Bild identifizieren und entfernen?
Diese vier Punkte machen das Polygon zu einem konkaven Polygon, deshalb möchte ich es entfernen.
Mein Ziel ist es, konkave Polygone in konvexe umzuwandeln, indem diese Art von Punkten entfernt wird, indem diese Punkte identifiziert und entfernt werden.
Gibt es eine Möglichkeit, diese Art von Punkten zu identifizieren und zu entfernen?
Danke
4 Antworten
Verwenden Sie einen konvexen Hüllenalgorithmus (z. B. Graham-Scan ) und entfernen Sie alle Punkte, die nicht sind Teil der resultierenden konvexen Hülle.
In Ihrem Beispiel besteht die konvexe Hülle aus P1, P2, P3, P5, P7, P8, P9, P11, P12, P13, P14, P15, P16, P18, die genau alle Punkte außer den roten sind .
Beachten Sie, dass das Entfernen von Punkten, deren Innenwinkel größer als 180 ist, nicht notwendigerweise zu einem konvexen Polygon führt. Nimm dieses Polygon zum Beispiel:
aioobe hat recht - Sie hören sich an, als ob Sie die konvexe Hülle Ihres Polygons berechnen möchten. In diesem Fall sollten Sie eines der konvexe Hüllenalgorithmen wie Graham Scan oder Chans Algorithmus.
Wenn Sie jedoch nur wissen möchten, ob ein Winkel konvex oder konkav ist, gibt es eine schnelle Möglichkeit, dies zu berechnen, wodurch Trigonometrie vermieden wird.
Wenn A, B und C aufeinanderfolgende Vertices sind, die im Uhrzeigersinn um das Polygon herumgehen, ist der Scheitelpunkt bei B konvex, wenn
(B - A) · (C - B) & lt; 0
Hier ist V ⟂ ein Vektor, der V um 90 ° gegen den Uhrzeigersinn gedreht ist, was wie folgt berechnet werden kann: ( x , y ) ⟂ = (- y , x ).
Sie können konkave Punkte erkennen, indem Sie den Innenwinkel betrachten - wenn er größer ist als ein Halbkreis, dann ist der Punkt konkav. Tatsächlich werden sie normalerweise Reflexpunkte genannt, weil der Innenwinkel ein Reflex ist.
Eine schnelle Überprüfung ist das Punktprodukt. Betrachten Sie zum Beispiel die drei Punkte P14, P15, P16. P16 liegt hinter der Linie, auf der das Segment zwischen P14 bis P15 liegt (dh das Skalarprodukt des Vektors von P15 bis P16 mit der Normalen zu dieser Linie ist negativ), also ist P15 ein konvexer Punkt.
P18 liegt vor der Linie, auf der das Segment von P16 bis P16 liegt (dh das Skalarprodukt des Vektors von P17 bis P18 mit der Normalen dieser Linie ist positiv), also ist P17 ein Reflexpunkt.
In 2d ist die Normale der Linie so einfach wie das Umdrehen der X- und Y-Koordinaten und das Negieren einer.
Was Sie jedoch vielleicht wollen, ist die konvexe Hülle - überlegen Sie, ob es konvexe Punkte geben könnte, die dennoch eine konkave Hülle erzeugen. Das offensichtlichste Beispiel ist, wenn ich P17 dort gelassen habe, wo es ist, aber P18 und P16 noch weiter in die Form, dahinter, verschoben habe. Wenn ja, dann sollten Sie konvexe Hüllen Algorithmen ausprobieren.
Ich vermute, Sie haben die Koordinaten für die Punkte (P1, P2 usw.). Sie können den Winkel, der zwischen den drei Punkten generiert wird, ermitteln und ihn entfernen, wenn er kleiner als 180 ist. Um den Winkel herauszufinden, überprüfen Sie Wie berechne ich einen Winkel von drei Punkten?
Tags und Links math