基于无序列邻接表重构二维网格图的Python实现方案问询

问题背景 #

给定无序列邻接表及对应节点二维坐标，需将变形网格中的节点映射到规则二维网格，确定结构化连接关系：

adjacency_list = [[1, 4], [0, 2, 5], [1, 3, 7], [2, 6, 12],
                  [5, 0, 11], [4, 1, 7, 13], [3, 15, 8],
                  [2, 5, 12, 14], [6, 9, 16], [8, 10, 17],
                  [9, 19], [4, 13, 18], [7, 15, 3], [5, 11, 14, 20],
                  [7, 13], [6, 12, 16], [8, 15, 17], [16, 9, 19, 22],
                  [11, 20, 21], [10, 17, 24], [13, 18, 23], [18, 23, 27],
                  [17, 24, 28], [20, 21, 25, 30], [19, 22, 31],
                  [23, 26, 32], [25, 29, 34], [21, 30, 35], [22, 31, 36],
                  [26, 33, 37], [23, 27, 32, 38], [24, 28, 39],
                  [25, 30, 34, 40], [29, 36, 41], [26, 32, 37, 42],
                  [27, 38], [33, 43, 39, 28], [29, 34, 41, 44],
                  [30, 35, 40], [31, 36, 45], [32, 38, 42],
                  [33, 37, 43, 46], [34, 44, 40], [36, 41, 45],
                  [46, 37, 42], [39, 43], [41, 44]]

centers = [(1023, 763), (902, 742), (776, 718), (629, 681),
             (1041, 673), (924, 651), (479, 643), (799, 625),
             (329, 620), (180, 599), (41, 581), (1051, 580),
             (653, 580), (937, 556), (810, 529), (498, 529),
             (340, 509), (188, 491), (1059, 490), (47, 470),
             (943, 463), (1059, 393), (195, 386), (941, 365),
             (54, 361), (814, 339), (663, 311), (1055, 294),
             (201, 286), (509, 285), (933, 262), (62, 256),
             (806, 234), (357, 232), (657, 199), (1043, 189),
             (210, 185), (507, 167), (925, 157), (74, 149),
             (798, 128), (360, 122), (652, 88), (219, 79),
             (507, 53), (87, 41), (364, 11)]

需求说明 #

• 基于邻接关系（必要时结合二维坐标）实现Python代码
• 避免依赖角度、距离类启发式方法（网格变形角度可能超过45°）
• 最终输出每个节点在规则二维网格中的位置映射及结构化连接关系

核心算法思路 #

以起始节点为基础，通过寻找节点与已确定邻居的公共邻节点（对角线节点），推导四边形面内的节点方向关系：

1. 从起始节点出发，手动/通过坐标确定初始方向（如节点0的东向为1、南向为3）
2. 寻找起始节点与邻居的公共邻节点作为对角线节点（如节点0与1的对角线为4）
3. 基于四边形面的结构，推导邻居及对角线节点的对应方向（如节点1的南向为4，节点3的东向为4）
4. 迭代处理已确定部分方向的节点，逐步推导所有节点的结构化连接关系

Python实现方案 #

1. 初始化数据结构 #

定义节点方向映射字典，存储每个节点的东、西、南、北邻居：

# 初始化每个节点的方向映射：east(东), west(西), south(南), north(北)
node_directions = {i: {'east': None, 'west': None, 'south': None, 'north': None} for i in range(len(adjacency_list))}

# 设置起始节点0的初始方向（可结合坐标自动判断，此处按示例手动指定）
start_node = 0
node_directions[start_node]['east'] = 1
node_directions[start_node]['south'] = 3
# 反向设置邻居的对应方向
node_directions[1]['west'] = start_node
node_directions[3]['north'] = start_node

2. 对角线节点查找函数 #

实现函数寻找两个节点的公共邻节点（即对角线节点）：

def find_diagonal(node_a, node_b, adjacency_list):
    """查找节点a和节点b的公共邻节点（排除彼此）"""
    neighbors_a = set(adjacency_list[node_a])
    neighbors_b = set(adjacency_list[node_b])
    common_neighbors = neighbors_a & neighbors_b
    common_neighbors.discard(node_a)
    common_neighbors.discard(node_b)
    return common_neighbors.pop() if len(common_neighbors) == 1 else None

3. 迭代推导方向关系 #

使用队列迭代处理节点，基于对角线节点推导所有方向连接：

from collections import deque

# 队列存储待处理的节点
queue = deque([start_node])

