逆时针排序x和y数据

Question

我有一组点的文本文件：random_shape.dat。文件中点的初始顺序是随机的。我想按照逆时针顺序对这些点进行排序，如下所示（红点是xy数据）： 我尝试使用极坐标来实现：我计算每个点(x,y)的极角，然后按升序排列，如下所示：

"""
Script: format_file.py
Description: This script will format the xy data file accordingly to be used with a program expecting CCW order of data points, By soting the points in Counterclockwise order
Example: python format_file.py random_shape.dat
"""

import sys
import numpy as np

# Read the file name
filename = sys.argv[1]

# Get the header name from the first line of the file (without the newline character)
with open(filename, 'r') as f:
    header = f.readline().rstrip('\n')

angles = []
# Read the data from the file
x, y = np.loadtxt(filename, skiprows=1, unpack=True)


for xi, yi in zip(x, y):
    angle = np.arctan2(yi, xi) 
    if angle < 0:
        angle += 2*np.pi # map the angle to 0,2pi interval
    angles.append(angle)

# create a numpy array 
angles = np.array(angles)

# Get the arguments of sorted 'angles' array
angles_argsort = np.argsort(angles)

# Sort x and y
new_x = x[angles_argsort]
new_y = y[angles_argsort]

print("Length of new x:", len(new_x))
print("Length of new y:", len(new_y))

with open(filename.split('.')[0] + '_formatted.dat', 'w') as f:
    print(header, file=f)
    for xi, yi in zip(new_x, new_y):
        print(xi, yi, file=f)

print("Done!")

通过运行脚本：

python format_file.py random_shape.dat

很不幸，我在random_shape_formated.dat中没有得到预期的结果！点没有按所需顺序排序。

感谢任何帮助。

编辑: 期望的结果如下：

• 创建一个名为：filename_formatted.dat 的新文件，其中包含根据上图排序的数据（第一行包含起始点，接下来的行包含蓝色箭头所示的点，方向为逆时针）。

编辑2: 此处添加了xy数据，而不是使用github gist:

