Vérifiez si un polygone est symétrique

Question

Étant donné un polygone (non nécessaire convexe) dans la coordonnée cartésienne, je me demande s'il existe un moyen de vérifier la symétrie de ce polygone?

Je peux penser à une solution O (n): utiliser des étriers rotatifs pour vérifier si chaque paire de bord opposé est parallèle et égale. Cependant, je ne peux pas prouver l'exactitude de cet algorithme. Pouvez-vous suggérer une meilleure solution?

Answer 1

• Vous calculez le centre de gravité de votre polygone.
• Vous le traduisez par l'origine afin que votre centre de gravité ait (0,0) de coordonnées.
• Ensuite, pour chaque sommet de coordonnées (i, j), vous vérifiez qu'il y a un sommet qui a des coordonnées (-i, -j).

Cela prouvera que votre polygone est en effet symétrique.

Complexité: N, en supposant que vous pouvez accéder directement à vos sommets à partir de leurs coordonnées.

Answer 2

Vous devez indiquer plus clairement quel type de symétrie est autorisé. Symétrie centrale (rotation à 180 degrés)? Miroir Symétrie sur l'un des axes? Rotation par quelque degré? Dans certaines applications, seules les rotations de 0,90,180,270 + miroir sont autorisées ... la réponse serait différente dans chaque cas.

Pour la symétrie centrale uniquement, si vous supposez que le polygone est bien représentateur (c'est-à-dire pas de sommets supplémentaires sur les bords, et que les sommets sont conservés dans un opérateur avant, alors le polygone symétrique central aurait un numéro 2 * n numéro 2, et vous vous peut le faire:

1. Définissez la référence ITER1 0th Vertex et ITER2 pour référence au nth vertex.

2. Répéter n fois:

   if (* iter1! = * iter2) return false;

3. retourne vrai;

Answer 3

Vous devez d'abord définir le type de symétrie que vous souhaitez vérifier (quelle transformation votre polygone doit être invariant). L'algorithme que vous fournissez vérifiera la symétrie centrale pour les polygones convexes (car les étriers rotatifs ne fonctionnent qu'avec des polygones convexes).