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上述.

类似于

注意:

1. rotation和边缘different length被认为是相似的.
2. 输入点是ordered.(所以他们可以path在polygon模块中绘制)

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

我在想什么:

也许我们可以lines从给定的重建points.从中lines,我们可以得到angles一个形状.通过比较angle series(顺时针和逆时针),我们可以确定输入点是否与上面给出的类型相似.

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

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