random_shape
0.4919261070361315  0.0861956168831175
0.4860816807027076  -0.06601587301587264
0.5023029456281289  -0.18238249845392662
0.5194784026079869  0.24347943722943777
0.5395164357511545  -0.3140611471861465
0.5570497147514262  0.36010146103896146
0.6074231036252226  -0.4142604617604615
0.6397066014669927  0.48590810704447085
0.7048302091822873  -0.5173701298701294
0.7499157837544145  0.5698170011806378
0.8000108666123336  -0.6199254449254443
0.8601249660418364  0.6500974025974031
0.9002010323281716  -0.7196585989767801
0.9703341483292582  0.7299242424242429
1.0104102146155935  -0.7931355765446666
1.0805433306166803  0.8102046438410078
1.1206193969030154  -0.865251869342778
1.1907525129041021  0.8909386068476981
1.2308285791904374  -0.9360074773711129
1.300961695191524  0.971219008264463
1.3410377614778592  -1.0076702085792988
1.4111708774789458  1.051499409681228
1.451246943765281  -1.0788793781975592
1.5213800597663678  1.1317798110979933
1.561456126052703  -1.1509956709956706
1.6315892420537896  1.2120602125147582
1.671665308340125  -1.221751279024005
1.7417984243412115  1.2923406139315234
1.7818744906275468  -1.2943211334120424
1.8520076066286335  1.3726210153482883
1.8920836729149686  -1.3596340023612745
1.9622167889160553  1.4533549783549786
2.0022928552023904  -1.4086186540731989
2.072425971203477  1.5331818181818184
2.1125020374898122  -1.451707005116095
2.182635153490899  1.6134622195985833
2.2227112197772345  -1.4884454939000387
2.292844335778321  1.6937426210153486
2.3329204020646563  -1.5192876820149541
2.403053518065743  1.774476584022039
2.443129584352078  -1.5433264462809912
2.513262700353165  1.8547569854388037
2.5533387666395  -1.561015348288075
2.6234718826405867  1.9345838252656438
2.663547948926922  -1.5719008264462806
2.7336810649280086  1.9858362849271942
2.7737571312143436  -1.5750757575757568
2.8438902472154304  2.009421487603306
2.883966313501766  -1.5687258953168035
2.954099429502852  2.023481896890988
2.9941754957891877  -1.5564797323888229
3.0643086117902745  2.0243890200708385
3.1043846780766096  -1.536523022432113
3.1745177940776963  2.0085143644234558
3.2145938603640314  -1.5088557654466737
3.284726976365118  1.9749508067689887
3.324803042651453  -1.472570838252656
3.39493615865254  1.919162731208186
3.435012224938875  -1.4285753640299088
3.5051453409399618  1.8343467138921687
3.545221407226297  -1.3786835891381335
3.6053355066557997  1.7260966810966811
3.655430589513719  -1.3197205824478546
3.6854876392284703  1.6130086580086582
3.765639771801141  -1.2544077134986225
3.750611246943765  1.5024152236652237
3.805715838087476  1.3785173160173163
3.850244800627849  1.2787337662337666
3.875848954088563  -1.1827449822904361
3.919007794704616  1.1336638361638363
3.9860581363759846  -1.1074537583628485
3.9860581363759846  1.0004485329485333
4.058012891753723  0.876878197560016
4.096267318663407  -1.0303482880755608
4.15638141809291  0.7443374218374221
4.206476500950829  -0.9514285714285711
4.256571583808748  0.6491902794175526
4.3166856832382505  -0.8738695395513574
4.36678076609617  0.593855765446675
4.426894865525672  -0.7981247540338443
4.476989948383592  0.5802489177489183
4.537104047813094  -0.72918339236521
4.587199130671014  0.5902272727272733
4.647313230100516  -0.667045454545454
4.697408312958435  0.6246979535615904
4.757522412387939  -0.6148858717040526
4.807617495245857  0.6754968516332154
4.8677315946753605  -0.5754260133805582
4.917826677533279  0.7163173947264858
4.977940776962782  -0.5500265643447455
5.028035859820701  0.7448917748917752
5.088149959250204  -0.5373268398268394
5.138245042108123  0.7702912239275879
5.198359141537626  -0.5445838252656432
5.2484542243955445  0.7897943722943728
5.308568323825048  -0.5618191656828015
5.358663406682967  0.8052154663518301
5.41877750611247  -0.5844972451790631
5.468872588970389  0.8156473829201105
5.5289866883998915  -0.6067217630853987
5.579081771257811  0.8197294372294377
5.639195870687313  -0.6248642266824076
5.689290953545233  0.8197294372294377
5.749405052974735  -0.6398317591499403
5.799500135832655  0.8142866981503349
5.859614235262157  -0.6493565525383702
5.909709318120076  0.8006798504525783
5.969823417549579  -0.6570670995670991
6.019918500407498  0.7811767020857934
6.080032599837001  -0.6570670995670991
6.13012768269492  0.7562308146399057
6.190241782124423  -0.653438606847697
6.240336864982342  0.7217601338055886
6.300450964411845  -0.6420995670995664
6.350546047269764  0.6777646595828419
6.410660146699267  -0.6225964187327819
6.4607552295571855  0.6242443919716649
6.520869328986689  -0.5922077922077915
6.570964411844607  0.5548494687131056
6.631078511274111  -0.5495730027548205
6.681173594132029  0.4686727666273125
6.7412876935615325  -0.4860743801652889
6.781363759847868  0.3679316979316982
6.84147785927737  -0.39541245791245716
6.861515892420538  0.25880333951762546
6.926639500135833  -0.28237987012986965
6.917336127605076  0.14262677798392165
6.946677533279001  0.05098957832291173
6.967431210462995  -0.13605442176870675
6.965045730326905  -0.03674603174603108

- s.ouchene

---

是的，但是任何人怎么能断言他们提供的答案是正确的呢？ - Dani Mesejo

我认为丹尼尔是在问你是否有一个已经（手动？）排序的文件版本来进行测试。 - YBadiss

从您的图片来看，x，y =（0,0）不在您的轮廓内，我没有在您的代码中看到任何移位。 - Paul Panzer

即使将原点移动到形状内部，通过对角度进行排序也无法得到您想要的结果，因为该形状不是凸形的。这意味着，如果你从原点到曲线上的一些点画一条直线，该直线可能会与曲线上的其他点相交。 - natnij

@Navaro "平滑"？我所说的与某些未定义的“平滑度”无关，只是对于y>0，您可以按x排序，而对于y<0，您可以按x排序。如果是，请参见YBadiss的答案。正如您所说的“平滑度”，可能是与最近的点连接（即我们不跳跃，然后返回未使用的点）。 - h4z3

Answer 1

我发现对于像这样具有x，y坐标的点进行排序的简单方法是根据从点到整个多边形的质心和水平线之间的夹角来对它们进行排序，该角度在示例中称为alpha。可以通过计算所有点的x，y坐标的平均值来轻松地计算出质心的坐标(x0和y0)。然后使用numpy.arccos等函数计算角度。当y-y0大于0时，您直接取角度，否则从360°(2)中减去角度。我在计算角度时使用了numpy.where，然后使用numpy.argsort生成一个索引初始化x，y值的掩码。以下函数sort_xy根据这个角度对所有x和y坐标进行排序。如果您想从任何其他点开始，可以添加偏移角度。但在您的情况下，应为零。

