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

Question

给定一组 points (with order)，我想知道它的形状是否在某些类型内。类型是：

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。

类似于

通知：

rotation 和带 different length 的边被认为是相似的。
输入点为ordered。（所以它们可以在 polygon 模块中由 path 绘制）

我该怎么做？有什么算法吗？

我在想什么：

也许我们可以从给定的 points 重构 lines。而从lines，我们可以得到angles的一个形状。通过比较angle series（顺时针和逆时针），我们可以确定输入点是否与上面给出的类型相似。

Answer 1

用线性代数来解决这个问题，每个点都是一个向量(x,y)，可以乘以rotation matrix得到指定角度的新坐标(x1,y1)。这里好像没有LaTeX的支持所以没写清楚，但本质上：

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

这会导致坐标 x1、y1 旋转角度 "a"。

编辑：这可能是基本理论，但您可以设置一种算法将形状逐点移动到 (0,0)，然后计算相邻点之间角度的余弦以对形状进行分类对象。

Answer 2

你的思路基本上是对的。您想要将测试形状中的角度序列与预定义形状中的角度序列进行比较（对于每个预定义形状）。由于测试形状的第一个顶点可能不对应于匹配的预定义形状的第一个顶点，因此我们需要允许测试形状的角度序列可以相对于预定义形状的序列旋转。（也就是说，您的测试形状的顺序可能是 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.)

但是，我认为浮点舍入可能会导致我们为测试形状与预定义形状选择不同的规范旋转。因此，我们将只检查所有旋转。

首先，returns 一个形状的角度序列的函数：

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

如果您想将测试形状与所有预定义形状进行比较，您可能只想计算一次测试形状的角度序列。如果您要针对预定义形状测试许多形状，您可能希望只预先计算预定义形状的序列一次。我将这些优化留作 reader.

的练习

Answer 3

您的形状不仅可以旋转，还可以平移，甚至可以缩放。节点的方向也可能不同。例如，您原来的正方形的边长为 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

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

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

Python & Algorithm: How to do simple geometry shape match?

python

algorithm

geometry