如何在NetworkX河流地理图网络中跨河连接邻近节点？

直接遍历所有节点对计算距离的O(n²)复杂度在节点量较大时完全不可行，推荐通过空间索引快速定位候选节点，大幅减少距离计算的次数，以下是两种落地方案：

方案一：GeoPandas + R-tree索引 #

借助GeoPandas的空间索引能力，快速圈定每个节点附近的候选对象，再精确过滤符合条件的跨河流节点对：

import networkx as nx
import geopandas as gpd
from shapely.geometry import Point

# 假设你的NetworkX图为G，每个节点包含'lon'（经度）、'lat'（纬度）、'river'（所属河流标识）属性
nodes_data = []
for node_id, attrs in G.nodes(data=True):
    nodes_data.append({
        'node_id': node_id,
        'geometry': Point(attrs['lon'], attrs['lat']),
        'river': attrs['river']
    })
# 转换为GeoDataFrame，设置WGS84坐标系
gdf = gpd.GeoDataFrame(nodes_data, crs="EPSG:4326")

# 转换为UTM投影坐标系（适合计算米级平面距离，避免经纬度大圆距离的计算开销）
gdf_proj = gdf.to_crs(gdf.estimate_utm_crs())

# 构建R-tree空间索引
sindex = gdf_proj.sindex

# 设置距离阈值（单位：米，根据实际河流交汇精度调整）
distance_threshold = 100

# 遍历节点查询近邻并添加边
for idx, row in gdf_proj.iterrows():
    # 生成当前节点周围阈值范围内的查询边界框
    bbox = row.geometry.buffer(distance_threshold).bounds
    # 用空间索引获取候选节点索引
    candidate_indices = list(sindex.intersection(bbox))
    # 排除自身和同河流节点
    for cand_idx in candidate_indices:
        if cand_idx == idx or row['river'] == gdf_proj.iloc[cand_idx]['river']:
            continue
        # 计算精确距离并判断是否符合阈值
        exact_distance = row.geometry.distance(gdf_proj.iloc[cand_idx].geometry)
        if exact_distance <= distance_threshold:
            G.add_edge(row['node_id'], gdf_proj.iloc[cand_idx]['node_id'], distance=exact_distance)

方案二：scikit-learn BallTree（球面距离优化） #

如果不需要完整的地理数据框能力，可直接用scikit-learn的BallTree处理球面距离（对应大圆距离）：

import networkx as nx
import numpy as np
from sklearn.neighbors import BallTree

# 提取节点数据：ID、经纬度、所属河流
node_ids = []
coords = []
river_tags = []
for node_id, attrs in G.nodes(data=True):
    node_ids.append(node_id)
    # BallTree计算球面距离需按[纬度, 经度]顺序传入
    coords.append([attrs['lat'], attrs['lon']])
    river_tags.append(attrs['river'])

coords = np.array(coords)
# 构建BallTree，使用haversine度量（球面距离，单位为弧度）
tree = BallTree(np.radians(coords), metric='haversine')

# 距离阈值转换：米转弧度（地球半径取6371000米）
distance_threshold = 100  # 单位：米
threshold_rad = distance_threshold / 6371000

# 查询每个节点的所有近邻节点索引
neighbor_indices = tree.query_radius(np.radians(coords), r=threshold_rad)

# 遍历结果添加跨河流边
for i, neighbors in enumerate(neighbor_indices):
    current_node = node_ids[i]
    current_river = river_tags[i]
    for j in neighbors:
        if i == j or current_river == river_tags[j]:
            continue
        # 可选：计算精确大圆距离（单位：米）
        exact_dist = 6371000 * tree.query(np.radians([coords[i]]), k=[j], return_distance=True)[0][0][0]
        if exact_dist <= distance_threshold:
            G.add_edge(current_node, node_ids[j], distance=exact_dist)

关键注意事项 #

• 必须给节点标记river属性，避免给同一条河流的节点重复加边
• 大范围区域优先用BallTree的球面距离；小范围区域转投影坐标系用平面距离更高效
• 距离阈值需根据河流数据的精度调整（比如高精度GPS数据可设为50米，低精度数据设为200米）

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