使用Euclidean Distance实现图像点分组的计算方法求助

你需要实现的逻辑本质是全点K近邻搜索，通常不需要用递归实现核心计算逻辑，递归反而容易引发栈溢出、重复计算问题，以下是工业界常用的可落地实践方案：

基础实现方案（适配点数量<10000的小规模场景） #

该方案逻辑简单易维护，不需要引入额外依赖：

• 先将所有点坐标整理为二维数组，格式参考coords = np.array([[x1,y1], [x2,y2], ..., [xn,yn]])，n为总点数
• 用numpy向量化计算所有点对的欧氏距离，效率远高于逐点循环计算：

import numpy as np

# 自定义近邻数量，需要5个就设为5，需要6个就设为6
k = 6
# 生成n*n的距离矩阵，每个元素是对应两个点的欧氏距离
dist_matrix = np.linalg.norm(coords[:, np.newaxis] - coords[np.newaxis, :], axis=2)
# 按行排序取前k+1个结果，跳过第0位（点和自身的距离为0，无意义）
top_k_neighbors = np.argsort(dist_matrix, axis=1)[:, 1:k+1]

• 如果需要保留5~6个近邻，可以额外加距离阈值过滤：近邻距离超过预设阈值的直接剔除，最终保留的数量会落在你需要的区间内。

大规模点集优化方案（适配点数量≥10000的场景） #

基础方案的内存占用为O(n²)，点量过大时会出现内存不足问题，此时用KD树做近邻搜索即可优化性能：

from sklearn.neighbors import KDTree

k = 6
# 基于点集构建KD树索引
tree = KDTree(coords, leaf_size=30)
# 查询所有点的前k+1个近邻，返回值第一个为距离数组，第二个为近邻索引数组
dist_arr, top_k_neighbors = tree.query(coords, k=k+1)
# 剔除自身对应的索引
top_k_neighbors = top_k_neighbors[:, 1:]

• 该方案的时间复杂度为O(n log n)，内存占用为O(n)，支持十万甚至百万级点集的近邻计算。

递归逻辑适配方法 #

如果你是要基于近邻结果做区域生长、连通域分析等需要递归的后续操作，可以按以下逻辑实现：

• 初始化访问标记数组visited = np.zeros(len(coords), dtype=bool)，用来标记点是否已经完成处理
• 递归函数参考逻辑：
  1. 输入当前点的索引，首先将该点标记为已访问
  2. 取出该点对应的前k个近邻，遍历所有未被标记为已访问的近邻，调用递归函数处理
  3. 所有点都被标记为已访问时终止流程

注意：Python默认递归深度限制为1000左右，如果点量过大需要将递归改为栈迭代的写法，逻辑完全一致，不会触发深度限制报错。

常见注意事项 #

• 图像坐标要注意格式统一，避免把(x,y)坐标和(行,列)坐标搞混，导致距离计算结果错误
• 如果需要过滤掉图像边界外的无效点，只需要在得到近邻索引后，加一步坐标范围判断再做过滤即可
• 如果需要结合像素灰度值优化近邻筛选规则，可以在欧氏距离的基础上加上灰度差的加权值，再做排序筛选。

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