Python 和算法 : How to do simple geometry shape match?

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. 旋转和不同长度的边被认为是相似的。
2. 输入点是有序的。 (所以它们可以通过 polygon 模块中的 path 绘制)

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

我在想什么:

也许我们可以根据给定的点重建线。从线，我们可以得到一个形状的角度。通过比较角度系列(顺时针和逆时针)，我们可以确定输入点是否与上面给出的类型相似。

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

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