我为提前给出的冗长答案道歉：P（问题没有那么简单）。
让我们重新表述这个问题。寻找一条连接所有点的线，可以重新表述为图中的最短路径问题，其中（1）图节点是空间中的点，（2）每个节点连接到其2个最近的邻居，和（3）最短路径通过每个节点仅一次。最后一个约束是非常重要的本质上，问题是找到长度为N的排列，其中排列指的是路径中每个节点的顺序（N是节点的总数）。
寻找所有可能的排列并评估它们的成本太昂贵了（如果我没猜错的话，有N!个排列，这对于问题来说太大了）。下面我提出了一种方法，先找到N个最佳排列（每个N点的最佳排列），然后（从这些N中）找到使错误/成本最小化的排列。

1.用无序点创建随机问题

现在，让我们开始创建一个示例问题：

import matplotlib.pyplot as plt
import numpy as np

x = np.linspace(0, 2 * np.pi, 100)
y = np.sin(x)

plt.plot(x, y)
plt.show()

而在这里，未排序版本的点[x, y]模拟了一个随机点在空间中连接成一条线：

idx = np.random.permutation(x.size)
x = x[idx]
y = y[idx]

plt.plot(x, y)
plt.show()

然后问题是对这些点进行排序以恢复它们的原始顺序，从而正确地绘制线。

2.在节点之间创建2-NN图

我们可以先重新排列[N, 2]数组中的点：

points = np.c_[x, y]

然后，我们可以从创建一个最近邻图开始，将每个节点连接到它的2个最近邻：

from sklearn.neighbors import NearestNeighbors

clf = NearestNeighbors(2).fit(points)
G = clf.kneighbors_graph()

G是稀疏的N x N矩阵，其中每行表示一个节点，并且列的非零元素表示到那些点的欧几里得距离。
然后，我们可以使用networkx从该稀疏矩阵构造图：

import networkx as nx

T = nx.from_scipy_sparse_matrix(G)

3.查找从源到目标的最短路径

这里开始 * 魔术 *：我们可以使用dfs_preorder_nodes来提取路径，在给定开始节点（如果没有给定，则选择0节点）的情况下，这将实质上创建通过所有节点的路径（通过它们中的每一个恰好一次）。

order = list(nx.dfs_preorder_nodes(T, 0))

xx = x[order]
yy = y[order]

plt.plot(xx, yy)
plt.show()

这是因为无序列表中的点0位于直线的中间，也就是说，它首先是向一个方向运动，然后返回，并在另一个方向结束。

4.从所有源中查找开销最小的路径

因此，为了获得最优顺序，我们可以仅获得所有节点的最优顺序：

paths = [list(nx.dfs_preorder_nodes(T, i)) for i in range(len(points))]

现在我们已经有了从每个N = 100节点开始的最优路径，我们可以丢弃它们，并找到使连接之间的距离最小化的路径（优化问题）：

mindist = np.inf
minidx = 0

for i in range(len(points)):
    p = paths[i]           # order of nodes
    ordered = points[p]    # ordered nodes
    # find cost of that order by the sum of euclidean distances between points (i) and (i+1)
    cost = (((ordered[:-1] - ordered[1:])**2).sum(1)).sum()
    if cost < mindist:
        mindist = cost
        minidx = i

为每条最优路径的点排序，然后计算成本（通过计算所有点对i和i+1之间的欧几里德距离）。如果路径开始于start或end点，则其将具有最小成本，因为所有节点将是连续的。另一方面，如果路径起始于位于线中间的节点，则在某个点的成本将非常高，因为它需要从线的结束（或开始）行进到初始位置以探索另一个方向。使成本最小化的路径是起始于最佳点的路径。

opt_order = paths[minidx]

现在，我们可以适当地重构这个顺序：

xx = x[opt_order]
yy = y[opt_order]

plt.plot(xx, yy)
plt.show()

一个可能的解决方案是使用最近邻方法，可能是使用KDTree。Scikit-learn有一个很好的界面。然后可以使用networkx来构建一个图形表示。只有当要绘制的线应该经过最近邻时，这才真正起作用：

from sklearn.neighbors import KDTree
import numpy as np
import networkx as nx

G = nx.Graph()  # A graph to hold the nearest neighbours

X = [(0, 1), (1, 1), (3, 2), (5, 4)]  # Some list of points in 2D
tree = KDTree(X, leaf_size=2, metric='euclidean')  # Create a distance tree

