给定笛卡尔坐标中的多边形(不一定是凸的),我想知道是否有任何方法可以检查该多边形的对称性?
我可以想到一个 O(N) 的解决方案:使用旋转卡尺检查每对相对边是否平行且大小相等。但是,我无法证明该算法的正确性。您能提出更好的解决方案吗?
你必须更清楚什么样的对称性是允许的。中心对称(又名 180 度旋转)?围绕其中一根轴镜像对称?任意角度旋转?在某些应用程序中,仅允许旋转 0,90,180,270 + 镜像...每种情况下的答案都会不同。
仅对于中心对称,如果您假设多边形可以很好地表示(即边上没有额外的顶点,并且顶点被包含在前向运算符中,那么中心对称多边形将具有偶数个 2*N 顶点,并且你可以这样做:
设置iter1引用第0个顶点,设置iter2引用第N个顶点。
重复N次:
if( *iter1 != *iter2 ) 返回 false;
返回真;
您首先需要定义要检查的对称类型(您的多边形应该保持不变的变换)。您提供的算法将检查凸多边形的中心对称性(因为旋转卡尺仅适用于凸多边形)。
我也需要回答这个问题,扩展了所选答案和对其的批评,我创建了一种方法,将其转换为质心周围的极坐标,然后检查目标角度交点给定精度内的半径,该角度为负180°。如果两个检查之间至少存在一个公共半径,则形状的该部分被认为是对称的。
x,y = (np.array(v) for v in shape.geom.exterior.coords.xy)
xc,yc = shape.calculate_centroid()
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_ = 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}')
这将证明你的多边形确实是对称的。
复杂度:N,假设您可以从坐标直接访问顶点。