如何从线段数组中识别闭合图形并获取其坐标与数量？

我有一个元组列表，每个元组包含构成线段的坐标点（格式如(x, y, x1, y1,...)），所有线段共同组成一幅图形，其中存在5个闭合对象。需要获取这些闭合对象的数量及其坐标。

坐标列表：

Coordinates_list = [(939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005), (939, 1002, 939, 900), (939, 900, 961, 916), (961, 916, 1031, 898), (1031, 898, 1080, 906), (1080, 906, 1190, 896), (1190, 896, 1225, 897), (1223, 1005, 1225, 897), (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)]

我尝试用DFS算法解决，但返回的闭合对象数量总是少于实际数量，原代码如下：

def find_closed_figures(lines):
    def dfs(line_idx, visited):
        visited.add(line_idx)
        for neighbor_idx, line in enumerate(lines):
            if neighbor_idx not in visited and lines[line_idx][3:6] == line[0:3]:
                dfs(neighbor_idx, visited)

    closed_figures_count = 0
    visited_lines = set()
    for idx, line in enumerate(lines):
        if idx not in visited_lines:
            dfs(idx, visited_lines)
            closed_figures_count += 1

    return closed_figures_count

coordinates_list = [(939, 1002, 0, 984, 993, 0), (984, 993, 0, 998, 1001, 0), (998, 1001, 0, 1043, 995, 0), (1043, 995, 0, 1080, 1004, 0), (1080, 1004, 0, 1106, 994, 0), (1106, 994, 0, 1147, 1003, 0), (1147, 1003, 0, 1182, 995, 0), (1182, 995, 0, 1223, 1005, 0), (939, 1002, 0, 939, 900, 0), (939, 900, 0, 961, 916, 0), (961, 916, 0, 1031, 898, 0), (1031, 898, 0, 1080, 906, 0), (1080, 906, 0, 1190, 896, 0), (1190, 896, 0, 1225, 897, 0), (1223, 1005, 0, 1225, 897, 0), (939, 1002, 0, 1031, 898, 0), (1031, 898, 0, 1106, 994, 0), (1106, 994, 0, 1190, 896, 0), (1190, 896, 0, 1182, 995, 0)]


closed_figures_count = find_closed_figures(coordinates_list)
print(closed_figures_count)

1. 坐标处理错误：原代码给坐标添加了多余的0，且判断线段连接时用lines[line_idx][3:6] == line[0:3]，完全不符合线段端点匹配逻辑——线段连接应该是前一条的终点等于后一条的起点（或反向，因为线段无向）。
2. DFS逻辑偏差：原DFS仅遍历连通的线段集合，但连通集合不一定是闭合环，也未检测是否形成闭合路径。
3. 未拆分多段线：输入元组存在包含多个连续线段的情况（比如第一个元组是一串连续点），原代码直接将整个元组当作一条线段处理，导致线段关系完全错误。

核心思路 #

1. 拆分所有多段线为单个线段；
2. 以坐标点为节点构建无向图；
3. 用DFS遍历图，寻找所有唯一的闭合环（避免重复统计正反方向的同一个环）。

完整代码 #

def split_lines(coords_list):
    """拆分多段线为单个线段，每个线段为(起点坐标, 终点坐标)"""
    lines = []
    for coords in coords_list:
        # 将元组按每两个元素一组拆分为坐标点
        points = [(coords[i], coords[i+1]) for i in range(0, len(coords), 2)]
        # 生成连续点之间的线段
        for i in range(len(points)-1):
            start = points[i]
            end = points[i+1]
            lines.append((start, end))
    return lines

def build_graph(lines):
    """构建无向图：key为坐标点，value为该点的所有相邻点列表"""
    graph = {}
    for start, end in lines:
        if start not in graph:
            graph[start] = []
        graph[start].append(end)
        if end not in graph:
            graph[end] = []
        graph[end].append(start)
    return graph

def find_closed_loops(graph):
    """寻找所有唯一的闭合环，避免重复统计正反方向的同一个环"""
    visited_nodes = set()
    loops = []
    
    def dfs(current, path, visited_edges):
        # 路径长度≥3且回到起点，说明找到闭合环
        if len(path) >= 3 and current == path[0]:
            # 标准化环：以路径中最小的坐标点为起点，消除正反方向的重复
            min_point = min(path)
            min_idx = path.index(min_point)
            normalized_loop = path[min_idx:] + path[1:min_idx+1]
            reversed_loop = normalized_loop[::-1]
            # 避免重复添加相同的环
            if normalized_loop not in loops and reversed_loop not in loops:
                loops.append(normalized_loop)
            return
        
        for neighbor in graph.get(current, []):
            # 用排序后的点元组标记已访问的边，避免重复走同一条边
            edge = tuple(sorted((current, neighbor)))
            if edge not in visited_edges:
                visited_edges.add(edge)
                dfs(neighbor, path + [neighbor], visited_edges)
                visited_edges.remove(edge)
    
    # 遍历所有未访问的节点，寻找环
    for node in graph:
        if node not in visited_nodes:
            dfs(node, [node], set())
            # 标记已找到的环中所有节点为已访问，避免重复处理
            for loop in loops:
                visited_nodes.update(loop)
    
    return loops

# 处理输入数据
coordinates_list = [(939, 1002, 984, 993, 998, 1001, 1043, 995, 1080, 1004, 1106, 994, 1147, 1003, 1182, 995, 1223, 1005), (939, 1002, 939, 900), (939, 900, 961, 916), (961, 916, 1031, 898), (1031, 898, 1080, 906), (1080, 906, 1190, 896), (1190, 896, 1225, 897), (1223, 1005, 1225, 897), (939, 1002, 1031, 898, 1106, 994, 1190, 896, 1182, 995)]

# 拆分线段
lines = split_lines(coordinates_list)
# 构建无向图
graph = build_graph(lines)
# 寻找所有闭合环
closed_loops = find_closed_loops(graph)

# 输出结果
print(f"闭合对象数量：{len(closed_loops)}")
print("各个闭合对象的坐标：")
for idx, loop in enumerate(closed_loops, 1):
    print(f"第{idx}个闭合环：{loop}")

代码说明 #

1. split_lines：将输入中包含多个点的元组拆分为两两连续的线段，确保每个线段都是独立的两点连接。
2. build_graph：构建无向图结构，方便后续遍历每个点的相邻节点。
3. find_closed_loops：通过DFS遍历图，找到所有闭合环，并通过标准化环的起点（以路径中最小坐标点为开头）避免重复统计同一个环的正反方向。

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