能否用Numpy函数替代循环实现点对匹配排序？

现有一个表示点集的Numpy数组，前两列与问题无关，后三列为X、Y、Z坐标。数组每两行构成一个线段对，需保持成对移动，要将数组排序为可形成闭合区域的点序列。目前已通过while循环实现该功能，询问是否可通过Numpy函数或其组合替代循环完成此操作。

原始数组：

import numpy as np
points = np.array([[1., 1., 4., 0., 0.],
                   [1., 1., 8., 0., 0.],
                   [1., 5., 4., 0., 0.],
                   [1., 5., 4., 0., 8.],
                   [1., 7., 4., 0., 8.],
                   [1., 7., 8., 0., 8.],
                   [1., 9., 8., 0., 0.],
                   [1., 9., 8., 0., 8.]])

目标排序数组：

array([[1., 1., 4., 0., 0.],
       [1., 1., 8., 0., 0.],
       [1., 9., 8., 0., 0.],
       [1., 9., 8., 0., 8.],
       [1., 7., 8., 0., 8.],
       [1., 7., 4., 0., 8.],
       [1., 5., 4., 0., 8.],
       [1., 5., 4., 0., 0.]])

当前循环实现代码：

compare2 = np.equal(points[:, -3:], points[:, -3:].reshape(-1, 1, 3))
compare2 = np.all(compare2, 2)
values, index = np.where(compare2)
values2, index2 = np.unique(index.reshape(-1, 2), return_index=True, axis=0)

ref_index = np.arange(0, 8).reshape(-1, 2)
new_index = np.arange(0, 8)
i = 1
while i < len(new_index) - 1:
    if i % 2 == 1:
        # 查找匹配值
        selected_entry = values2[np.any(values2 == new_index[i], 1)]
        # 添加到下一个位置
        new_index[i+1] = int(selected_entry[selected_entry != new_index[i]])
    else:
        selected_entry = ref_index[np.any(ref_index == new_index[i], 1)]
        # 添加到下一个位置
        new_index[i+1] = int(selected_entry[selected_entry != new_index[i]])
    i += 1  
sorted_points = points[new_index]

可以通过Numpy结合字典映射的方式替代逐点循环，核心是先构建点与线段对的邻接关系，再推导排序序列，效率比原始循环更高。具体实现如下：

import numpy as np

points = np.array([[1., 1., 4., 0., 0.],
                   [1., 1., 8., 0., 0.],
                   [1., 5., 4., 0., 0.],
                   [1., 5., 4., 0., 8.],
                   [1., 7., 4., 0., 8.],
                   [1., 7., 8., 0., 8.],
                   [1., 9., 8., 0., 0.],
                   [1., 9., 8., 0., 8.]])

# 提取有效坐标与原始线段对分组
coords = points[:, -3:]
seg_pairs = np.arange(len(points)).reshape(-1, 2)

# 构建坐标到点索引的映射，快速找到共享坐标的点
coord_to_indices = {}
for idx, coord in enumerate(coords):
    key = tuple(coord)
    coord_to_indices[key] = coord_to_indices.get(key, []) + [idx]

# 生成每个点的连接点索引（排除自身）
adjacent = np.zeros(len(points), dtype=int)
for idx in range(len(points)):
    connected_points = coord_to_indices[tuple(coords[idx])]
    adjacent[idx] = connected_points[0] if connected_points[1] == idx else connected_points[1]

# 构建线段对的邻接关系：每个线段对对应的下一个关联线段对
pair_adjacent = {}
for pair in seg_pairs:
    end_point = pair[1]
    # 找到终点的连接点所属的线段对
    connected_point = adjacent[end_point]
    next_pair_idx = np.where((seg_pairs == connected_point).any(axis=1))[0][0]
    pair_adjacent[tuple(pair)] = seg_pairs[next_pair_idx]

# 生成排序后的索引序列
current_pair = seg_pairs[0]
sorted_indices = list(current_pair)
used_pairs = {tuple(current_pair)}

# 遍历所有线段对完成排序
while len(sorted_indices) < len(points):
    next_pair = pair_adjacent[tuple(current_pair)]
    if tuple(next_pair) not in used_pairs:
        # 保证线段对的顺序与连接逻辑一致
        if next_pair[0] == adjacent[current_pair[1]]:
            sorted_indices.extend(next_pair)
        else:
            sorted_indices.extend(next_pair[::-1])
        used_pairs.add(tuple(next_pair))
        current_pair = next_pair

# 得到最终排序数组
sorted_points = points[sorted_indices]
print(sorted_points)

代码说明 #

1. 坐标映射：用字典记录每个坐标对应的所有点索引，快速找到共享坐标的连接点
2. 邻接关系构建：先确定单个点的连接点，再推导线段对之间的关联关系
3. 序列生成：从第一个线段对出发，依次根据邻接关系遍历所有线段对，生成完整的排序索引

这种方式的循环次数仅为线段对的数量（远小于原始点数量），核心的关系查找依赖字典和Numpy的向量化操作，比原始逐点循环效率更高。如果追求完全无循环，可以通过构建邻接矩阵并利用矩阵累积运算推导路径，但实现复杂度会大幅提升，对于小规模数据来说，上述方案已经足够高效且易读。

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