Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Check if a polygon is symmetric

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?

like image 805
Chan Le Avatar asked May 04 '11 09:05

Chan Le


People also ask

How do we test if a polygon has point symmetry?

If a figure is rotated 180 degrees about a point and it coincides with its original position, then it is said that the figure has point symmetry. The point of rotation is called the point of symmetry. The figure below shows the point symmetric polygon ABCDEF rotated clockwise about P, its point of symmetry.

Are polygons symmetrical?

Regular polygons are symmetrical and divided by more than one lines of symmetry to form identical parts. A rectangle is divided into symmetrical parts with the help of two lines. An equilateral triangle is divided into identical parts with the help of three lines of symmetry passing through its center.

What are the 4 types of symmetry?

Types of symmetries are rotational symmetry, reflection symmetry, translation symmetry, and glide reflection symmetry. These four types of symmetries are examples of different types of symmetry on a flat surface called planar symmetry.


2 Answers

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

like image 130
user703016 Avatar answered Sep 22 '22 21:09

user703016


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;

like image 36
Michael Avatar answered Sep 24 '22 21:09

Michael