将三角形及矩形面片列表转换为带孔洞的闭合实体多边形的算法需求

针对你提出的需求——把三角面片集合转换成符合matplotlib PathPatch要求的外部轮廓、孔洞（含不连通场景），我整理了一套基于边统计和环遍历的算法，完全贴合你的前提假设和需求细节：

核心思路 #

因为你的面片满足互不重叠、仅共享完整边的前提，所以有一个关键规律：

• 内部边（被两个面片共享）会在所有面片的边中出现恰好2次
• 边界边（属于外部轮廓或孔洞）只会出现1次

我们可以利用这个规律，先筛选出所有边界边，再把这些边连成闭合环，最后区分环的类型（外部/孔洞）、调整方向并关联归属。

详细步骤 #

1. 提取并统计所有边的出现次数

首先遍历每个三角面片，生成它的三条边。为了避免同一条边的正反方向被当作不同边，我们统一边的表示：把边的两个顶点按坐标排序（比如先比较x坐标，x相同则比较y坐标），转换成tuple（因为列表不能作为字典键）后存入统计字典。

统计完成后，只保留出现次数为1的边——这些就是我们需要的边界边。

2. 构建边界边的邻接图并遍历生成闭合环

用一个邻接表记录每个顶点的相邻顶点（来自边界边）。然后从任意一条未访问的边界边出发，沿着邻接顶点遍历，每次标记走过的边（包括正反方向），直到回到起点，这样就得到一个闭合的顶点环。

重复这个过程，直到所有边界边都被处理，得到所有闭合环。

3. 判断环的类型并调整方向

接下来要区分每个环是外部轮廓还是孔洞，同时调整为符合要求的方向：

• 方向判断：用鞋带公式计算环的有向面积——面积为正表示环是逆时针方向，面积为负是顺时针方向。
• 类型区分：用射线法判断环的顶点是否被其他环包含：
  • 如果一个环不被任何其他环包含，它就是外部轮廓，需要调整为顺时针方向（如果当前是逆时针，就反转顶点顺序）。
  • 如果一个环被某个外部轮廓包含，它就是孔洞，需要调整为逆时针方向（如果当前是顺时针，就反转顶点顺序）。

4. 关联孔洞与所属外部多边形

对于每个孔洞，找到包含它的最内层外部轮廓（避免嵌套外部轮廓的干扰），把孔洞和对应的外部轮廓关联起来。如果是和外部轮廓仅通过孤立点接触的孔洞，射线法依然能正确判断它属于该外部轮廓。

5. 处理不连通多边形

所有不被其他环包含的外部轮廓，都是独立的不连通多边形，各自作为单独的条目返回，每个条目包含自身的外部顶点列表和关联的孔洞列表。

伪代码实现 #

def extract_boundaries(facet_list):
    # 步骤1：提取并统计边的出现次数
    edge_count = {}
    for facet in facet_list:
        # 生成当前面片的三条边，统一表示为排序后的顶点元组
        edges = []
        for i in range(3):
            v1 = facet[i]
            v2 = facet[(i+1)%3]
            # 按坐标排序，确保边的表示唯一
            if (v1[0], v1[1]) < (v2[0], v2[1]):
                edge = (tuple(v1), tuple(v2))
            else:
                edge = (tuple(v2), tuple(v1))
            edges.append(edge)
        for edge in edges:
            edge_count[edge] = edge_count.get(edge, 0) + 1
    
    # 筛选边界边（仅出现1次）
    boundary_edges = [edge for edge, cnt in edge_count.items() if cnt == 1]
    
    # 步骤2：构建邻接表并遍历生成闭合环
    adj = {}
    for u, v in boundary_edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    
    visited_edges = set()
    rings = []
    for edge in boundary_edges:
        if edge in visited_edges:
            continue
        # 初始化环的遍历
        current, next_v = edge
        ring = [list(current)]
        visited_edges.add(edge)
        visited_edges.add((next_v, current))  # 标记反向边已访问
        
        while next_v != edge[0]:
            ring.append(list(next_v))
            # 找到下一个未访问的邻接顶点
            for neighbor in adj[next_v]:
                current_edge = (next_v, neighbor)
                if current_edge not in visited_edges:
                    visited_edges.add(current_edge)
                    visited_edges.add((neighbor, next_v))
                    next_v = neighbor
                    break
        rings.append(ring)
    
    # 步骤3：判断环类型并调整方向
    def shoelace_area(polygon):
        # 计算有向面积：正=逆时针，负=顺时针
        n = len(polygon)
        area = 0.0
        for i in range(n):
            x1, y1 = polygon[i]
            x2, y2 = polygon[(i+1)%n]
            area += (x1 * y2) - (x2 * y1)
        return area / 2.0
    
    def point_in_polygon(point, polygon):
        # 射线法判断点是否在多边形内部（处理孤立点接触场景）
        x, y = point
        inside = False
        n = len(polygon)
        for i in range(n):
            xi, yi = polygon[i]
            xj, yj = polygon[(i+1)%n]
            # 检查点是否在边上（仅可能是孤立点接触）
            if ((yi > y) != (yj > y)) and (x < (xj - xi) * (y - yi) / (yj - yi) + xi):
                inside = not inside
        return inside
    
    # 分离外部轮廓和孔洞
    outer_rings = []
    hole_rings = []
    for ring in rings:
        is_outer = True
        # 检查当前环是否被其他环包含
        for other_ring in rings:
            if ring == other_ring:
                continue
            if point_in_polygon(ring[0], other_ring):
                is_outer = False
                break
        # 调整方向
        area = shoelace_area(ring)
        if is_outer:
            # 外部轮廓需要顺时针（面积为负）
            if area > 0:
                ring.reverse()
            outer_rings.append(ring)
        else:
            # 孔洞需要逆时针（面积为正）
            if area < 0:
                ring.reverse()
            hole_rings.append(ring)
    
    # 步骤4：关联孔洞到所属外部多边形
    result = []
    for outer in outer_rings:
        associated_holes = []
        for hole in hole_rings:
            # 检查孔洞是否属于当前外部轮廓（且不被更外层的外部轮廓包含）
            if point_in_polygon(hole[0], outer):
                belongs_to_this = True
                for other_outer in outer_rings:
                    if outer == other_outer:
                        continue
                    if point_in_polygon(hole[0], other_outer) and point_in_polygon(outer[0], other_outer):
                        belongs_to_this = False
                        break
                if belongs_to_this:
                    associated_holes.append(hole)
        result.append({
            "outer_contour": outer,
            "holes": associated_holes
        })
    
    return result

符合需求的验证 #

• 内部面片处理：内部面片的所有边都会被两个面片共享，会被过滤掉，不会出现在最终轮廓中。
• 孔洞支持：孔洞会被正确识别，调整为逆时针方向，并关联到所属的外部轮廓。
• 不连通多边形：每个独立的外部轮廓会作为单独的条目返回，互不干扰。
• 边缘场景：对于仅通过孤立点接触的孔洞，射线法会正确判断其归属，不会被误判为外部轮廓。

内容的提问来源于stack exchange，提问作者Jagerber48