如何用深度优先搜索移除Shapely MultiLineString分支并计算主线路长度

核心思路 #

主线是连通的且两端为度数1的端点（仅连接一条线段），分支是从主线延伸出的次级线段。通过构建端点邻接表+深度优先搜索（DFS），可以精准筛选出主线线段，再合并计算总长度。

步骤1：拆分线段并收集端点 #

先将MultiLineString拆分为单个LineString，同时提取每条线段的起点和终点，注意用equals_exact处理浮点精度问题，避免点匹配错误。

from shapely.geometry import MultiLineString, LineString, Point

# 替换为你的MultiLineString对象
mls = MultiLineString([
    [(0,0), (1,1)],
    [(1,1), (2,0)],
    [(1,1), (1,2)],  # 待移除的分支
    [(2,0), (3,1)],
    [(3,1), (4,0)]
])

# 拆分线段并建立索引映射
segments = list(mls.geoms)
seg_id_map = {idx: seg for idx, seg in enumerate(segments)}

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

邻接表记录每个端点连接的所有线段ID，为DFS遍历提供基础：

def get_endpoints(seg):
    """提取线段的起点和终点"""
    coords = list(seg.coords)
    return Point(coords[0]), Point(coords[-1])

# 构建邻接表：{端点Point: [关联线段ID列表]}
adjacency = {}
for seg_id, seg in seg_id_map.items():
    p1, p2 = get_endpoints(seg)
    
    def add_adj(point, sid):
        """处理精度后添加到邻接表"""
        for existing_p in adjacency:
            if point.equals_exact(existing_p, tolerance=1e-8):
                adjacency[existing_p].append(sid)
                return
        adjacency[point] = [sid]
    
    add_adj(p1, seg_id)
    add_adj(p2, seg_id)

步骤3：确定DFS起点 #

主线的起点是度数为1的端点（仅连接一条线段），这类点是主线的两端之一：

# 筛选度数为1的端点（主线的起点/终点）
start_candidates = [p for p, seg_ids in adjacency.items() if len(seg_ids) == 1]
# 取第一个候选作为DFS起点
start_point = start_candidates[0]
start_seg_id = adjacency[start_point][0]

步骤4：DFS遍历筛选主线线段 #

遍历过程中标记已访问的线段，避免重复，跟踪当前位置并递归遍历下一个端点：

visited_segs = set()
main_seg_ids = []

def dfs(current_p):
    connected_seg_ids = adjacency[current_p]
    for seg_id in connected_seg_ids:
        if seg_id not in visited_segs:
            visited_segs.add(seg_id)
            main_seg_ids.append(seg_id)
            # 获取线段的另一个端点
            seg = seg_id_map[seg_id]
            p1, p2 = get_endpoints(seg)
            next_p = p2 if p1.equals_exact(current_p, 1e-8) else p1
            dfs(next_p)

# 启动DFS
dfs(start_point)

步骤5：合并主线并计算总长度 #

提取筛选出的主线线段，合并后计算总长度：

# 提取主线线段
main_segments = [seg_id_map[sid] for sid in main_seg_ids]
# 合并为MultiLineString（如需单条LineString，可尝试shapely.ops.linemerge）
main_mls = MultiLineString(main_segments)
# 计算主线总长度
total_length = main_mls.length

print(f"主线总长度: {total_length}")
print("主线对象:", main_mls)

关键注意事项 #

• 精度控制：必须用equals_exact而非直接比较坐标，避免浮点误差导致点匹配失败，tolerance可根据数据精度调整。
• 闭合主线处理：如果主线是闭合的（无度数1的端点），需手动指定起点，遍历至回到起点为止。
• 线段合并：使用shapely.ops.linemerge(main_mls)可将首尾相连的主线合并为单个LineString，前提是线段无分支且连续。

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