电网节点坐标映射算法优化问询：PostGIS节点重定位问题

问题背景 #

需要实现算法将带真实坐标的电网节点网络转换为缩版网格地图，核心要求是保留节点间的相对位置与关联关系，输出网格坐标（如x:340,Y:670），可基于PostGIS/ST函数实现。当前采用「缩放真实坐标→ST_SnapToGrid→移动重合节点」的流程，导致网络变形，寻求可行算法思路。

当前尝试的PL/pgSQL函数代码：

CREATE OR REPLACE FUNCTION reduce_nodes(
    p_origin_geom    geometry,
    p_factor         float8)
RETURNS void AS $$
DECLARE
    v_node_geom     geometry;
    v_node_id       core_object_id;
    v_x_offset      float8;
    v_y_offset      float8;
    v_node_pin_geom geometry;
BEGIN
    FOR v_node_id, v_node_geom IN SELECT node_id, node_geom FROM tmp_node_positions
    LOOP
        v_node_geom := st_centroid(v_node_geom);
        v_x_offset := (st_x(v_node_geom) - st_x(p_origin_geom)) * 0.9;
        v_y_offset := (st_y(v_node_geom) - st_y(p_origin_geom)) * 0.9;
        v_node_pin_geom :=
            st_snaptogrid(
                st_makepoint(
                    st_x(v_node_geom) - v_x_offset,
                    st_y(v_node_geom) - v_y_offset
                ),
                10
            )
        ;
        UPDATE tmp_node_positions
        SET
            node_geom = v_node_pin_geom,
            x_log     = st_x(v_node_pin_geom),
            y_log     = st_y(v_node_pin_geom)
        WHERE node_id = v_node_id;
    END LOOP;
END;
$$ LANGUAGE plpgsql;

现有方案问题分析 #

当前代码的核心问题是孤立处理每个节点，未考虑节点间的拓扑关联：

1. 缩放逻辑仅基于单个节点与原点的偏移计算，未做全局统一的仿射变换，容易破坏节点间的相对位置关系；
2. ST_SnapToGrid直接对单个节点生效，导致相邻节点可能被snap到无关联的网格位置，引发网络拓扑变形；
3. 无重合节点的拓扑感知调整逻辑，移动重合节点时可能进一步打乱原有连接关系。

可行算法与实现思路 #

1. 力导向布局算法（Force-Directed Layout） #

基于物理模拟的拓扑保持布局，适合保留节点相对位置与关联：

• 核心逻辑：为每个节点添加两种力：
  • 斥力：所有节点间的排斥力，避免重合；
  • 拉力：相邻节点（有连接关系）间的吸引力，维持拓扑关联；
• PostGIS实现思路：
  1. 先对所有节点做全局缩放，将坐标映射到目标网格的大致范围；
  2. 迭代计算每个节点的受力：用ST_Distance计算节点间距，根据间距调整斥力/拉力的大小；
  3. 每次迭代更新节点坐标，直到节点位置稳定（位移小于阈值）；
  4. 最后用ST_SnapToGrid将坐标对齐到网格。

2. 拓扑感知的网格映射 #

先保证拓扑关联，再映射到网格：

• 步骤：
  1. 提取电网的拓扑邻接矩阵，记录每个节点的所有相邻节点；
  2. 对所有节点做全局统一的仿射变换（平移+缩放），将真实坐标映射到目标网格的边界范围内；
  3. 遍历节点，用ST_SnapToGrid获取初始网格坐标；
  4. 对重合节点，优先向其相邻节点的网格位置方向微调（比如选择相邻节点最多的方向的邻格），确保调整后仍保持邻接关系；
• 关键：调整重合节点时，必须参考其拓扑连接，避免破坏原有关联。

3. 网格嵌入的拓扑简化算法 #

针对电网的层级结构（如变电站→线路→变压器）做分层映射：

• 核心：先处理核心节点（如变电站），分配网格位置后，再依次处理其下级关联节点，保证下级节点的网格位置与核心节点保持合理的相对位置；
• PostGIS实现：
  1. 按节点的重要性（如电压等级）排序；
  2. 为高优先级节点分配网格坐标，确保间距符合缩放比例；
  3. 对低优先级节点，基于其连接的高优先级节点位置，计算并分配网格坐标，同时用ST_DWithin检查是否重合，必要时微调。

代码优化方向 #

先修正全局缩放逻辑，再添加拓扑感知的重合处理：

-- 示例：全局缩放+拓扑感知重合调整
CREATE OR REPLACE FUNCTION reduce_nodes_optimized(
    p_target_width  float8,  -- 目标网格宽度
    p_target_height float8,  -- 目标网格高度
    p_grid_size     float8   -- 网格单元大小
) RETURNS void AS $$
DECLARE
    v_min_x float8;
    v_max_x float8;
    v_min_y float8;
    v_max_y float8;
    v_scale_x float8;
    v_scale_y float8;
    v_node_geom geometry;
    v_node_id core_object_id;
    v_snapped_geom geometry;
BEGIN
    -- 1. 计算全局边界，确定缩放比例
    SELECT MIN(st_x(node_geom)), MAX(st_x(node_geom)), MIN(st_y(node_geom)), MAX(st_y(node_geom))
    INTO v_min_x, v_max_x, v_min_y, v_max_y
    FROM tmp_node_positions;

    v_scale_x := p_target_width / (v_max_x - v_min_x);
    v_scale_y := p_target_height / (v_max_y - v_min_y);

    -- 2. 全局缩放+平移到目标范围
    UPDATE tmp_node_positions
    SET node_geom = st_makepoint(
        (st_x(node_geom) - v_min_x) * v_scale_x,
        (st_y(node_geom) - v_min_y) * v_scale_y
    );

    -- 3. 网格对齐+拓扑感知重合处理
    FOR v_node_id, v_node_geom IN SELECT node_id, node_geom FROM tmp_node_positions LOOP
        v_snapped_geom := st_snaptogrid(v_node_geom, p_grid_size);
        
        -- 检查是否重合，若重合则向邻接节点方向微调
        WHILE EXISTS (SELECT 1 FROM tmp_node_positions 
                      WHERE node_id != v_node_id 
                        AND st_equals(node_geom, v_snapped_geom)) LOOP
            -- 获取邻接节点的平均方向，向该方向移动一个网格单元
            WITH adj_nodes AS (
                SELECT st_x(n.node_geom) - st_x(v_snapped_geom) AS dx,
                       st_y(n.node_geom) - st_y(v_snapped_geom) AS dy
                FROM tmp_node_positions n
                JOIN tmp_node_connections c ON n.node_id = c.connected_node_id
                WHERE c.node_id = v_node_id
            )
            SELECT st_makepoint(
                st_x(v_snapped_geom) + SIGN(AVG(dx)) * p_grid_size,
                st_y(v_snapped_geom) + SIGN(AVG(dy)) * p_grid_size
            ) INTO v_snapped_geom;
        END LOOP;

        UPDATE tmp_node_positions
        SET node_geom = v_snapped_geom,
            x_log = st_x(v_snapped_geom),
            y_log = st_y(v_snapped_geom)
        WHERE node_id = v_node_id;
    END LOOP;
END;
$$ LANGUAGE plpgsql;

注：上述代码需依赖tmp_node_connections表存储节点间的关联关系，需根据实际拓扑结构调整。

内容的提问来源于stack exchange，提问作者Andrés Almeida