如何用Python标准库按公共顶点分组线段以识别闭合环？

一、按共享顶点分组线段 #

要把共享任意顶点的线段归为同一组，本质是找线段的连通分量：通过顶点作为关联节点，用DFS/BFS遍历所有相连的线段即可完成分组。

实现步骤 #

1. 构建顶点到线段ID的映射，记录每个顶点属于哪些线段；
2. 用DFS遍历所有线段，把通过顶点相连的线段归为同一组。

代码实现 #

lines = {
    "A": [(0, 0), (0, 1)],
    "B": [(0, 1), (1, 1)],
    "C": [(1, 1), (1, 0)],
    "D": [(1, 0), (0, 0)],
    "E": [(4, 4), (4, 5)],
    "F": [(4, 5), (5, 5)],
    "G": [(5, 5), (4, 4)],
}

# 1. 建立顶点到线段ID的映射
vertex_to_lines = {}
for line_id, (v1, v2) in lines.items():
    # 处理第一个顶点
    if v1 not in vertex_to_lines:
        vertex_to_lines[v1] = set()
    vertex_to_lines[v1].add(line_id)
    # 处理第二个顶点
    if v2 not in vertex_to_lines:
        vertex_to_lines[v2] = set()
    vertex_to_lines[v2].add(line_id)

# 2. DFS遍历分组连通线段
visited_lines = set()
groups = []

for line_id in lines:
    if line_id not in visited_lines:
        stack = [line_id]
        current_group = []
        while stack:
            current_line = stack.pop()
            if current_line in visited_lines:
                continue
            visited_lines.add(current_line)
            current_group.append(current_line)
            # 获取当前线段的两个顶点，把关联的未访问线段加入栈
            v1, v2 = lines[current_line]
            for related_line in vertex_to_lines[v1]:
                if related_line not in visited_lines:
                    stack.append(related_line)
            for related_line in vertex_to_lines[v2]:
                if related_line not in visited_lines:
                    stack.append(related_line)
        groups.append(current_group)

print("分组结果：", groups)  # 输出: [['A', 'B', 'C', 'D'], ['E', 'F', 'G']]

二、将分组线段排序为闭合环 #

分组完成后，沿着顶点依次连接线段，即可形成闭合环；若需要顺时针顺序，可通过多边形面积符号调整方向。

实现思路 #

1. 从组内任意线段出发，记录当前顶点，寻找下一个包含该顶点的未使用线段；
2. 更新当前顶点为线段的另一个端点，循环直到回到起始顶点；
3. 可选：用Shoelace公式计算多边形有向面积，判断方向并调整为顺时针。

代码实现 #

def sort_group_to_cycle(group, lines):
    if not group:
        return ""
    # 初始化，取第一条线段作为起点
    start_line = group[0]
    v_start, v_current = lines[start_line]
    used_lines = {start_line}
    cycle = [start_line]
    
    while len(used_lines) < len(group):
        # 寻找包含当前顶点的未使用线段
        for line_id in group:
            if line_id in used_lines:
                continue
            v1, v2 = lines[line_id]
            if v1 == v_current:
                v_current = v2
                used_lines.add(line_id)
                cycle.append(line_id)
                break
            elif v2 == v_current:
                v_current = v1
                used_lines.add(line_id)
                cycle.append(line_id)
                break
    # 验证是否闭合
    assert v_current == v_start, "组内线段未形成闭合环"
    return "".join(cycle)

# 生成闭合环结果
answer = [sort_group_to_cycle(group, lines) for group in groups]
print("闭合环结果：", answer)  # 输出: ['ABCD', 'EFG']

补充：调整为顺时针顺序 #

def is_clockwise(cycle, lines):
    # 提取环的顶点序列
    vertices = []
    v_prev = None
    for line_id in cycle:
        v1, v2 = lines[line_id]
        if v_prev is None:
            vertices.append(v1)
            vertices.append(v2)
            v_prev = v2
        else:
            vertices.append(v2 if v1 == v_prev else v1)
            v_prev = vertices[-1]
    # 移除重复的起始顶点
    vertices = vertices[:-1]
    # Shoelace公式计算有向面积
    area = 0.0
    n = len(vertices)
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i+1)%n]
        area += (x1 * y2) - (x2 * y1)
    # 面积为负表示顺时针（y轴向上坐标系）
    return area < 0

def sort_group_to_clockwise_cycle(group, lines):
    cycle = sort_group_to_cycle(group, lines)
    if not is_clockwise(cycle, lines):
        cycle = cycle[::-1]
    return cycle

# 生成顺时针闭合环
answer_clockwise = [sort_group_to_clockwise_cycle(group, lines) for group in groups]
print("顺时针闭合环：", answer_clockwise)

说明 #

• 所有代码仅依赖Python标准库，无需额外安装包；
• 先分组再处理环的方式，避免了跨组寻找循环导致的冗余结果；
• 顺时针判断逻辑可根据实际坐标系（如y轴向下）调整面积符号判断条件。

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