def sort_xy(x, y):

    x0 = np.mean(x)
    y0 = np.mean(y)

    r = np.sqrt((x-x0)**2 + (y-y0)**2)

    angles = np.where((y-y0) > 0, np.arccos((x-x0)/r), 2*np.pi-np.arccos((x-x0)/r))

    mask = np.argsort(angles)

    x_sorted = x[mask]
    y_sorted = y[mask]

    return x_sorted, y_sorted

使用matplotlib.pyplot.plot绘制未排序的x，y值（点明显未排序）：

使用此方法排序后，使用matplotlib.pyplot.plot绘制x，y值：

- SariO

Answer 2

逆时针顺序取决于枢轴点的选择。根据您的问题，一个好的枢轴点选择是重心。

类似这样：

# Find the Center of Mass: data is a numpy array of shape (Npoints, 2)
mean = np.mean(data, axis=0)
# Compute angles
angles = np.arctan2((data-mean)[:, 1], (data-mean)[:, 0])
# Transform angles from [-pi,pi] -> [0, 2*pi]
angles[angles < 0] = angles[angles < 0] + 2 * np.pi
# Sort
sorting_indices = np.argsort(angles)
sorted_data = data[sorting_indices]

- Remi Zaidan

Answer 3

如果确定曲线不会在同一X坐标（即任何竖直线）上交叉超过两次，那么可以按照X排序的顺序访问点，并将一个点附加到你跟随的两个轨道中的一个：附加到最接近新点的末端点的轨道。其中一个轨道代表曲线的“上部”，另一个轨道代表“下部”。

逻辑如下：

dist2 = lambda a,b: (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1])

z = list(zip(x, y)) # get the list of coordinate pairs
z.sort() # sort by x coordinate

cw = z[0:1] # first point in clockwise direction
ccw = z[1:2] # first point in counter clockwise direction
# reverse the above assignment depending on how first 2 points relate
if z[1][1] > z[0][1]: 
    cw = z[1:2]
    ccw = z[0:1]

for p in z[2:]:
    # append to the list to which the next point is closest
    if dist2(cw[-1], p) < dist2(ccw[-1], p):
        cw.append(p)
    else:
        ccw.append(p)

cw.reverse()
result = cw + ccw

这种方法也适用于Y坐标波动剧烈的曲线，即使是从某个中心点开始的围绕角度也无法解决，就像这张图片所示的一样: 不会对X或Y坐标的范围做任何假设：例如，该曲线不一定要横跨X轴（Y = 0）才能使用此方法。

- trincot

---

谢谢你的回答。你能否请检查一下你的代码是否运行良好？ - s.ouchene

“Zip”对象没有“sort”属性。 - s.ouchene

好的，我在我的测试中有明确的数据（z = [[0.4919261070361315, 0.0861956168831175], ...]）。所以首先将其转换为列表：list(zip(x, y))。对此感到抱歉。 - trincot

Answer 4

如果：

• 形状任意复杂且
• 点间距离大致随机

那么我认为这是一个非常难的问题。

值得一提的是，我曾经遇到过类似的问题，并使用了旅行商求解器。特别地，我使用了LKH求解器。我看到有一个用于解决问题的Python仓库，LKH-TSP。一旦你有了点的顺序，我认为决定顺时针还是逆时针排序不会太难。

- Matt Hall

Answer 5

我觉得这不完全是一个Python问题，但你可以尝试使用 - sign(y) * x 进行排序，类似于以下操作：

def counter_clockwise_sort(points):
    return sorted(points, key=lambda point: point['x'] * (-1 if point['y'] >= 0 else 1))

假设您将您的点正确地读入到字典列表中，格式为{'x': 0.12312, 'y': 0.912}，那么应该能够正常工作。

编辑：只要您仅在X轴上交叉两次，就像您的示例一样，这将起作用。

- YBadiss

---

是的，因此我进行了编辑，它只在您精确地穿过X轴两次时才起作用。 - YBadiss

Answer 6

如果我们想回答你具体的问题，我们需要选择一个枢轴点。

由于您想根据选择的起始点进行排序，我会在中间取一个枢轴点（x = 4，y = 0即可）。

由于我们是按逆时针方向排序的，因此我们将采用arctan2（-（y-pivot_y），-（x-center_x））（我们翻转了x轴）。

我们得到以下结果，并使用渐变着色的散点图证明正确性（请注意，我在下载后删除了dat文件的第一行）：

import numpy as np
import matplotlib.pyplot as plt
points = np.loadtxt('points.dat')

#oneliner for ordering points (transform, adjust for 0 to 2pi, argsort, index at points)
ordered_points = points[np.argsort(np.apply_along_axis(lambda x: np.arctan2(-x[1],-x[0]+4) + np.pi*2, axis=1,arr=points)),:]

#color coding 0-1 as str for gray colormap in matplotlib
plt.scatter(ordered_points[:,0], ordered_points[:,1],c=[str(x) for x in np.arange(len(ordered_points)) / len(ordered_points)],cmap='gray')