# Now loop over your points and find the two nearest neighbours

# If the first and last points are also the start and end points of the line you can use X[1:-1]

for p in X
    dist, ind = tree.query(p, k=3)
    print ind

    # ind Indexes represent nodes on a graph
    # Two nearest points are at indexes 1 and 2. 
    # Use these to form edges on graph
    # p is the current point in the list
    G.add_node(p)
    n1, l1 = X[ind[0][1]], dist[0][1]  # The next nearest point
    n2, l2 = X[ind[0][2]], dist[0][2]  # The following nearest point  
    G.add_edge(p, n1)
    G.add_edge(p, n2)

print G.edges()  # A list of all the connections between points
print nx.shortest_path(G, source=(0,1), target=(5,4))
>>> [(0, 1), (1, 1), (3, 2), (5, 4)]  # A list of ordered points

更新：如果起点和终点未知，并且数据已合理地分开，则可以通过在图形中查找团来找到终点。起点和终点将形成一个团。如果从团中删除最长的边，则将在图形中创建一个自由端，该自由端可用作起点和终点。例如，此列表中的起点和终点显示在中间：

X = [(0, 1), (0, 0), (2, 1),  (3, 2),  (9, 4), (5, 4)]

构建完图之后，现在需要从团中删除最长的边，以找到图的自由端：

def find_longest_edge(l):
    e1 = G[l[0]][l[1]]['weight']
    e2 = G[l[0]][l[2]]['weight']
    e3 = G[l[1]][l[2]]['weight']
    if e2 < e1 > e3:
        return (l[0], l[1])
    elif e1 < e2 > e3:
        return (l[0], l[2])
    elif e1 < e3 > e2:
    return (l[1], l[2])

end_cliques = [i for i in list(nx.find_cliques(G)) if len(i) == 3]
edge_lengths = [find_longest_edge(i) for i in end_cliques]
G.remove_edges_from(edge_lengths)
edges = G.edges()

start_end = [n for n,nbrs in G.adjacency_iter() if len(nbrs.keys()) == 1]
print nx.shortest_path(G, source=start_end[0], target=start_end[1])
>>> [(0, 0), (0, 1), (2, 1), (3, 2), (5, 4), (9, 4)]  # The correct path

我也遇到了同样的问题。如果你有两个数组，其中的x和y值不是太弯曲，那么你可以将这些点转换到PCA空间，在PCA空间中对它们排序，然后再将它们转换回来。（我还添加了一些额外的平滑功能）。

import numpy as np
from scipy.signal import savgol_filter
from sklearn.decomposition import PCA

def XYclean(x,y): 

    xy = np.concatenate((x.reshape(-1,1), y.reshape(-1,1)), axis=1)     

    # make PCA object
    pca = PCA(2)
    # fit on data
    pca.fit(xy)

    #transform into pca space   
    xypca = pca.transform(xy) 
    newx = xypca[:,0]
    newy = xypca[:,1]

    #sort
    indexSort = np.argsort(x)
    newx = newx[indexSort]
    newy = newy[indexSort]

    #add some more points (optional)
    f = interpolate.interp1d(newx, newy, kind='linear')        
    newX=np.linspace(np.min(newx), np.max(newx), 100)
    newY = f(newX)            

    #smooth with a filter (optional)
    window = 43
    newY = savgol_filter(newY, window, 2)

    #return back to old coordinates
    xyclean = pca.inverse_transform(np.concatenate((newX.reshape(-1,1), newY.reshape(-1,1)), axis=1) )
    xc=xyclean[:,0]
    yc = xyclean[:,1]

    return xc, yc

我同意Imanol_Luengo Imanol Luengo的解决方案，但是如果您知道第一个点的索引，那么有一个简单得多的解决方案，它只使用NumPy：

def order_points(points, ind):
    points_new = [ points.pop(ind) ]  # initialize a new list of points with the known first point
    pcurr      = points_new[-1]       # initialize the current point (as the known point)
    while len(points)>0:
        d      = np.linalg.norm(np.array(points) - np.array(pcurr), axis=1)  # distances between pcurr and all other remaining points
        ind    = d.argmin()                   # index of the closest point
        points_new.append( points.pop(ind) )  # append the closest point to points_new
        pcurr  = points_new[-1]               # update the current point
    return points_new