while queue:
    current = queue.popleft()
    current_dirs = node_directions[current]
    
    # 遍历当前节点已确定的所有方向邻居
    for dir_type, neighbor in current_dirs.items():
        if neighbor is None:
            continue
        
        # 获取对角线节点
        diagonal = find_diagonal(current, neighbor, adjacency_list)
        if diagonal is None:
            continue
        
        # 根据当前方向推导其他节点的方向
        if dir_type == 'east':
            # 当前节点东向是neighbor → neighbor的南向是diagonal
            if node_directions[neighbor]['south'] is None:
                node_directions[neighbor]['south'] = diagonal
                node_directions[diagonal]['north'] = neighbor
                queue.append(neighbor)
            # 当前节点南向邻居的东向是diagonal
            south_neighbor = current_dirs['south']
            if south_neighbor and node_directions[south_neighbor]['east'] is None:
                node_directions[south_neighbor]['east'] = diagonal
                node_directions[diagonal]['west'] = south_neighbor
                queue.append(south_neighbor)
        
        elif dir_type == 'south':
            # 当前节点南向是neighbor → neighbor的东向是diagonal
            if node_directions[neighbor]['east'] is None:
                node_directions[neighbor]['east'] = diagonal
                node_directions[diagonal]['west'] = neighbor
                queue.append(neighbor)
            # 当前节点东向邻居的南向是diagonal
            east_neighbor = current_dirs['east']
            if east_neighbor and node_directions[east_neighbor]['south'] is None:
                node_directions[east_neighbor]['south'] = diagonal
                node_directions[diagonal]['north'] = east_neighbor
                queue.append(east_neighbor)
        
        elif dir_type == 'west':
            # 当前节点西向是neighbor → neighbor的北向是diagonal
            if node_directions[neighbor]['north'] is None:
                node_directions[neighbor]['north'] = diagonal
                node_directions[diagonal]['south'] = neighbor
                queue.append(neighbor)
            # 当前节点北向邻居的西向是diagonal
            north_neighbor = current_dirs['north']
            if north_neighbor and node_directions[north_neighbor]['west'] is None:
                node_directions[north_neighbor]['west'] = diagonal
                node_directions[diagonal]['east'] = north_neighbor
                queue.append(north_neighbor)
        
        elif dir_type == 'north':
            # 当前节点北向是neighbor → neighbor的西向是diagonal
            if node_directions[neighbor]['west'] is None:
                node_directions[neighbor]['west'] = diagonal
                node_directions[diagonal]['east'] = neighbor
                queue.append(neighbor)
            # 当前节点西向邻居的北向是diagonal
            west_neighbor = current_dirs['west']
            if west_neighbor and node_directions[west_neighbor]['north'] is None:
                node_directions[west_neighbor]['north'] = diagonal
                node_directions[diagonal]['south'] = west_neighbor
                queue.append(west_neighbor)
    
    # 将对角线节点加入队列（若未处理）
    for dir_type in ['east', 'south', 'west', 'north']:
        neighbor = current_dirs[dir_type]
        if neighbor:
            diagonal = find_diagonal(current, neighbor, adjacency_list)
            if diagonal and diagonal not in queue:
                queue.append(diagonal)

4. 映射到规则网格坐标 #

基于已确定的方向关系，将节点映射到规则二维网格的(x,y)坐标：

# 存储节点到规则网格坐标的映射
grid_coords = {}
grid_coords[start_node] = (0, 0)
queue = deque([start_node])

while queue:
    current = queue.popleft()
    x, y = grid_coords[current]
    current_dirs = node_directions[current]
    
    # 东向：x+1，y不变
    if current_dirs['east'] and current_dirs['east'] not in grid_coords:
        grid_coords[current_dirs['east']] = (x+1, y)
        queue.append(current_dirs['east'])
    # 西向：x-1，y不变
    if current_dirs['west'] and current_dirs['west'] not in grid_coords:
        grid_coords[current_dirs['west']] = (x-1, y)
        queue.append(current_dirs['west'])
    # 南向：x不变，y+1
    if current_dirs['south'] and current_dirs['south'] not in grid_coords:
        grid_coords[current_dirs['south']] = (x, y+1)
        queue.append(current_dirs['south'])
    # 北向：x不变，y-1
    if current_dirs['north'] and current_dirs['north'] not in grid_coords:
        grid_coords[current_dirs['north']] = (x, y-1)
        queue.append(current_dirs['north'])

# 输出结果
print("节点规则网格坐标映射：")
for node in sorted(grid_coords.keys()):
    print(f"节点{node}: {grid_coords[node]}")

注意事项 #

• 若起始节点的初始方向需自动判断，可结合centers坐标的x/y轴差值：x值较小为西、较大为东；y值较小为南、较大为北（需根据实际坐标系统调整）
• 若网格存在边界节点（邻接节点数不足），需在代码中增加边界判断逻辑，避免报错

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