Сортировка списка двумерных координат по часовой стрелке с помощью Python?

Question

У меня есть набор точек с координатами x и y, которые можно увидеть на рисунке ниже. Координаты 9 пунктов были сохранены в списке следующим образом:

L = [[5,2], [4,1], [3.5,1], [1,2], [2,1], [3,1], [3,3], [4,3] , [2,3]] 

Идея заключается в том, чтобы сортировать точки по часовой стрелке от начала координат. В этом случае начало координат - это точка, которая окрашена и имеет стрелку, указывающую направление упорядочения. Не беспокойтесь о создании методологии для определения происхождения, потому что она уже решена.

Таким образом, после того, как упорядоченный список L должен выглядеть следующим образом:

L = [[2,3], [3,3], [4,3], [5,2], [4,1], [3.5,1], [3,1], [2,1], [1,2]] 

Обратите внимание, что х и у координаты не изменяются. Какие изменения внесены в порядок хранения.

Есть ли у вас какое-либо представление об алгоритме, скрипте или методологии для этой проблемы на языке python?

Answer 1

С немного тригонометрии это не так уж трудно. Возможно, вы знаете, но угол между двумя (нормализованными) векторами равен acos(vec1 * vec2). Однако это вычисляет только проецируемый угол, но можно использовать atan2 для расчета угла направления.

Чтобы это означает функцию вычисления его, а затем использовать его в качестве key для сортировки было бы хорошим способом:

import math 

pts = [[2,3], [5,2],[4,1],[3.5,1],[1,2],[2,1],[3,1],[3,3],[4,3]] 
origin = [2, 3] 
refvec = [0, 1] 

def clockwiseangle_and_distance(point): 
    # Vector between point and the origin: v = p - o 
    vector = [point[0]-origin[0], point[1]-origin[1]] 
    # Length of vector: ||v|| 
    lenvector = math.hypot(vector[0], vector[1]) 
    # If length is zero there is no angle 
    if lenvector == 0: 
     return -math.pi, 0 
    # Normalize vector: v/||v|| 
    normalized = [vector[0]/lenvector, vector[1]/lenvector] 
    dotprod = normalized[0]*refvec[0] + normalized[1]*refvec[1]  # x1*x2 + y1*y2 
    diffprod = refvec[1]*normalized[0] - refvec[0]*normalized[1]  # x1*y2 - y1*x2 
    angle = math.atan2(diffprod, dotprod) 
    # Negative angles represent counter-clockwise angles so we need to subtract them 
    # from 2*pi (360 degrees) 
    if angle < 0: 
     return 2*math.pi+angle, lenvector 
    # I return first the angle because that's the primary sorting criterium 
    # but if two vectors have the same angle then the shorter distance should come first. 
    return angle, lenvector 

sorted пробег:

>>> sorted(pts, key=clockwiseangle_and_distance) 
[[2, 3], [3, 3], [4, 3], [5, 2], [4, 1], [3.5, 1], [3, 1], [2, 1], [1, 2]] 

и с прямоугольной сетке вокруг происхождение это также работает как ожидалось:

>>> origin = [2,3] 
>>> refvec = [0, 1] 
>>> pts = [[1,4],[2,4],[3,4],[1,3],[2,3],[3,3],[1,2],[2,2],[3,2]] 
>>> sorted(pts, key=clockwiseangle_and_distance) 
[[2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [2, 2], [1, 2], [1, 3], [1, 4]] 

, даже если вы измените эталонный вектор:

>>> origin = [2,3] 
>>> refvec = [1,0] # to the right instead of pointing up 
>>> pts = [[1,4],[2,4],[3,4],[1,3],[2,3],[3,3],[1,2],[2,2],[3,2]] 
>>> sorted(pts, key=clockwiseangle_and_distance) 
[[2, 3], [3, 3], [3, 2], [2, 2], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]] 

Спасибо @Scott Mermelstein для лучшего названия функции и @f5r5e5d для atan2 предложения.

Answer 2

это должно иллюстрировать проблемы, дает инструмент визуализации

, но она не работает каждый раз для получать правильную точку входа для группы точек на том же расстоянии

import random 
import pylab 
import cmath 
from itertools import groupby 


pts = [(random.randrange(-5,5), random.randrange(-5,5)) for _ in range(10)] 

# for this problem complex numbers are just too good to pass up 

z_pts = [ i[0] + 1j*i[1] for i in pts if i != (0, 0)] 

z_pts.sort(key = lambda x: abs(x)) 

gpts = [[*g] for _, g in groupby(z_pts, key = lambda x: abs(x)) ] 
print(*gpts, sep='\n') 

spts = [1j/2] 

for e in gpts: 
    if len(e) > 1: 
     se = sorted(e, key = lambda x: cmath.phase(-x/spts[-1])) 
     spts += se 
    else: 
     spts += e 

print(spts) 

def XsYs(zs): 
    xs = [z.real for z in zs] 
    ys = [z.imag for z in zs] 
    return xs, ys 

def SpiralSeg(a, b): 
    ''' 
    construct a clockwise spiral segment connecting 
    ordered points a, b specified as complex numbers 

    Inputs 
     a, b complex numbers 
    Output 
     list of complex numbers 
    ''' 
    seg = [a] 
    if a == 0 or a == b: 
     return seg 
    # rotation interpolation with complex numbers! 
    rot = (b/a) ** (1/30) 
    # impose cw rotation direction constraint 
    if cmath.phase(b/a) > 0: # add a halfway point to force long way around 
     plr = cmath.polar(b/a) 
     plr = (plr[0]**(1/2), plr[1]/2 - 1 * cmath.pi) # the rotor/2 
     a_b = cmath.rect(*plr) * a # rotate the start point halfway round 
     return SpiralSeg(a, a_b) + (SpiralSeg(a_b, b)) 

    for _ in range(30): 
     a *= rot 
     seg.append(a) 
    return seg 

segs = [SpiralSeg(a, b) for a, b in zip(spts, spts[1:])] 

pylab.axes().set_aspect('equal', 'datalim') 

pylab.scatter(*XsYs(z_pts)) 
for seg in segs: 
    pylab.plot(*XsYs(seg)) 

[(1-2j), (-2-1j)] 
[(2-3j)] 
[(1+4j)] 
[(3+3j)] 
[(-3-4j), (3-4j), (4-3j)] 
[(1-5j)] 
[(-4-4j)] 
[0.5j, (-2-1j), (1-2j), (2-3j), (1+4j), (3+3j), (-3-4j), (3-4j), (4-3j), (1-5j), (-4-4j)] 



[-1j] 
[(-1-1j)] 
[(-1-2j), (-1+2j), (2+1j)] 
[(-4+0j)] 
[(1-4j)] 
[-5j, (-4-3j)] 
[(1-5j)] 
[0.5j, -1j, (-1-1j), (-1-2j), (2+1j), (-1+2j), (-4+0j), (1-4j), (-4-3j), -5j, (1-5j)]