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?

Backspace

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) – Dovetailed

Checking pairs only works for polygons with an even number of edges. – Incrustation

I think all the polygon with an odd number of edges can't be symmetric? @@ – Backspace

They can be rotation symmetric. – Incrustation

Isn't an equilateral (3 sides) symmetrical? You can definitely fold it in half onto itself, which is one definition of symmetric. – Ligament

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.

Typo

This will only check for symmetry along the vertical axis. – Bastion

@Bastion - Heandel is inverting both coordinates, so I think this solution is checking for rotational symmetry, not reflective symmetry, as in the OPs original proposal – Dovetailed

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... – Talamantes

This checks that the polygon has the same vertices, but doesn't guarantee that they're connected in the same order. – Dovetailed

@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. – Bastion

@Heandel - but the OP did specify (not necessarily convex) - which implies you need to know more than just the vertices. – Dovetailed

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. – Lexy

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;

Wistful

Answer 3

I had a need to answer this question as well, expanding on the chosen answer and criticism of it I created a method that converts to polar coordinates around the centroid, then check the radius within a given precision of the intersections of a target angle, and that angle minus 180deg. If at least one common radius exists between the two checks then that portion of the shape is considered symmetirc.

x,y = (np.array(v) for v in shape.exterior.coords.xy)
xc = shape.centroid.x
yc = shape.centroid.y
dx= x-xc
dy= y-yc

dth = np.arctan2(dx,dy)
rth = (dx**2 + dy**2)**0.5
inx = np.cumsum(np.ones(dth.size))-1

Nincr = 1000
Imax = inx.max()
inx2 = np.linspace(0,Imax,Nincr)

R = np.interp(inx2,inx,rth)
T = np.interp(inx2,inx,dth)

def find_radii(targetth,precision=3):
    """targetth must be positive from 0->pi"""
    r = (dth - targetth)
    #print(r)
    if np.all(r < 0):
        r = r + np.pi
    elif np.all(r > 0):
        r = r - np.pi
    sgn = np.concatenate([ r[1:]*r[:-1], [r[0]*r[-1]] ] )
    possibles = np.where( sgn < 0)[0]
    #print(f'\n{targetth}')
    out = set()
    for poss in possibles:
        poss2 = int((poss+1)%Imax)
        x_ = np.array([r[poss],r[poss2]])
        y_ = np.array([inx[poss],inx[poss2]])
        itarget = (0 - x_[0])*(y_[1]-y_[0])/(x_[1]-x_[0]) + y_[0]
        r_ = np.interp(itarget,inx2,R)
        out.add(round(r_,precision))
        #print(itarget,r_)
    return out


syms = []
for targetth in np.linspace(0,np.pi,Nincr ):
    o1 = find_radii(targetth)
    o2 = find_radii(targetth-np.pi)
    sym_point = len(o1.intersection(o2)) >= 1
    syms.append(sym_point)
    
symmetric = np.all(syms)
print(f'symmetric: {symmetric}')

Orangeism

Answer 4

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

Kirst