如何在Python中从边列表生成面列表？计算几何技术求助

核心思路（针对流形网格） #

主流几何场景中，每条边最多属于两个闭合面，基于这个前提，通过邻接表+哈希边映射的方式可以实现线性时间复杂度的面生成，完全避免双重循环的低效问题。

步骤1：边的标准化与映射 #

将每条边转换为无序标准化形式（比如按顶点ID从小到大排序的元组），用哈希表存储每条边的状态（是否已被使用），确保[p1,p2]和[p2,p1]被视为同一条边，查询和标记状态的时间复杂度为O(1)。

步骤2：构建顶点邻接表 #

为每个顶点建立相邻顶点的列表，快速获取从任意顶点出发的所有关联边，构建时间复杂度O(n)（n为边数）。可选对邻接表按极角排序，保证生成的面顶点按顺时针/逆时针有序排列。

步骤3：遍历生成闭合面 #

1. 初始化未使用边集合，循环取出未使用边作为面的起始边；
2. 从起始边的第二个顶点出发，在邻接表中寻找下一个未使用且非回头的边，标记为已使用并加入当前面；
3. 重复直到回到起始顶点，形成闭合面，加入面列表；
4. 直到所有边被处理完毕。

代码实现示例（Python） #

# 假设顶点对象包含唯一id、x/y/z坐标属性
class Vertex:
    def __init__(self, vid, x, y, z):
        self.id = vid
        self.x = x
        self.y = y
        self.z = z

# 示例顶点
p1 = Vertex(1, 0, 0, 0)
p2 = Vertex(2, 1, 0, 0)
p3 = Vertex(3, 0, 1, 0)
p4 = Vertex(4, 1, 1, 0)
edges = [[p1, p2], [p1, p3], [p2, p3], [p2, p4], [p3, p4]]

# 1. 构建边映射（标准化+使用状态）
edge_map = {}
for v1, v2 in edges:
    key = tuple(sorted([v1.id, v2.id]))
    if key not in edge_map:
        edge_map[key] = {'vertices': (v1, v2), 'used': False}

# 2. 构建邻接表并按极角排序（保证面顶点顺序）
import math

def sort_by_polar_angle(center, neighbors):
    """按相对于center的逆时针极角排序邻居顶点"""
    def polar_angle(v):
        dx = v.x - center.x
        dy = v.y - center.y
        return math.atan2(dy, dx)
    return sorted(neighbors, key=lambda x: polar_angle(x))

adj = {}
for v1, v2 in edges:
    adj.setdefault(v1, []).append(v2)
    adj.setdefault(v2, []).append(v1)
for v in adj:
    adj[v] = sort_by_polar_angle(v, adj[v])

# 3. 遍历生成闭合面
faces = []
unused_edges = set(edge_map.keys())

while unused_edges:
    start_key = next(iter(unused_edges))
    v_start, v_prev = edge_map[start_key]['vertices']
    current_face = [v_start, v_prev]
    current_v = v_prev
    
    # 标记起始边为已使用
    edge_map[start_key]['used'] = True
    unused_edges.remove(start_key)
    
    # 构建闭合环
    while current_v != v_start:
        for v_next in adj[current_v]:
            edge_key = tuple(sorted([current_v.id, v_next.id]))
            if not edge_map[edge_key]['used'] and v_next != v_prev:
                edge_map[edge_key]['used'] = True
                unused_edges.remove(edge_key)
                current_face.append(v_next)
                v_prev, current_v = current_v, v_next
                break
    faces.append(current_face)

# 输出面的顶点ID
for idx, face in enumerate(faces):
    print(f"面{idx+1}: {[v.id for v in face]}")

复杂度说明 #

• 预处理（边映射+邻接表）：O(n)，n为边数；
• 面生成过程：每条边仅被处理一次，整体时间复杂度O(n)，适合大规模边列表处理。

特殊情况处理 #

• 非流形边：若存在一条边属于超过两个面，需在邻接表遍历中添加额外逻辑（比如按法向方向选择下一个顶点）；
• 开放网格：若存在仅属于一个面的边界边，遍历到边界时会无法形成闭合环，需根据需求跳过或单独处理这类边。

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