我有一组点，这些点的x和y坐标可以在下面的图中看到。九个点的坐标如下列表所示：
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]]
用一些三角函数并不难。也许你知道两个（标准化的）向量之间的角度是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 建议。lenvector和angle进行排序”，但现在我仔细阅读后，我看到这就是您的angle函数正在做的。我能否建议重命名您的函数？我几乎会称其为“矩形到极坐标”，但您的系统比极坐标对这个问题更有用。为您的排序函数取一个类似的名称将有助于避免混淆。 - Scott Mermelsteinatan2 应该足以表示 0 到 360（或 0 到 2*math.pi）之间的所有角度。 - MSeifert这应该说明问题，并提供可视化工具。
但是，对于在相同距离处获取一组点的正确入口点，它并不总是有效。
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)]
