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?
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.
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.
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.
This will prove that your polygon is symmetric indeed.
Complexity : N, assuming you can access directly your vertices from their coordinates.
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;
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With