Check if the polygon is symmetrical

Question

Given a polygon (not necessarily convex) in a Cartesian coordinate, I wonder if there is a way to check the symmetry of this polygon?

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

Answer 1

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

This will prove that your polygon is really symmetrical.

Difficulty: N, assuming you can directly get your vertices from your coordinates.

Answer 2

You need to understand what symmetry is allowed. Central symmetry (180 degree rotation)? Mirror symmetry over one of the axes? Rotation to any degree? In some applications, only 0,90,180,270 rotations + mirroring are allowed ... In each case, the answer will be different.

Only for central symmetry, if you assume that the polygon is a beautiful representative (i.e. there are no extra vertices on the edges, and the vertices are held in the containing one with the direct operator, then the centrally symmetric polygon will have an even number of 2 * N vertices, and you can do it:

• Set iter1 to the 0th vertex, and iter2 to the Nth vertex.

• Repeat N times:

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

• return true;

Answer 3

First you need to determine the type of symmetry you want to check (which transformation your polygon should have). The algorithm you provide will check for central symmetry for convex polygons (since rotating calipers only work with convex polygons).