Python和算法：如何进行简单的几何形状匹配？

Question

给定一组有序的 点，我想知道它的形状是否属于某些类型。这些类型包括：

rectangle = [(0,0),(0,1),(1,1),(1,0)]
hexagon = [(0,0),(0,1),(1,2),(2,1),(2,0),(1,-1)]
l_shape = [(0,0),(0,3),(1,3),(1,1),(3,1),(3,0)]
concave = [(0,0),(0,3),(1,3),(1,1),(2,1),(2,3),(3,3),(3,0)]
cross = [(0,0),(0,-1),(1,-1),(1,0),(2,0),(2,1),(1,1),(1,2),(0,2),(0,1),(-1,1),(-1,0)]

例如，给出roratated_rectangle = [(0,0),(1,1),(0,2),(-1,1)]，我们可以知道它属于上面的rectangle。 与相似。

注意：

1.不同长度的rotation和边缘被视为相似。

2.输入点是有序的。(因此可以用

- cqcn1991

---

这种方法听起来可行，尽管对于非凸形状可能会导致一些奇怪的匹配。 - augurar

您对“矩形”的定义是正方形。那么对于[(0,0),(2,0),(2,1),(0,1)]，它是一个矩形吗？它不是一个正方形。 - rob mayoff

@robmayoff，我的错，rectangle和square被认为是相同的。正如我在 notice 中所写的，不同的长度被认为是相似的。 - ZK Zhao

你的 roratated_rectangle 的点的顺序与 rectangle 的点的顺序也相反。也就是说，rectangle 是顺时针方向的，但 roratated_rectangle 是逆时针方向的。它们应该被视为相似吗？ - rob mayoff

@robmayoff，是的，我在我的思考中提到了角度序列的检查。 - ZK Zhao

@augurar 有没有相关的模块？就像 Python 中的 convex hull 算法一样？ - ZK Zhao

Answer 1

你的想法基本正确。你希望比较测试形状中的角序列与预定义形状中的角序列（针对每个预定义形状）。由于测试形状的第一个顶点可能不对应匹配的预定义形状的第一个顶点，因此我们需要允许测试形状的角序列相对于预定义形状的角序列进行旋转。（也就是说，你的测试形状序列可能是a、b、c、d，但你的预定义形状是c、d、a、b。）此外，测试形状的序列也可能被反转，这种情况下，相对于预定义形状的角度也将被否定。（也就是说，a、b、c、d相对于-d、-c、-b、-a或等效地2π-d、2π-c、2π-b、2π-a。）

我们可以尝试选择一个标准的角序列旋转。例如，我们可以找到字典序最小的旋转。（例如，l_shape给出的序列为3π/2、3π/2、π/2、3π/2、3π/2、3π/2。字典序最小的旋转将把π/2放在第一位：π/2、3π/2、3π/2、3π/2、3π/2、3π/2。）

然而，我认为存在四舍五入的风险。选择测试形状与预定义形状不同的规范旋转。因此，我们将检查所有旋转。

首先，编写一个返回形状角序列的函数：

import math

def anglesForPoints(points):
    def vector(tail, head):
        return tuple(h - t for h, t in zip(head, tail))

    points = points[:] + points[0:2]
    angles = []
    for p0, p1, p2 in zip(points, points[1:], points[2:]):
        v0 = vector(tail=p0, head=p1)
        a0 = math.atan2(v0[1], v0[0])
        v1 = vector(tail=p1, head=p2)
        a1 = math.atan2(v1[1], v1[0])
        angle = a1 - a0
        if angle < 0:
            angle += 2 * math.pi
        angles.append(angle)
    return angles

（请注意，仅使用点积计算余弦不足够，因为我们需要一个有符号的角度，但是cos（a）== cos（-a）。）

接下来，一个生成器产生列表的所有旋转：

def allRotationsOfList(items):
    for i in xrange(len(items)):
        yield items[i:] + items[:i]

最后，确定两个形状是否匹配：

def shapesMatch(shape0, shape1):
    if len(shape0) != len(shape1):
        return False

    def closeEnough(a0, a1):
        return abs(a0 - a1) < 0.000001

    angles0 = anglesForPoints(shape0)
    reversedAngles0 = list(2 * math.pi - a for a in reversed(angles0))
    angles1 = anglesForPoints(shape1)
    for rotatedAngles1 in allRotationsOfList(angles1):
        if all(closeEnough(a0, a1) for a0, a1 in zip(angles0, rotatedAngles1)):
            return True
        if all(closeEnough(a0, a1) for a0, a1 in zip(reversedAngles0, rotatedAngles1)):
            return True
    return False

（请注意，由于浮点数舍入误差，我们需要使用模糊比较。由于我们知道角度始终在小范围内固定为0 … 2π，因此我们可以使用绝对误差限制。）

>>> shapesMatch([(0,0),(1,1),(0,2),(-1,1)], rectangle)
True
>>> shapesMatch([(0,0),(1,1),(0,2),(-1,1)], l_shape)
False
>>> shapesMatch([(0,0), (1,0), (1,1), (2,1), (2,2), (0,2)], l_shape)
True

如果您想将测试形状与所有预定义形状进行比较，您可能希望仅计算一次测试形状的角度序列。如果您要测试许多形状与预定义形状相比，您可能希望预先计算预定义形状的序列。对于这些优化，我会留给读者自己去实践。

- rob mayoff

---

天啊！我没想到会这样。我正在计算“角度系列”（https://dev59.com/XWYs5IYBdhLWcg3wAfEi），但在“for循环”中遇到了困难，因为我对Python不是很熟悉。非常感谢。 - ZK Zhao

Answer 2

您的形状不仅可以旋转，还可以平移并且甚至可以缩放。节点的方向也可能不同。例如，原始的正方形边长为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):
        # compare radii
        if abs(aa[0] - bb[0]) > eps:
            return False

        # compare angles
        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"""

    # Only consider shapes with same number of points
    if len(a) != len(b) or len(a) < 3:
        return False        

    # find centre of gravity
    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)]

    # convert Cartesian coords into radial coords
    ar = [radial(x, y, ax, ay) for x, y in a]
    br = [radial(x, y, bx, by) for x, y in b]

    # find maximum radius
    amax = max([r for r, phi in ar])
    bmax = max([r for r, phi in br])

    # and normalise the coordinates with it
    ar = [(r / amax, phi) for r, phi in ar]
    br = [(r / bmax, phi) for r, phi in br]

    # ensure both shapes are anticlockwise
    anticlockwise(ar)
    anticlockwise(br)

    # now match radius and angle difference in n cionfigurations
    n = len(a)
    while n:
        if similar_r(ar, br):
            return True                

        br.append(br.pop(0))      # rotate br by one
        n -= 1

    return False

编辑：虽然这个解决方案可行，但过于复杂。罗布的答案本质上相似，但使用了一种简单的度量方法：边缘之间的内部角度，它可以自动处理平移和缩放。

- M Oehm

Answer 3

通过线性代数的方法，每个点都可以表示为一个向量(x,y)，可以将其乘以旋转矩阵，得到指定角度下的新坐标(x1,y1)。这里似乎没有LaTeX支持，所以我无法清楚地写出来，但本质上是这样：

(cos(a) -sin(a);sin(a) cos(a))*(x y) = (x1 y1)

这将导致坐标 x1，y1 按角度“a”旋转。

编辑：这可能是基础理论，但您可以设置算法逐点移动形状到（0,0），然后计算相邻点之间的余弦值来分类对象。

- Topher

---

但是你不知道角度a的任何信息，所以你是在尝试通过所有可能的角度来进行暴力破解吗？ - ZdaR

我相信他的意思是你可以解决系统 RM * A = B，其中 RM 是一个旋转矩阵。如果你能够解决这个系统，也就是找到 RM，那么你可以说 A 和 B 是相似的。如果解决方案不存在，那么这些对象就不相似。 - Eli Korvigo

@anmol_uppal，您根本不需要猜测，您可以从集合中相邻的坐标测试不同的可能角度。通过将整个点集移动到感兴趣的点处于(0,0)位置，然后获取两个相邻点的点积除以它们长度的乘积得到角度的余弦值。这将告诉您方向的相对变化，通过比较和逐步推断形状，您可以使用算法来进行。 - Topher

可以实现一个更加高效的算法，具体步骤如下：从集合A中取出一条边(a)，从集合B中取出一条边(b)，解方程RM*a = b。如果存在解，则可以将得到的RM应用于形状的其余部分。然后只需检查A中的任何一条边是否存在与之平行的边在B中即可。 - Eli Korvigo

@EliKorvigo，没错！没有LaTeX支持，手写是很麻烦的。你需要解决这个问题的方法就是采用系统化的方法来移动集合、获取角度，然后对下一个进行操作，并相应地进行分类。 - Topher