如何用Python基于NetworkX路网生成支持边截断的服务区？

核心逻辑 #

NetworkX原生路径搜索仅基于节点计算距离，要实现边截断的服务区，需在搜索过程中实时跟踪累计距离：当距离达到阈值时，在对应边上插入虚拟节点，最终基于所有可达节点（含虚拟节点）和边段生成服务区多边形。

具体实现步骤 #

1. 网络数据预处理 #

• 确保图中每条边存储length属性（代表边的实际长度），节点存储x、y坐标属性，这是计算截断点位置的基础。
• 若起点（橙色点）不在网络节点上：
  • 用shapely计算起点到最近边的投影点。
  • 拆分原边为两段，删除原边后添加两段新边，并将投影点作为新节点加入网络，后续以此新节点作为搜索起点。

2. 带距离阈值的路径搜索与边截断 #

自定义Dijkstra算法变种，遍历过程中判断每条边是否需要截断：

• 初始化优先队列，存储（累计距离，当前节点），起点累计距离为0。
• 遍历当前节点的所有邻边：
  • 若当前累计距离 + 边长度 ≤ 阈值：将整条边加入可达边段集合，更新邻节点的累计距离并加入队列。
  • 若当前累计距离 + 边长度 > 阈值：计算剩余距离占边长度的比例，插值得到截断点坐标，将当前节点到截断点的边段加入集合，终止该边的后续遍历。

示例代码：

import networkx as nx
import heapq
from shapely.geometry import Point, LineString

def get_reachable_segments(G, start_node, distance_threshold):
    # 初始化节点距离字典
    node_dist = {node: float('inf') for node in G.nodes}
    node_dist[start_node] = 0
    priority_queue = []
    heapq.heappush(priority_queue, (0, start_node))
    reachable_segments = []

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_dist > distance_threshold:
            continue
        
        # 遍历当前节点的所有邻边
        for neighbor, edge_attr in G.adj[current_node].items():
            edge_len = edge_attr.get('length', 1.0)
            new_total_dist = current_dist + edge_len

            # 获取节点坐标
            curr_point = Point(G.nodes[current_node]['x'], G.nodes[current_node]['y'])
            neighbor_point = Point(G.nodes[neighbor]['x'], G.nodes[neighbor]['y'])

            if new_total_dist <= distance_threshold:
                # 整条边都在服务区内
                reachable_segments.append(LineString([curr_point, neighbor_point]))
                # 更新邻居节点距离并加入队列
                if new_total_dist < node_dist[neighbor]:
                    node_dist[neighbor] = new_total_dist
                    heapq.heappush(priority_queue, (new_total_dist, neighbor))
            else:
                # 截断边，计算截断点
                remaining_dist = distance_threshold - current_dist
                ratio = remaining_dist / edge_len
                # 插值计算截断点坐标
                cut_x = curr_point.x + ratio * (neighbor_point.x - curr_point.x)
                cut_y = curr_point.y + ratio * (neighbor_point.y - curr_point.y)
                cut_point = Point(cut_x, cut_y)
                # 添加截断后的边段
                reachable_segments.append(LineString([curr_point, cut_point]))
    
    return reachable_segments

3. 生成服务区多边形 #

基于收集到的可达边段，用shapely工具生成闭合的服务区多边形：

from shapely.ops import unary_union, polygonize

# 假设G是已构建的NetworkX图，start_node是搜索起点
segments = get_reachable_segments(G, start_node, 500)  # 500为距离阈值
# 合并所有边段
merged_lines = unary_union(segments)
# 生成多边形集合
polygon_list = list(polygonize([merged_lines]))
# 取面积最大的多边形作为最终服务区（过滤小碎片）
service_area = max(polygon_list, key=lambda p: p.area)

4. 多阈值服务区生成 #

若需要多个不同距离阈值的服务区，只需多次调用get_reachable_segments函数，传入不同阈值，重复多边形生成步骤即可。

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