检查多边形是否对称

Question

给定笛卡尔坐标中的多边形（不一定是凸的），我想知道是否有任何方法可以检查该多边形的对称性？

我可以想到一个 O(N) 解决方案：使用旋转卡尺检查每对相对边是否平行且大小相等。但是，我无法证明该算法的正确性。您能建议更好的解决方案吗？

Answer 1

你必须更加清楚什么样的对称性是允许的。中心对称（又名 180 度旋转）？围绕其中一根轴镜像对称？任意角度旋转？在某些应用程序中，只允许旋转 0,90,180,270 + 镜像...每种情况下的答案都会不同。

仅对于中心对称，如果您假设多边形可以很好地表示（即边上没有额外的顶点，并且顶点被包含在前向运算符中，那么中心对称多边形将具有偶数个 2*N 顶点，并且您可以这样做：

1. 设置iter1引用第0个顶点，iter2引用第N个顶点。

2. 重复 N 次：

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

3. 返回真；

Answer 2

我也需要回答这个问题，扩展了所选答案和对其的批评，我创建了一种方法，可以转换为质心周围的极坐标，然后检查目标角度交点给定精度内的半径，并且该角度为负180°。如果两个检查之间至少存在一个公共半径，则形状的该部分被认为是对称的。

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}')

Answer 3

• 您计算多边形的重心。
• 您将其平移到原点，以便您的重心坐标为 (0,0)。
• 然后，对于坐标 (i, j) 的每个顶点，检查是否存在具有坐标 (-i, -j) 的顶点。

这将证明你的多边形确实是对称的。

复杂度：N，假设您可以从坐标直接访问顶点。

Answer 4

您首先需要定义要检查的对称类型（多边形应该保持不变的变换）。您提供的算法将检查凸多边形的中心对称性（因为旋转卡尺仅适用于凸多边形）。