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?

From your description of your proposed solution, I'm assuming you're only looking for 180° rotational symmetry, and not any other kind (e.g. 120° rotational, reflective, etc) — Damien_The_Unbeliever, May 04 '11 at 09:10
Checking pairs only works for polygons with an even number of edges. — Sjoerd C. de Vries, May 04 '11 at 10:37
I think all the polygon with an odd number of edges can't be symmetric? @@ — Chan Le, May 04 '11 at 13:37
Isn't an equilateral (3 sides) symmetrical? You can definitely fold it in half onto itself, which is one definition of symmetric. — JCooper, May 06 '11 at 14:29

score 1 · Answer 1 · answered Sep 01 '13 at 19:32

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:

Set iter1 reference 0th vertex, and iter2 to reference Nth vertex.
Repeat N times:

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

score 1 · Accepted Answer · answered May 04 '11 at 09:07

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.

answered May 04 '11 at 09:07

user703016

37,307
8
87
112

This will only check for symmetry along the vertical axis. – Ezku May 04 '11 at 09:10
@Ezku - Heandel is inverting both coordinates, so I think this solution is checking for rotational symmetry, not reflective symmetry, as in the OPs original proposal – Damien_The_Unbeliever May 04 '11 at 09:12
1

what if the polygon has a point on one side which is on an edge, which does not occur on the other side polygon which has an edge which is identical? so A has points (0,0),(0,1),(0,2) and B has and edge (2,0),(2,2). They could be identical through the reflection line through x=2. You would need to ensure the polygon does not have extraneous points first... – Sam Holder May 04 '11 at 09:13
2

This checks that the polygon has the same vertices, but doesn't guarantee that they're connected in the same order. – Damien_The_Unbeliever May 04 '11 at 09:17
@Heandel True, sorry. Got kind of mixed up in the difference between the implications of your solution and what the OP wanted. Meant to say just that it doesn't seem to check for the right kind of symmetry. – Ezku May 04 '11 at 09:21
@Heandel - but the OP did specify (not necessarily convex) - which implies you need to know more than just the vertices. – Damien_The_Unbeliever May 04 '11 at 09:29
3

Obviously, not every triangle is symmetric. But an equilateral triangle, e.g., has three reflective and a three rotational symmetries, none of which will be found by your algorithm. – ackb May 07 '11 at 05:42

score 0 · Answer 3 · answered Jul 12 '17 at 01:31

0

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).

answered Jul 12 '17 at 01:31

Carlos Alegría

374
1
3
13

Check if a polygon is symmetric

3 Answers3