基于距离的无重复点邻域查找算法实现疑问

核心问题分析 #

你当前的双重循环逻辑会遍历所有点对两次（点A→点B和点B→点A），只要距离小于阈值就记录，自然会产生重复连接。最近邻算法如果是双向遍历的话，同样会出现这个问题——因为点A的最近邻是点B，点B的最近邻也可能是点A。

解决方案 #

1. 限制内层循环的遍历范围 #

把内层循环的起始索引设为外层循环当前索引+1，这样每个点对只会被遍历一次。比如外层循环遍历第i个点，内层循环只遍历i+1到末尾的点：

# 示例伪代码
points = [point(0,0), point(1,1), point(2,0)]
threshold = 2.0
adjacent_pairs = []

for i in range(len(points)):
    p1 = points[i]
    # 内层从i+1开始，避免重复遍历
    for j in range(i+1, len(points)):
        p2 = points[j]
        distance = calculate_distance(p1, p2)
        if distance < threshold:
            adjacent_pairs.append( (p1, p2) )

这样得到的adjacent_pairs里每个连接只会出现一次，比如只会有(点1,点2)，不会有(点2,点1)。

2. 用集合存储连接（需处理点的可哈希性） #

如果不想修改循环范围，可以把连接转换成无序的可哈希结构（比如用元组存储点的索引，且按从小到大排序），然后存入集合自动去重：

# 示例伪代码
temp_pairs = set()
for i in range(len(points)):
    p1 = points[i]
    for j in range(len(points)):
        if i == j:
            continue
        p2 = points[j]
        distance = calculate_distance(p1, p2)
        if distance < threshold:
            # 把索引按顺序存，确保(1,2)和(2,1)变成同一个键
            pair = tuple(sorted( (i,j) ))
            temp_pairs.add(pair)
# 再把集合转成需要的点对格式
adjacent_pairs = [ (points[pair[0]], points[pair[1]]) for pair in temp_pairs ]

这种方法适合无法调整循环顺序的场景，但要注意点对象如果不可哈希，最好用索引代替点本身来处理。

3. 针对最近邻算法的去重 #

如果用最近邻算法，同样可以用上面两种方法：要么只遍历i<j的点对，记录每个点对中符合最近邻条件的连接；要么把得到的邻接关系用集合去重。另外，如果你只需要每个点的单向最近邻（比如每个点只保留一个最近的点，不管对方是否把自己当最近邻），可以直接为每个点记录唯一的最近邻，不需要考虑反向连接的问题。

补充说明 #

如果你的最终目标是生成无向图的边集，上述方法都能有效避免重复边；如果是有向图，那重复连接可能是合理的，但根据你描述的互连需求，应该是需要无向的边集，所以去重是必要的。

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