python-3.x - 多边形三角剖分算法

Question

我编写了以下代码来生成正多边形或凸多边形的所有“三角剖分”:

def getTriangles(points,i,j):
    print('i={}, j={}'.format(i,j))
    ee = []
    if j-i<2:
        return []
    if j-i==2:
        return [[[i,i+1,j]]]
    for k in range(i+1,j):
        print('    k={}'.format(k))
        e1= getTriangles(points,i,k)
        e2 = getTriangles(points,k,j)
        for x in e1:
            for y in e2:
                e = [[i,k,j]]
                e.extend(x)
                e.extend(y)
                ee.append(e)
        if len(e1)==0:
            for y in e2:
                e = [[i,k,j]]
                e.extend(y)
                ee.append(e)
        if len(e2)==0:
            for a in e1:
                e = [[i,k,j]]
                e.extend(x)
                ee.append(e)
        print('        e1={}, e2={}, ee={}'.format(e1,e2,ee))
    return ee

n=5
tr = getTriangles(range(1,n+1),0,n-1)
print()
print(tr)
print(len(tr))

对于 n=3,4 它是正确的，并且对于 n=3,4,5,6,7,8 通常“导航”通过正确数量的可能三角剖分(即加泰罗尼亚数)，但是三角剖分不是唯一的。这里是 n=5 的格式化输出，由三角形列表组成(例如 [0,1,2,3,4] 中的三个顶点):

[[[0, 1, 4], [1, 2, 4], [2, 3, 4]],
 [[0, 1, 4], [1, 3, 4], [1, 2, 3]],
 [[0, 2, 4], [0, 1, 2], [2, 3, 4]],
 [[0, 3, 4], [0, 2, 3], [0, 1, 2]], 
 [[0, 3, 4], [0, 2, 3], [0, 1, 2]]]

如您所见，最后两个是相等的。错误在哪里？直觉上代码比需要的更复杂。

编辑 如您所见，我并没有因为这个错误而陷入困境:这里是普林斯顿大学计算机科学教授 Robert Sedgewick，在背景中您会看到 n=5 是正确但对于 n=6 有双 ;-)

Answer 1

以下代码接缝工作。变化在中间。该算法固定边 [i,j] 并且 k 从 i+1 移动到 j-1。固定三角形 ijk 并将多边形分成三个子多边形:它本身、多边形 i...k 和多边形 k..j。如果k=i+1或k=j-1，则两个多边形之一退化(空):

def getTriangles(points,i,j):
    print('i={}, j={}'.format(i,j))
    ee = []
    if j-i<2:
        return []
    if j-i==2:
        return [[[i,i+1,j]]]
    for k in range(i+1,j): # k is the vertex such that the triangle ikj split the polygon 1j in 2 subspace plus the triangle ikj
        print('    k={}'.format(k))
        e1= getTriangles(points,i,k)
        e2 = getTriangles(points,k,j)
        if k==i+1:
            for y in e2:
                e = [[i,k,j]]
                e.extend(y)
                ee.append(e)
        elif k==j-+1:
            for x in e1:
                e = [[i,k,j]]
                e.extend(x)
                ee.append(e)
        else:
            for x in e1:
                for y in e2:
                    e = [[i,k,j]]
                    e.extend(x)
                    e.extend(y)
                    ee.append(e)
        print('        e1={}, e2={}, ee={}'.format(e1,e2,ee))
    return ee

n=5
tr = getTriangles(range(1,n+1),0,n-1)
print()
print(tr)
print(len(tr))