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

Question

我有一个 2D 几何体，它由多个面指定，其中每个面都是由 3 个顶点坐标指定的三角形，如 facet = [[0, 0], [1, 0], [1, 1 ]]。

我可以通过将每个面转换为Polygon补丁并绘制这些补丁来在matplotlib中绘制它们。但是，我想要一种算法，可以获取我的面列表并将其转换为所有外部顶点的单个闭合多边形路径。

例如假设我有

facet_list = [[[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]]]

solid_vertex_list = [[0, 0],
                     [1, 0],
                     [2, 0],
                     [2, 1],
                     [2, 2],
                     [1, 2],
                     [1, 1],
                     [0, 1]]

第一个数据集是面列表，第二个数据集是外部顶点的目标列表。请参阅下面这两个数据集的可视化:

我寻求一种将第一个数据集转换为第二个数据集的算法。此特定示例未捕获一些功能，但算法需要这些功能。

(1) 在此示例中，所有顶点都是外部顶点，但通常可能存在完全位于所得“大”多边形内部的面。

(2) 一般来说，“大”多边形中可能有孔。我不确定如何最好地处理这个问题，但根据 this matplotlib documentation ，如果您以相反的顺序给出孔的顶点，则看起来 matplotlib PathPatch 对象可以在多边形中绘制孔。因此，对于该算法来说，如果任何“洞”的顶点路径简单地以相反的顺序报告为单独的多边形就足够了。

(3) 小面可以形成不连续的多边形。在这种情况下，应该返回单独的顶点列表，指示单独的多边形。如果两个多边形仅由单个顶点或更少的顶点连接，则它们被视为断开连接。

我认为以上三点是facets -> Polygon(s) (withhole(s))算法的要求。总的来说，我认为该算法将返回一个顶点列表列表，其中如果顶点列表对应于断开的外部多边形，则顺时针列出顶点列表；如果对应于孔，则逆时针列出顶点列表。也许需要有一些东西来指示哪个孔对应于哪个外部多边形。一种棘手的边缘情况可能是:如何处理具有一个或多个外部顶点的孔。即当一个孔在一个或多个孤立点接触外部时。

出于该算法的目的，我们可以假设小平面与其他小平面共享节点，以便 (1) 小平面不重叠，即任何小平面的节点都不在另一个小平面内，并且 (2) 小平面仅共享完整的边，即一个面的任何节点都不位于另一面的边缘的中间位置。另一个问题的主题是如何获取不满足(1)和(2)的数据，并通过添加更多面来分解交叉点和中边缘节点来对其进行清理。

Answer 1

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

1. 收集所有边，只保留那些不与相反边相对的边(因此 [a, b] 被 [b, a] 删除)。这样你最终会得到应该属于多边形的边。剩余的边描述了一个或多个与三角形具有相同循环方向的多边形，以及零个或多个具有相反方向的孔。

2. 为第 1 步的边创建邻接表。

3. 只要存在未访问过的边，就选择一条未访问过的边，将其从邻接列表中删除，以该边的起始顶点开始一个新的多边形，并重复以下步骤来填充具有更多顶点的多边形:

   • 将边缘标记为已访问
   • 如果结束顶点在邻接列表中没有出边，则退出本次循环
   • 将结束顶点附加到多边形
   • 从邻接列表中提取相邻顶点(并将其从中删除)
   • 从第一个项目符号点开始，使用该相邻边缘重复此操作。

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)