Delaunay三角剖分中顶点多层邻居高效查找方法咨询

阿华AIGC实验室

2026-5-27

问题描述

我原本使用Python的scipy.spatial库对一组经纬度（LatLon）点生成Voronoi图来查找各点的邻居，后来发现Delaunay三角剖分更实用。目前我通过以下算法可以轻松查找各点的一阶邻居和二阶邻居：

from collections import defaultdict

def findNeighbors(delaunay): 
    """Returns a adjacency list of the graph"""
    neighbors = defaultdict(set)
    for simplex in delaunay.simplices:
        for vertice in simplex:
            other = set(simplex)
            other.remove(vertice)
            neighbors[vertice] = neighbors[vertice].union(other)
    return neighbors

def neighborCount(graph, start, target):
    if target in graph[start]:
        return 'First Tier Neighbor'
    elif graph[start] & graph[target]:
        return 'Second Tier Neighbor'

但现在我需要查找至多六阶邻居，目前找不到无需遍历整个邻接表的实现方式。下图是我要查找的“三阶邻居”示例：

三阶邻居示例

请问是否有更巧妙的实现方法？

解决方案

嘿，这个问题刚好戳中了广度优先搜索（BFS）的强项！你的Delaunay邻接表本质就是个无向图，按“阶数”找邻居本质上就是在图里做有限深度的分层遍历——完全不需要遍历整个邻接表，只从起始点出发，逐层扩展到你需要的最大阶数（比如6阶）就行。

我给你写了个通用的实现，既能一次性获取1到N阶的所有邻居，也能快速判断两个节点是否在指定阶数范围内，效率很高：

from collections import deque, defaultdict

def find_kth_neighbors(graph, start_node, max_k):
    """
    返回起始节点的1到max_k阶所有邻居，按阶数分组
    :param graph: 由findNeighbors生成的邻接表
    :param start_node: 起始节点的索引
    :param max_k: 需要查找的最大阶数（比如6）
    :return: 字典，key为阶数，value是对应阶数的邻居节点集合
    """
    # 记录每个节点的最小到达阶数，防止重复访问和重复计算
    visited = {start_node: 0}
    # 队列里存（当前节点，当前阶数）的元组
    queue = deque([(start_node, 0)])
    kth_neighbors = defaultdict(set)
    
    while queue:
        current_node, current_k = queue.popleft()
        # 如果当前已经到了最大阶数，就停止扩展这个节点的邻居
        if current_k >= max_k:
            continue
        # 遍历当前节点的所有一阶邻居
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                # 这个邻居的阶数是当前阶数+1
                visited[neighbor] = current_k + 1
                kth_neighbors[current_k + 1].add(neighbor)
                queue.append((neighbor, current_k + 1))
    
    return kth_neighbors

# 用法示例：
# 假设你已经生成了Delaunay对象delaunay
# graph = findNeighbors(delaunay)
# 获取节点0的1-6阶邻居
# neighbors_by_k = find_kth_neighbors(graph, 0, 6)
# 查看三阶邻居：print(neighbors_by_k[3])

# 如果你只是要判断两个节点是否是至多6阶邻居，可以用这个辅助函数
def is_within_k_tiers(graph, start, target, max_k):
    if start == target:
        return "Same Node"
    neighbors_by_k = find_kth_neighbors(graph, start, max_k)
    for k in range(1, max_k + 1):
        if target in neighbors_by_k.get(k, set()):
            return f"{k}th Tier Neighbor"
    return f"Not within {max_k} tiers"