平面1000点集如何为每个点计算对应的第n近邻点？

方案1：基于你已生成的listofdistances直接处理 #

你当前使用字符串作为键的单值字典结构不利于后续排序统计，首先需要重构数据结构：

• 遍历listofdistances，将每个点对的双向距离拆分存储到对应点的距离列表中
• 对每个点的距离列表按距离升序排序，截取前n项即可得到所需结果
  示例代码如下：

from collections import defaultdict

# 初始化每个点的距离存储字典
point_dist_map = defaultdict(list)

for item in listofdistances:
    # 取出单键字典的键值对
    pair_str, dist = next(iter(item.items()))
    # 把点对字符串转回元组，你自己生成的字符串可安全使用eval
    p1, p2 = eval(pair_str)
    # 跳过点自身与自身的配对（如果存在的话）
    if p1 == p2:
        continue
    # 双向存储距离与对应点
    point_dist_map[p1].append((dist, p2))
    point_dist_map[p2].append((dist, p1))

n = 3 # 替换为你需要的n值
result = {}
for p, dist_list in point_dist_map.items():
    # 按距离升序排序
    dist_list.sort(key=lambda x: x[0])
    # 取前n个最近邻，如果要严格第n近的点取dist_list[n-1]即可
    # 如果有相同距离的并列项，可额外过滤距离等于dist_list[n-1][0]的所有项
    result[p] = dist_list[:n]

方案2：更高效的免全量预计算方案 #

1000个点的全量点对计算量不大，但如果后续点规模扩容，建议直接使用KD树算法实现k近邻查询，无需提前枚举所有点对，Python生态已有成熟实现可以直接调用：

import numpy as np
from scipy.spatial import cKDTree

# 把你的点集P转成numpy数组格式，示例P = [(33,9), (34,13), ...]
point_arr = np.array(P)
# 构建KD树
tree = cKDTree(point_arr)
# 查询每个点的n+1个近邻，+1是因为第一个结果是点自身（距离为0）
distances, indices = tree.query(point_arr, k=n+1)
# 结果处理：indices[:, 1:] 是每个点前n个近邻的索引，distances[:, 1:]是对应距离
# 要转成点坐标直接取point_arr[indices[i][j]]即可

该方案时间复杂度远低于暴力枚举全量点对，即使点规模扩大到10万级也能快速得到结果。

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