此方法似乎适用于正弦曲线示例，尤其是因为很容易将第一个点定义为最左侧或最右侧的点。
对于问题中引用的img_skeleton数据，同样容易通过算法获得第一个点，例如作为最高点。

# create sine curve:

x      = np.linspace(0, 2 * np.pi, 100)
y      = np.sin(x)

# shuffle the order of the x and y coordinates:

idx    = np.random.permutation(x.size)
xs,ys  = x[idx], y[idx]   # shuffled points

# find the leftmost point:

ind    = xs.argmin()

# assemble the x and y coordinates into a list of (x,y) tuples:

points = [(xx,yy)  for xx,yy in zip(xs,ys)]

# order the points based on the known first point:

points_new = order_points(points, ind)

# plot:

fig,ax = plt.subplots(1, 2, figsize=(10,4))
xn,yn  = np.array(points_new).T
ax[0].plot(xs, ys)  # original (shuffled) points
ax[1].plot(xn, yn)  # new (ordered) points
ax[0].set_title('Original')
ax[1].set_title('Ordered')
plt.tight_layout()
plt.show()

我正在研究一个类似的问题，但它有一个重要的约束（很像OP给出的例子），即每个像素都有一个或两个相邻的像素，在8连通的意义上。

def sort_to_form_line(unsorted_list):
    """
    Given a list of neighboring points which forms a line, but in random order, 
    sort them to the correct order.
    IMPORTANT: Each point must be a neighbor (8-point sense) 
    to a least one other point!
    """
    sorted_list = [unsorted_list.pop(0)]

    while len(unsorted_list) > 0:
        i = 0
        while i < len(unsorted_list):
            if are_neighbours(sorted_list[0], unsorted_list[i]):
                #neighbours at front of list
                sorted_list.insert(0, unsorted_list.pop(i))
            elif are_neighbours(sorted_list[-1], unsorted_list[i]):
                #neighbours at rear of list
                sorted_list.append(unsorted_list.pop(i))
            else:
                i = i+1

    return sorted_list

def are_neighbours(pt1, pt2):
    """
    Check if pt1 and pt2 are neighbours, in the 8-point sense
    pt1 and pt2 has integer coordinates
    """
    return (np.abs(pt1[0]-pt2[0]) < 2) and (np.abs(pt1[1]-pt2[1]) < 2)

修改Toddp的答案，你可以找到任意形状的线的端点使用这个代码，然后排序点如Toddp所述，这比Imanol Luengo的答案快得多，唯一的约束是，线必须只有2个端点：

def order_points(points):
  if isinstance(points,np.ndarray): 
    assert points.shape[1]==2
    points = points.tolist()

  exts = get_end_points(points)
  assert len(exts) ==2
  ind = points.index(exts[0])

  points_new = [ points.pop(ind) ]  # initialize a new list of points with the known first point
  pcurr      = points_new[-1]       # initialize the current point (as the known point)
  while len(points)>0:
      d      = np.linalg.norm(np.array(points) - np.array(pcurr), axis=1)  # distances between pcurr and all other remaining points
      ind    = d.argmin()                   # index of the closest point
      points_new.append( points.pop(ind) )  # append the closest point to points_new
      pcurr  = points_new[-1]               # update the current point
  return points_new

def get_end_points(ptsxy):
  #source : https://stackoverflow.com/a/67145008/10998081
  if isinstance(ptsxy,list): ptsxy = np.array(ptsxy)
  assert ptsxy.shape[1]==2
  #translate to (0,0)for faster excution

  xx,yy,w,h = cv2.boundingRect(ptsxy)
  pts_translated = ptsxy -(xx,yy)
  bim = np.zeros((h+1,w+1))
  bim[[*np.flip(pts_translated).T]]=255
  extremes = []    
  for p in pts_translated:
    x = p[0]
    y = p[1]
    n = 0        
    n += bim[y - 1,x]
    n += bim[y - 1,x - 1]
    n += bim[y - 1,x + 1]
    n += bim[y,x - 1]    
    n += bim[y,x + 1]    
    n += bim[y + 1,x]    
    n += bim[y + 1,x - 1]
    n += bim[y + 1,x + 1]
    n /= 255        
    if n == 1:
      extremes.append(p)
  extremes = np.array(extremes)+(xx,yy)
  return extremes.tolist()