python - 对曲线上定期采样的 2D 点列表进行排序

Question

我需要一个函数，根据 2D 点在曲线上的位置对它们进行排序，这样曲线上彼此相邻的两个点就会在排序列表中彼此相邻放置。

列表的长度没有限制，我只能使用math模块，我使用的是python 2.7。

“定期采样”意味着对于给定的点列表，任意两个相邻点之间的距离几乎恒定(具有 10**-3 epsilon 值，例如 0.0=0.001)。

到目前为止，我定义了一个由所有点之间的所有距离组成的函数，但卡住了。我虽然使用最短路径算法，但在这种情况下我需要使用所有点。到目前为止我的代码是

def dist(s):    
    return ((float(s[0][0])-s[1][0])**2.0+(float(s[0][1])-s[1][1])**2.0)**(1/2.)
def uz(x):
    if len(x)<=2:
        return []            
    else:
        x[1:2]=[]
        return [dist(x)]+uz(x)
def m(liste):
    return [dist(liste)]+uz(liste)
def alldist(liste):
    if len(liste)==2:
        return []
    else:
        k=[]
        for i in range(1,len(liste)):
            c=liste[(i-1):]
            k.append(m(c))
    print k

两种可能的排序之一就足够了。我更喜欢算法方面的帮助，但也欢迎代码。

提前致谢!!!

示例输入:

[[2.4492935982947064e-16, 4.0], 
 [2.0000000000000004, 3.4641016151377544], 
 [4.0, 0.0], 
 [-3.4641016151377539, 2.0000000000000013],
 [-1.9999999999999991, 3.4641016151377548], 
 [3.4641016151377548, 1.9999999999999998]]

输出:

[[4.0, 0.0], 
 [3.4641016151377548, 1.9999999999999998], 
 [2.0000000000000004, 3.4641016151377544], 
 [2.4492935982947064e-16, 4.0], 
 [-1.9999999999999991, 3.4641016151377548], 
 [-3.4641016151377539, 2.0000000000000013]]

Answer 1

我成功地做到了这一点，但我确信它可以用更好、更短的方式编写。

import math
def rec_helper(x,u,constant):
    if x==[]:
            return u
    elif abs(x[0]-constant)<10**(-3):
        u=u+1
        return rec_helper(x[1:],u,constant)
    else:
        return rec_helper(x[1:],u,constant)

def distance(x,i,j):
    return math.sqrt((x[j][0]-x[i][0])**2+(x[j][1]-x[i][1])**2)
def alt(f,l,n,liste,constant):
    p=liste[n*l:(n*l)+l]
    for o in range(0,l):    
        if abs(p[o]-constant)<10**(-3):
            return f
        else:
            f=f+1
def order(x):
    t=x
    l=len(x)
    liste=[]
    for i in range(0,l):
        for j in range(0,l):
            liste=liste+[distance(x,i,j)]
    a=liste[0:l]
    a.sort()
    sabit=a[1]
    n=0
    uc_nokta_sira=0
    for h in range(0,l):
        if rec_helper(liste[h*l:h*l+l],uc_nokta_sira,constant)==1:
            n=h
    uc_nokta=t[n]
    sonlist=[uc_nokta]
    m=[]
    f=0
    g=0
    return son(f,l,n,liste,constant,sonlist,t,g)
def son(f,l,n,liste,constant,sonlist,t,g):
    f=0
    m=liste
    if len(sonlist)==1:
        g=n
        n=alt(f,l,n,liste,constant)
        f=0
        sonlist=sonlist+[t[n]]
        return son(f,l,n,liste,constant,sonlist,t,g)
    if len(sonlist)==l:
        return sonlist
    if sonlist[-1]==t[alt(f,l,n,liste,constant)]:
        m[(n*l)+alt(f,l,n,liste,constant)]=10**5
        k=alt(f,l,n,m,constant)
        g=n
        sonlist=sonlist+[t[n]]
        n=k
        return son(f,l,n,liste,constant,sonlist,t,g)
    else:       
            if sonlist[-1]==t[n]:
                g=n
                n=alt(f,l,n,liste,constant)
                return son(f,l,n,liste,constant,sonlist,t,g)
            else:
                sonlist=sonlist+[t[n]]
                g=n
                n=alt(f,l,n,liste,constant)
                return son(f,l,n,liste,constant,sonlist,t,g)