将三角形和矩形面列表转换为实心多边形？

我知道你称它们为分面，但这个词对我来说太过分了。我称它们为三角形。

第一步，确保所有三角形的方向相同。这里有一些简单的代码。

def dot (vector1, vector2):
    return vector1[0] * vector2[0] + vector1[1] * vector2[1]

def vector_from_points (point1, point2):
    return [point2[0] - point1[0], point2[1] - point1[1]]

def rotate_vector_90 (vector):
    return [-vector[1], vector[0]]

def oriented_triangle (triangle):
    vector1 = vector_from_points(triangle[0], triangle[1])
    vector2 = vector_from_points(triangle[1], triangle[2])
    normal = rotate_vector_90(vector1)
    if 0 < dot(normal, vector2):
        return triangle
    else:
        return [triangle[0], triangle[2], triangle[1]]

现在，如果两个三角形共享一条边，则保证一个三角形是形式，另一个是形式。[a, b][b, a]

因此，我们可以按如下方式加载字典：

triangle_position = {}
for triangle in triangles:
    for i in range(3):
        triangle_position[tuple(triangle[i])] = (triangle, i)

现在我们可以遍历所有的边缘。如果它是内部边缘，我们会忽略它。如果它是外边，我们可以在它所来自的三角形中找到下一条边。虽然这不是外边，但我们可以找到具有反边的三角形并移动到 ITS 的下一条边。最终，我们到达了下一个外部边缘。这让我们可以在外部走动。

我可以保证形状的外侧是逆时针方向，形状内的孔是顺时针方向。不过，我不能保证孔与形状的顺序会是什么 - 你可能需要自己弄清楚。我建议使用光线追踪算法。

我不会解决奖金问题。

假设所有三角形的点都以相同的循环方向（全部顺时针或全部逆时针）给出，您可以执行以下操作：

1. 收集所有边，只保留那些没有被反边抵消的边缘（所以 [a， b] 被 [b， a] 删除）。这样，您最终会得到应该属于多边形的边。剩余的边描述了一个或多个与三角形具有相同循环方向的多边形，以及零个或多个具有相反方向的孔。

2. 为步骤 1 的边缘创建邻接列表。

3. 只要存在未访问的边，请选择一条未访问的边，将其从邻接列表中移除，使用该边的起始顶点开始一个新多边形，然后重复以下步骤以使用更多顶点填充多边形：

   • 将 Edge 标记为已访问
   • 如果结束顶点在邻接列表中没有传出边，则退出此环路
   • 将结束顶点追加到多边形
   • 从邻接列表中提取相邻顶点（并将其从中删除）
   • 从拳头项目符号点开始，用这个相邻的边缘重复。

4. 将此多边形添加到多边形列表中

5. 从步骤 3 开始重复，直到所有边都标记为已访问。

下面是执行此操作的代码：

def triangles_to_polygons(triangles):
    # Collect those edges that are not negated by an opposite edge
    edges = set()
    for triangle in triangles:
        a, b, c = map(tuple, triangle)
        for start, end in (a, b), (b, c), (c, a):
            if (end, start) in edges:
                edges.remove((end, start))
            else:
                edges.add((start, end))
    # Create an adjacency list
    adj = {}
    for a, b in edges:
        adj.setdefault(a, []).append(b)
    
    # Populate polygons
    polygons = []
    visited = set()
    for edge in edges:
        if edge not in visited:
            a, b = edge
            adj[a].remove(b)
            polygon = [a]
            while True:
                visited.add((a, b))
                if not adj[b]:
                    break
                polygon.append(b)
                a, b = b, adj[b].pop()
            polygons.append(polygon)
    return polygons

运行示例：

triangles = [[[0, 0], [1, 0], [1, 1]],
             [[0, 0], [1, 1], [0, 1]],
             [[1, 0], [2, 0], [2, 1]],
             [[1, 0], [2, 1], [1, 1]],
             [[1, 1], [2, 1], [2, 2]],
             [[1, 1], [2, 2], [1, 2]]]
polygons = triangles_to_polygons(triangles)
print(polygons)