Comprueba si un polígono es simétrico

Question

Dado un polígono (no necesariamente convexo) en la coordenada cartesiana, me pregunto si hay alguna forma de verificar la simétrica de ese polígono.

Puedo pensar en una solución O (N): usar calibradores giratorios para verificar si cada par de bordes opuestos es paralelo y de igual tamaño.Sin embargo, no puedo probar la exactitud de ese algoritmo.¿Puede sugerir alguna solución mejor?

Answer 1

• Calcula el centro de gravedad de su polígono.
• Lo traslada al origen para que su centro de gravedad tenga (0,0) como coordenada.
• Luego, para cada vértice de coordenada (i, j), verifica que haya un vértice que tenga coordenadas (-i, -j).

Esto demostrará que su polígono es simétrico de hecho.

Complejidad: N, asumiendo que puede acceder directamente a sus vértices desde sus coordenadas.

Answer 2

Tienes que dejar más claro qué tipo de simetría se permite.¿Simetría central (también conocida como rotación de 180 grados)?¿Simetría de espejo sobre uno de los ejes?¿Rotación en algún grado?En algunas aplicaciones solo se permiten rotaciones de 0,90,180,270 + duplicación ... La respuesta sería diferente en cada caso.

Solo para la simetría central, si asume que el polígono está bien representado (es decir, no hay vértices adicionales en los bordes, y los vértices se mantienen en un contenido con un operador hacia adelante, entonces el polígono centralmente simétrico tendría un número par 2 * N vericesy puede hacer esto:

1. Establezca iter1 como referencia en el vértice 0 e iter2 como referencia en el vértice n.

2. Repetir N veces:

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

3. devuelve verdadero;

Answer 3

Primero debe definir el tipo de simetría que desea verificar (a qué transformación debe ser invariante su polígono).El algoritmo que proporcione comprobará la simetría central de los polígonos convexos (ya que los calibradores giratorios solo funcionan con polígonos convexos).