给定单个目标点时如何从二维坐标点列表中查找指定数量最近邻点

这是典型的K近邻（K=8）查询场景，可根据点的总数量、查询频率选择不同的实现方式：

小数据量场景（总点数<1万，查询频率低） #

直接用暴力计算法即可，实现零成本，性能足够满足需求。

优化技巧：对比距离时不需要计算完整欧氏距离，仅用距离平方 (x1-x2)² + (y1-y2)² 对比即可，避免开平方运算的开销，排序结果完全一致。

# 原始坐标点列表
points = [(82.62000274658203, 79.7300033569336), (82.72000122070312, 79.56999969482422), (82.81999969482422, 80.06999969482422), (82.20999908447266, 80.5999984741211), (81.95999908447266, 80.29239654541016), (81.44000244140625, 81.08999633789062), (80.9000015258789, 81.48999786376953), ...]
# 目标红点坐标，替换为你的实际坐标即可
target_point = (target_x, target_y)

# 按距离平方排序后取前8个
nearest_8_points = sorted(points, key=lambda p: (p[0] - target_point[0])**2 + (p[1] - target_point[1])**2)[:8]

大数据量/高查询频率场景（总点数>10万，需要多次查询不同目标点） #

推荐用空间索引优化查询效率，可选两种常见实现：

• KD树：提前构建一次索引后，单次查询耗时可降低到O(logN)级别，Python可直接使用scipy封装好的KD树实现：

  import numpy as np
  from scipy.spatial import KDTree
  
  # 转换为numpy数组
  points_np = np.array(points)
  # 预构建KD树索引
  kdtree = KDTree(points_np)
  # 查询最近8个点，返回对应距离和点在原列表中的索引
  distances, indices = kdtree.query(np.array(target_point), k=8)
  # 取出对应的8个坐标点
  nearest_8_points = points_np[indices].tolist()
  

• 网格分桶法：适合点分布均匀的场景，无需第三方依赖，实现逻辑简单：
  1. 把整个坐标范围划分为等大的网格，每个网格存储落在该区域内的坐标点
  2. 查询时先定位目标点所在的网格，优先遍历该网格内的点，若不足8个再向外层相邻网格扩展，直到找到足够的最近点

若你的坐标点列表会频繁增删改动，单次查询的点数量又不多，优先选择暴力法，避免反复重建空间索引带来的额外开销。

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