Check if a polygon is symmetric

Question

Given a polygon (not necessary convex) in the Cartesian coordinate, i wonder if there are any way to check the symmetricalness of that polygon?

I can think of an O(N) solution: using rotating calipers to check if each pair of opposite edge is parallel and equal in size. However, i can't prove the correctness of that algorithm. Can you suggest any better solution?

Answer 1

• You compute the center of gravity of your polygon.
• You translate it to the origin so that your center of gravity has (0,0) as coordinate.
• Then for each vertex of coordinate (i, j) you check that there is a vertex that has coordinates (-i, -j).

This will prove that your polygon is symmetric indeed.

Complexity : N, assuming you can access directly your vertices from their coordinates.

Answer 2

You've got to make it more clear what kind of symmetry is allowed. Central symmetry (a.k.a. 180 degree rotation)? Mirror symmetry over one of the axes? Rotation by any degree? In some applications only rotations by 0,90,180,270 + mirroring are allowed... The answer would be different in each case.

For central symmetry only, if you assume that polygon is nicely representer (i.e. no extra vertices on edges, and vertices are held in a contained with a forward operator, then the centrally symmetric polygon would have an even number 2*N verices, and you can do this:

1. Set iter1 reference 0th vertex, and iter2 to reference Nth vertex.

2. Repeat N times:

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

3. return true;

Answer 3

You first need to define the type of symmetry you want to check (what transformation your polygon should be invariant to). The algorithm you provide will check central symmetry for convex polygons (as rotating calipers only works with convex polygons).