Überprüfen Sie, ob ein Polygon symmetrisch ist

Question

Angesichts eines Polygons (nicht unbedingt konvex) in der kartesischen Koordinate frage ich mich, ob es eine Möglichkeit gibt, die Symmetrie dieses Polygons zu überprüfen?

Ich kann mir eine O (N) -Lösung vorstellen: Verwenden Sie rotierende Bremssättel, um zu überprüfen, ob jedes Paar gegenüberliegender Kanten parallel und gleich groß ist.Ich kann jedoch die Richtigkeit dieses Algorithmus nicht beweisen.Können Sie eine bessere Lösung vorschlagen?

Answer 1

• Sie berechnen den Schwerpunkt Ihres Polygons.
• Sie übersetzen es in den Ursprung, sodass Ihr Schwerpunkt (0,0) als Koordinate hat.
• Dann überprüfen Sie für jeden Koordinatenscheitelpunkt (i, j), ob es einen Scheitelpunkt mit Koordinaten (-i, -j) gibt.

  Dies beweist, dass Ihr Polygon tatsächlich symmetrisch ist.

  Komplexität: N, vorausgesetzt, Sie können von ihren Koordinaten aus direkt auf Ihre Scheitelpunkte zugreifen.

Answer 2

Sie müssen klarer machen, welche Art von Symmetrie zulässig ist.Zentrale Symmetrie (a.k.a. 180 Grad Drehung)?Spiegelsymmetrie über einer der Achsen?Rotation um irgendeinen Grad?In einigen Anwendungen sind nur Rotationen um 0,90,180,270 + Spiegelung zulässig ... Die Antwort wäre in jedem Fall anders.

Wenn Sie nur für die zentrale Symmetrie davon ausgehen, dass das Polygon gut repräsentativ ist (dh keine zusätzlichen Scheitelpunkte an Kanten und Scheitelpunkte in einem mit einem Vorwärtsoperator enthaltenen enthalten sind, hat das zentral symmetrische Polygon eine gerade Zahl 2 * N Vericesund Sie können dies tun:

1. Setzen Sie iter1 auf den 0. Scheitelpunkt und iter2 auf den N-ten Scheitelpunkt.

2. N-mal wiederholen:

   if (* iter1!= * iter2) gibt false zurück;

3. gibt true zurück;

Answer 3

Sie müssen zuerst die Art der Symmetrie definieren, die Sie überprüfen möchten (für welche Transformation sollte Ihr Polygon unveränderlich sein).Der von Ihnen bereitgestellte Algorithmus überprüft die zentrale Symmetrie für konvexe Polygone (da rotierende Bremssättel nur mit konvexen Polygonen funktionieren).