Сортировка данных по x, y против часовой стрелки

Question

У меня есть набор точек в текстовом файле: random_shape.dat. Начальный порядок точек в файле является случайным. Я хотел бы отсортировать эти точки в порядке против часовой стрелки следующим образом (красные точки - данные xy):

Данные xy можно найти здесь

Я пытался добиться этого, используя полярные координаты: я вычисляю полярный угол каждой точки (x,y), а затем сортирую по возрастанию углов следующим образом:

"""
Script: format_file.py
Description: This script will format the xy data file accordingly to be used with construct2d, 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, который содержит отсортированные данные в соответствии с изображением выше (первая строка содержит начальную точку, следующие строки содержат точки, показанные синими стрелками в направлении против часовой стрелки на изображении).

Answer 1

Для точек с сопоставимыми расстояниями между соседними пунктами мы можем использовать 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)

Выход -

Answer 2

Если мы хотим ответить на вашу конкретную проблему , нам нужно выбрать опорную точку.

Так как вы хотите отсортировать по выбранной отправной точке, я бы выбрал опорную точкув середине (x = 4, y = 0 подойдет).

Так как мы сортируем против часовой стрелки, мы возьмем arctan2 (- (y-pivot_y), - (x-center_x)) (мыпереворачиваем ось х).

Мы получаем следующее с разбросанным по градиенту цветным разбросом, чтобы доказать правильность (к сожалению, я удалил первую строку файла данных после загрузки):

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 по порядку:

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), чтобы это работало.

Answer 4

Я не думаю, что это вопрос Python, но, тем не менее, я думаю, что вы можете попробовать сортировку, если - sign(y) * x сделать что-то вроде:

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

должно работать нормально, при условии, что вы правильно прочитали свои пункты в спискеdicts формата {'x': 0.12312, 'y': 0.912}

РЕДАКТИРОВАТЬ: Это будет работать, пока вы пересекаете ось X только дважды, как в вашем примере.

Answer 5

Заказ против часовой стрелки зависит от выбора точки разворота. Из вашего вопроса, один хороший выбор точки поворота - это центр масс.

Примерно так:

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

Answer 6

Если:

• форма произвольно сложна и
• интервал между точками ~ случайный

, тогда я думаю, что это действительно сложная проблема.

Для чего бы это ни стоило, я сталкивался с подобной проблемой в прошлом, и я использовал решатель коммивояжера. В частности, я использовал решатель LKH . Я вижу, что есть репозиторий Python для решения проблемы, LKH-TSP. Как только вы получите приказ по пунктам, я не думаю, что будет слишком сложно определиться с порядком по часовой стрелке против часовой.

Answer 7

Я считаю, что простой способ сортировки точек с такими координатами x, y состоит в том, чтобы сортировать их в зависимости от угла между линией от точек и центром масс всего многоугольника и горизонтальной линией, которая называетсяalpha в примере. Координаты центра масс (x0 и y0) можно легко рассчитать путем усреднения координат x, y всех точек. Затем вы рассчитываете угол, используя, например, 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

Построение x, y перед сортировкой с использованием matplotlib.pyplot.plot (точки явно не отсортированы):

Построение x, y с использованием matplotlib.pyplot.plot после сортировки с помощью этого метода: