如何在Python中按顺时针/逆时针方向对点列表进行排序？

我得到了坐标点列表，我想按顺时针/逆时针对它们进行排序。

这是我提到的清单：
[(985, 268), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (986, 0), (830, 0), (983, 230), (998, 425), (998, 255)]

这些坐标点将帮助我绘制物体的线段。下面是用于说明的图像。正如您所看到的，我已经标记了该图像列表中的所有点。

我的目标是对这些坐标点进行排序，以创建多个线段。因此，我的预期结果如下：
逆时针方向：[(985, 268), (998, 425), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (998, 255), (986, 0), (983, 230), (830, 0)]

顺时针方向：[(985, 268), (830, 0),(983, 230), (986, 0), (998, 255), (1161, 443), (1196, 477), (1279, 577), (1018, 453), (998, 448), (112, 316), (998, 425)]

到目前为止，我已经建立了一个网站，https://www.baeldung.com/cs/sort-points-顺时针 https://www.baeldung.com/cs/sort-points-clockwise，作为参考并编写了以下代码，但它不起作用：

def getDistance(pt1 , pt2):
    x = pt1[0] - pt2[0]
    y = pt1[1] - pt2[1]
    return math.sqrt(x*x+y*y)

def getAngle(pt_center, pt):
    x = pt[0] - pt_center[0]
    y = pt[1] - pt_center[1]
    angle = math.atan2(y,x)

    if angle <= 0:
        angle = 2*math.pi + angle

    return angle

def comparePoints(pt_center, pt1, pt2):
    angle1 = getAngle(pt_center, pt1)
    angle2 = getAngle(pt_center, pt2)

    if angle1 < angle2:
        return True

    d1 = getDistance(pt_center, pt1)
    d2 = getDistance(pt_center, pt2)

    if angle1 == angle2 and d1 < d2:
        return True

    return False

final_concave_points_list = []
for items in final_concave_points:
    final_concave_points_list.append([])
    for points in items:
        final_concave_points_list[-1].append(list(points))

pt_center = [0,0]
point = []
points = final_concave_points_list[0]
for pt in points:
    pt_center[0] = pt_center[0] + pt[0]
    pt_center[1] = pt_center[1] + pt[1]

pt_center[0] = pt_center[0] / len(points)
pt_center[1] = pt_center[1] / len(points)

for pt in points:
    pt[0] = pt[0] - pt_center[0]
    pt[1] = pt[1] - pt_center[1]
    point.append((pt[0], pt[1]))
print(point)

'''
[(23.0, -56.333333333333314), (-850.0, -8.333333333333314), (36.0, 123.66666666666669), (56.0, 128.66666666666669), (317.0, 252.66666666666669), (234.0, 152.66666666666669), (199.0, 118.66666666666669), (24.0, -324.3333333333333), (-132.0, -324.3333333333333), (21.0, -94.33333333333331), (36.0, 100.66666666666669), (36.0, -69.33333333333331)]
'''

points = scaled_point_list[0]
angle_list = []
for concave in points:
    angle = getAngle((0,0), concave)
    angle_list.append(angle)
print(angle_list)

'''
[5.102097551727555, 3.15100414040828, 1.2882413743253092, 1.1612360403462985, 0.6735857636846376, 0.5790742693677309, 0.5389402114087971, 4.78632801804263, 4.325513262653661, 4.932184051908722, 1.2283997388640362, 5.193276260580025]
'''

zipped_list = zip(angle_list, points)
sorted_zipped_lists = sorted(zipped_list)
sorted_list1 = [element for _, element in sorted_zipped_lists]
print(sorted_list1)

'''
[(199, 119), (234, 153), (317, 253), (56, 129), (36, 101), (36, 124), (-850, -8), (-132, -324), (24, -324), (21, -94), (23, -56), (36, -69)]
'''

虽然我将中心点（962, 324）添加回上述每个点，但它们仍然不是期望的结果。

多谢。

我已经在评论中链接了 7 个相关/重复的问题。这些问题通过几种不同的方法得到了有趣的答案。两种主要方法是“计算凸包”方法和“围绕中心”方法。

由于 Danielhao 已经发布了凸包方法的答案，所以让我用中心方法给出答案。

基本算法如下：

• 定义一个新点C，称为中心； C 可能是任何东西，并且 C 的精确选择将影响结果，特别是如果由点定义的多边形不是凸的。 C 的一个简单选择是取点列表的重心（即取列表中坐标的平均值）。
• 对于列表中的每个点 P，计算 x 轴和矢量 CP 之间的定向角 alpha_P。
• 按相关角度对点列表进行排序；逆时针方向按递增顺序，顺时针方向按递减顺序。

python中的实现：

import matplotlib.pyplot as plt  # plot, show
import math                      # atan2

points = [(985, 268), (112, 316), (998, 448), (1018, 453), (1279, 577), (1196, 477), (1161, 443), (986, 0), (830, 0), (983, 230), (998, 425), (998, 255)]

def sort_counterclockwise(points, centre = None):
  if centre:
    centre_x, centre_y = centre
  else:
    centre_x, centre_y = sum([x for x,_ in points])/len(points), sum([y for _,y in points])/len(points)
  angles = [math.atan2(y - centre_y, x - centre_x) for x,y in points]
  counterclockwise_indices = sorted(range(len(points)), key=lambda i: angles[i])
  counterclockwise_points = [points[i] for i in counterclockwise_indices]
  return counterclockwise_points

我强烈鼓励您使用不同的中心坐标值，看看这如何影响点的最终顺序。

points = sort_counterclockwise(points)
plt.plot([x for x,_ in points], [y for _,y in points])
plt.show()

points = sort_counterclockwise(points, (0,0))
plt.plot([x for x,_ in points], [y for _,y in points])
plt.show()

points = sort_counterclockwise(points, (1000, 200))
plt.plot([x for x,_ in points], [y for _,y in points])
plt.show()