您的形状不仅可以旋转,还可以平移并且甚至可以缩放。节点的方向也可能不同。例如,原始的正方形边长为1.0,逆时针定义,而菱形边长为1.414,顺时针定义。
您需要找到一个好的参考对象进行比较。以下应该有效:
- 为每个形状找到重心C。
- 确定所有节点的径向坐标(r,φ),其中径向坐标系统的原点是重心C。
- 对于每个形状,将半径归一化,使得形状中r的最大值为1.0。
- 确保节点逆时针定向,即随着角度φ的增加。
现在您有两个n个径向坐标的列表。(已经排除了节点数不匹配或少于三个节点的情况。)
评估所有n个偏移配置,其中您保留第一个数组,移动第二个数组。对于四个元素的数组,您将比较:
{a1, a2, a3, a4} <=> {b1, b2, b3, b4}
{a1, a2, a3, a4} <=> {b2, b3, b4, b1}
{a1, a2, a3, a4} <=> {b3, b4, b1, b2}
{a1, a2, a3, a4} <=> {b4, b1, b2, b3}
径向坐标是浮点数。当比较值时,应该允许一些余地以适应由浮点数计算引入的不准确性。因为数字0 ≤ r ≤ 1和−π ≤ φ ≤ π大致在相同的范围内,所以可以使用固定的epsilon。
半径通过其归一化值进行比较。角度通过与列表中前一个点的角度差进行比较。当该差异为负时,我们已经绕过了360°的边界,必须进行调整。(我们必须强制执行正角度差异,因为我们要比较的形状可能没有被等比旋转,因此可能没有绕过间隙。) 角度可以向前和向后,但最终必须完整地绕一圈。
代码必须检查n个配置,并为每个测试所有n节点。实际上,不匹配会很快被发现,因此代码应该具有良好的性能。如果您要比较很多形状,则可能值得预先创建所有形状的归一化,逆时针径向表示。
无论如何,下面开始:
def radial(x, y, cx = 0.0, cy = 0.0):
"""Return radial coordinates from Cartesian ones"""
x -= cx
y -= cy
return (math.sqrt(x*x + y*y), math.atan2(y, x))
def anticlockwise(a):
"""Reverse direction when a is clockwise"""
phi0 = a[-1]
pos = 0
neg = 0
for r, phi in a:
if phi > phi0:
pos += 1
else:
neg += 1
phi0 = phi
if neg > pos:
a.reverse()
def similar_r(ar, br, eps = 0.001):
"""test two sets of radial coords for similarity"""
_, aprev = ar[-1]
_, bprev = br[-1]
for aa, bb in zip(ar, br):
if abs(aa[0] - bb[0]) > eps:
return False
da = aa[1] - aprev
db = bb[1] - bprev
if da < 0: da += 2 * math.pi
if db < 0: db += 2 * math.pi
if abs(da - db) > eps:
return False
aprev = aa[1]
bprev = bb[1]
return True
def similar(a, b):
"""Determine whether two shapes are similar"""
if len(a) != len(b) or len(a) < 3:
return False
ax, ay = [1.0 * sum(x) / len(x) for x in zip(*a)]
bx, by = [1.0 * sum(x) / len(x) for x in zip(*b)]
ar = [radial(x, y, ax, ay) for x, y in a]
br = [radial(x, y, bx, by) for x, y in b]
amax = max([r for r, phi in ar])
bmax = max([r for r, phi in br])
ar = [(r / amax, phi) for r, phi in ar]
br = [(r / bmax, phi) for r, phi in br]
anticlockwise(ar)
anticlockwise(br)
n = len(a)
while n:
if similar_r(ar, br):
return True
br.append(br.pop(0))
n -= 1
return False
编辑:虽然这个解决方案可行,但过于复杂。罗布的答案本质上相似,但使用了一种简单的度量方法:边缘之间的内部角度,它可以自动处理平移和缩放。
[(0,0),(2,0),(2,1),(0,1)]
,它是一个矩形吗?它不是一个正方形。 - rob mayoffrectangle
和square
被认为是相同的。正如我在notice
中所写的,不同的长度被认为是相似的。 - ZK Zhaororatated_rectangle
的点的顺序与rectangle
的点的顺序也相反。也就是说,rectangle
是顺时针方向的,但roratated_rectangle
是逆时针方向的。它们应该被视为相似吗? - rob mayoff角度序列
的检查。 - ZK Zhaoconvex hull
算法一样? - ZK Zhao