Python OpenCV：基于最近邻规则排序点集构建连续线段

你用Zhang-Suen算法提取的是8连通单像素宽骨架，针对这类点集，最可靠的排序方式是邻域追踪法，普通按x/y值排序的方式完全无法适配斜向、弯折线段，就是你看到的OpenCV默认扫描线存储的乱序效果。 #

实现步骤 #

• 预处理点集：把分离存储的x、y坐标数组合并为(x,y)格式的点集合，用哈希结构存储，实现O(1)复杂度的点存在性判断。
• 定位线段端点：遍历所有点，统计每个点8邻域范围内属于当前点集的点数量，非闭合单线段一定存在2个邻域计数为1的点，任选其一作为排序起点。如果是闭合环形骨架（无端点），任意选一个点作为起点即可。
• 顺序追踪建链：
  1. 将起点加入排序结果列表，标记为已访问
  2. 取结果列表的最后一个点作为当前点，遍历其8邻域，找到属于点集且未被访问的点，即为线段上的下一个相邻点
  3. 将找到的相邻点加入结果列表、标记为已访问，重复上一步，直到找不到下一个相邻点为止，最终输出的列表就是沿线段连续排列的点数组

注意事项 #

• 不要使用单纯按x或y坐标升/降序的排序逻辑：只要线段存在斜向段、弯折段、竖直段，这种排序都会打乱点的相邻关系，无法组成连续线段。
• 邻域判断必须用8邻域：Zhang-Suen骨架提取算法默认输出8连通结果，用4邻域判断会出现邻域漏检，导致追踪中途断连。
• 如果追踪时在某个点找到2个及以上未访问的邻域点，说明骨架存在分叉毛刺，需要先做骨架修剪去除毛刺再排序，否则会出现追踪路径错误。

核心逻辑参考代码 #

def sort_skeleton_points(x_coords, y_coords):
    point_set = set(zip(x_coords, y_coords))
    if not point_set:
        return []
    # 8邻域偏移量
    neighbor_offsets = [(-1,-1), (-1,0), (-1,1),
                        (0,-1),          (0,1),
                        (1,-1),  (1,0), (1,1)]
    # 查找起始端点
    start_point = None
    for p in point_set:
        x, y = p
        neighbor_count = 0
        for dx, dy in neighbor_offsets:
            if (x+dx, y+dy) in point_set:
                neighbor_count += 1
        if neighbor_count == 1:
            start_point = p
            break
    # 无端点（闭合环/孤立点）时随机选起点
    if start_point is None:
        start_point = next(iter(point_set))
    # 邻域追踪排序
    sorted_points = [start_point]
    visited = {start_point}
    current_p = start_point
    while True:
        next_p = None
        for dx, dy in neighbor_offsets:
            candidate = (current_p[0]+dx, current_p[1]+dy)
            if candidate in point_set and candidate not in visited:
                next_p = candidate
                break
        if next_p is None:
            break
        sorted_points.append(next_p)
        visited.add(next_p)
        current_p = next_p
    return sorted_points

拿到排序完成的点列表后，逐点计算相邻两点的欧氏距离并累加，就能得到两段红色标记线之间的骨架线精确长度。

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