numpy x，y数据的逆时针排序

plupiseo 于 2023-08-05 发布在其他

关注(0)|答案(8)|浏览(84)

我在一个文本文件中有一组要点：random_shape.dat。文件中点的初始顺序是随机的。我想按逆时针顺序对这些点进行排序，如下所示（红点是xy数据）：x1c 0d1x的数据
我试着用极坐标来实现：我计算每个点(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中没有得到预期的结果！这些点未按所需顺序排序。
任何帮助都是感激的。

EDIT：预期结果：

创建一个新文件，名为：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

型

numpy

来源：https://stackoverflow.com/questions/58377015/counterclockwise-sorting-of-x-y-data

8条答案

按热度按时间

mefy6pfw1#

我发现一个简单的方法来排序像这样的x，y坐标的点是根据从点到整个多边形质心的直线和水平线之间的Angular 来排序它们，在这个例子中称为alpha。质心的坐标（x0和y0）可以通过对所有点的x、y坐标进行平均来容易地计算。然后使用numpy.arccos计算Angular 。当y-y0大于0时，直接取Angular ，否则从360°中减去Angular （2𝜋）。我使用numpy.where计算Angular ，然后使用numpy.argsort生成索引初始x，y值的掩码。下面的函数sort_xy对所有x和y坐标相对于该Angular 进行排序。如果要从任何其他点开始，可以为此添加偏移Angular 。在你的情况下，这将是零。

的数据

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：

的

赞(0）回复(0）举报 2023-08-05

3lxsmp7m2#

如果确定曲线不穿过相同的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坐标中具有陡峭波动的曲线，对于该曲线，从某个中心点的Angular 环视将失败，如下所示：

的数据
不对X坐标和Y坐标的范围进行假设：例如，曲线不一定必须穿过X轴（Y = 0）才能起作用。

赞(0）回复(0）举报 2023-08-05

6yjfywim3#

逆时钟顺序取决于枢轴点的选择。从你的问题来看，一个很好的支点选择是质心。
大概是这样的：

# 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]

字符串

赞(0）回复(0）举报 2023-08-05

ar5n3qh54#

我认为这不是一个真正的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}的dicts列表中，应该可以正常工作
编辑：只要你只穿过X轴两次，就可以了，就像你的例子一样。

赞(0）回复(0）举报 2023-08-05

bq3bfh9z5#

如果：

该形状是任意复杂的，并且
点间距为~随机

那我觉得这是个很难的问题。
不管怎么说，我过去也遇到过类似的问题，我使用了一个旅行推销员求解器。特别是，我使用了the LKH solver。我看到有一个Python repo来解决这个问题，LKH-TSP。一旦你有了一个点的顺序，我不认为这将是太难决定顺时针与顺时针排序。

赞(0）回复(0）举报 2023-08-05

i1icjdpr6#

如果我们想回答您的具体问题，我们需要选择一个枢轴点。
因为你想根据你选择的起始点排序，我会在中间选择一个枢轴（x=4，y=0）。
由于我们是逆时针排序，我们将取arctan 2（-（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')

字符串
结果（在色彩Map表中，1为白色，0为黑色），它们按顺序在0-1范围内编号：
x1c 0d1x的数据

赞(0）回复(0）举报 2023-08-05

ego6inou7#

对于相邻点之间具有可比距离的点，我们可以使用KDTree来获得每个点的两个最近点。然后画线连接这些给予我们一个封闭的形状轮廓。然后，我们将使用OpenCV的findContours来始终以逆时针方式跟踪轮廓。现在，由于OpenCV处理图像，我们需要将数据从提供的float格式采样为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)

型
输出-
x1c 0d1x的数据

赞(0）回复(0）举报 2023-08-05

7eumitmz8#

有点晚的游戏，但我有一个类似的问题，不能使用质心的概念，由于大量的悬垂/削弱的数据。与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')

字符串
绘制原始数据如下所示：Raw Data
排序后的数据现在看起来像这样：Sorted Data
我发现这个方法对于界面的图像非常有用，这些界面可能有很多重叠的特征，比如下面的波浪图像：
Wave Image的
当使用ImageJ等程序将其转换为XY坐标时，绘制的数据如下所示：
Raw Wave XY Data的
使用此方法可以成功地对数据进行排序，因此您可以得到以下内容：
Sorted Wave XY Data的

赞(0）回复(0）举报 2023-08-05

我来回答

numpy x，y数据的逆时针排序

8条答案

相关问题

热门标签

最新问答