使用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]]

请注意，x 和 y 坐标不会更改。改变的是存储顺序。

你知道用 python 语言解决这个问题的算法、脚本或方法吗？

原文由 Jayme Muzzi 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

A 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 建议。

原文由 MSeifert 发布，翻译遵循 CC BY-SA 3.0 许可协议

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

原文由 f5r5e5d 发布，翻译遵循 CC BY-SA 3.0 许可协议