结果（在颜色地图中，1代表白色，0代表黑色），它们按顺序以0-1范围内的数字编号：

- ec2604

Answer 7

对于相邻点之间距离可比较的点，我们可以使用KDTree获取每个点的两个最近点。然后连接这些线条以得到一个封闭形状轮廓。然后，我们将利用OpenCV的findContours始终以逆时针方式跟踪轮廓。现在，由于OpenCV处理图像，因此我们需要从提供的浮点格式中采样数据以转换为uint8图像格式。由于两个点之间的距离是可比较的，因此这应该是非常安全的。而且，OpenCV可以很好地处理曲线中的锐角，即使是光滑或不光滑的数据也能正常工作。而且，没有枢轴要求等等。因此，所有类型的形状都可以很好地处理。

以下是实现：

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist
from scipy.spatial import cKDTree
import cv2
from scipy.ndimage.morphology import binary_fill_holes

def counter_clockwise_order(a, DEBUG_PLOT=False):
    b = a-a.min(0)
    d = pdist(b).min()
    c = np.round(2*b/d).astype(int)

    img = np.zeros(c.max(0)[::-1]+1, dtype=np.uint8)

    d1,d2 = cKDTree(c).query(c,k=3)
    b = c[d2]
    p1,p2,p3 = b[:,0],b[:,1],b[:,2]
    for i in range(len(b)):    
        cv2.line(img,tuple(p1[i]),tuple(p2[i]),255,1)
        cv2.line(img,tuple(p1[i]),tuple(p3[i]),255,1)

    img = (binary_fill_holes(img==255)*255).astype(np.uint8)   
    if int(cv2.__version__.split('.')[0])>=3:
        _,contours,hierarchy = cv2.findContours(img.copy(),cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
    else:
        contours,hierarchy = cv2.findContours(img.copy(),cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)

    cont = contours[0][:,0]        
    f1,f2 = cKDTree(cont).query(c,k=1)
    ordered_points = a[f2.argsort()[::-1]]

    if DEBUG_PLOT==1:
        NPOINTS = len(ordered_points)
        for i in range(NPOINTS):
            plt.plot(ordered_points[i:i+2,0],ordered_points[i:i+2,1],alpha=float(i)/(NPOINTS-1),color='k')
        plt.show()
    return ordered_points

示例运行 -

# Load data in a 2D array with 2 columns
a = np.loadtxt('random_shape.csv',delimiter='  ')
ordered_a = counter_clockwise_order(a, DEBUG_PLOT=1)

输出 -

- Divakar

Answer 8

有点晚了，但我遇到了一个类似的问题，由于数据中有很多悬挂/凹陷部分，无法使用质心概念。与Divakar的答案类似，我使用了Pandas来进行点之间的间距排序。思路是计算一个点与所有其他数据点之间的距离，距离最短的数据点被视为下一个邻居。

实现如下：

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np

df = pd.read_csv('data.csv', headers=None)

#  Creating blank lists for XY data
x = []
y = []

# Creating list with first entry being the desired starting point
l=[[df.iloc[0][0],df.iloc[1][0]]]

# Creating dataframe that does not contain the starting point
df2=df.iloc[1:]

# Iterating through each data point
for i in l:
    # Once the list reaches the same length as the original dataframe the
    # process has examined all data points and breaks
    if len(l) == len(df):
        break

    else:
        # Calculating the distance to each point
        d = np.sqrt((df2[0]-i[0])**2+(df2[1]-i[1])**2)
    
        # Removing any duplicates to the current point
        dd = d[d!=0]
    
        # Setting a minimum distance threshold for the points,
        # helps to deal with noisy data and should be adjusted to your data
        if d.min()<5:        
        
            # Adding the sorted X & Y data to lists for easy plotting
            x.append(df2.loc[dd.idxmin()][0])
            y.append(df2.loc[dd.idxmin()][1])
       
            # Adding the next data point for analysis to the list
            l.append([df2.loc[dd.idxmin()][0],df2.loc[dd.idxmin()][1]])
        
            # Removing the current datapoint from the dataframe to prevent
            # multiple analysis
            df2=df2.drop(index=dd.idxmin())

# plotting the sorted data
plt.plot(x,y)
plt.scatter(x,y,c='r')

绘制原始数据如下所示： 原始数据 现在，排序后的数据如下所示： 排序数据 我发现这种方法对于界面图像非常有用，因为它们可能存在很多重叠的特征，就像这张波浪图像一样： 波浪图像 当使用像ImageJ这样的程序将其转换为XY坐标时，绘制的数据如下所示： 原始波浪XY数据 使用这种方法成功地对数据进行了排序，因此您会得到以下结果： 排序波浪XY数据

- TiFighter64