如何基于最近邻规则对坐标数组列表进行排序？

问题描述 #

给定一组由x、y坐标组成的NumPy数组列表，需要按照前一个数组的最后一个坐标与下一个数组的第一个坐标距离最近的规则排序数组，得到连贯的路径序列。

输入修正 #

首先将输入的坐标列表修正为合法的Python/NumPy格式：

import numpy as np

# 原始输入修正为列表形式
coordinates = [
    np.array([[300, 2300], [670, 2360], [400, 2300]]),
    np.array([[1500, 1960], [1620, 2200], [1505, 1975]]),
    np.array([[980, 1965], [1060, 2240], [1100, 2250], [980, 1975]]),
    np.array([[565, 1940], [680, 2180], [570, 1945]])
]

解决方案：贪心最近邻排序 #

通过提取每个数组的首尾坐标，使用贪心算法依次选择距离当前路径终点最近的下一个数组：

方法1：纯NumPy实现

# 提取每个数组的起点（第一个坐标）和终点（最后一个坐标）
starts = [arr[0] for arr in coordinates]
ends = [arr[-1] for arr in coordinates]

sorted_coords = []
remaining_indices = set(range(len(coordinates)))

# 初始化：选择第一个数组作为起点（可根据需求调整起点）
current_idx = 0
sorted_coords.append(coordinates[current_idx])
remaining_indices.remove(current_idx)

while remaining_indices:
    current_end = ends[current_idx]
    # 计算当前终点到所有剩余数组起点的欧氏距离
    distance_list = []
    for idx in remaining_indices:
        dist = np.linalg.norm(current_end - starts[idx])
        distance_list.append((dist, idx))
    
    # 选择距离最小的数组
    distance_list.sort()
    next_idx = distance_list[0][1]
    
    sorted_coords.append(coordinates[next_idx])
    remaining_indices.remove(next_idx)
    current_idx = next_idx

# 输出排序结果
print("coordinates =", sorted_coords)

方法2：结合sklearn.NearestNeighbors优化

如果数组数量较多，可使用NearestNeighbors加速最近邻查找：

from sklearn.neighbors import NearestNeighbors

# 提取起点数组
start_points = np.array(starts)

sorted_coords = []
remaining_indices = set(range(len(coordinates)))
current_idx = 0
sorted_coords.append(coordinates[current_idx])
remaining_indices.remove(current_idx)

nn = NearestNeighbors(n_neighbors=1)

while remaining_indices:
    current_end = ends[current_idx].reshape(1, -1)
    # 仅对剩余的起点进行拟合
    remaining_start_arr = start_points[list(remaining_indices)]
    nn.fit(remaining_start_arr)
    
    # 查找最近邻
    _, idx_in_remaining = nn.kneighbors(current_end)
    # 转换为原列表索引
    next_idx = list(remaining_indices)[idx_in_remaining[0][0]]
    
    sorted_coords.append(coordinates[next_idx])
    remaining_indices.remove(next_idx)
    current_idx = next_idx

# 输出排序结果
print("coordinates =", sorted_coords)

说明 #

• 两种方法均会得到你期望的排序结果，核心逻辑是贪心选择最近邻：每次从剩余数组中挑选起点与当前路径终点距离最小的数组。
• 若之前使用NearestNeighbors失败，大概率是没有动态过滤已选中的数组，导致重复选择或匹配错误。

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