按顺时针顺序对点进行排序

Question

我试图按顺时针顺序对（x，y）点列表进行排序。我试图在这个站点https://www.baeldung.com/cs/sort-points-clockwise上用Python算法实现，但我不太明白排序函数是如何与函数一起用作参数的。我尝试使用sorted（）Python函数，但没有成功。有人能给我一些提示吗？我如何在Python中实现这一点

part of sort clockwise algorithm

Answer 1

该站点上概述的算法很容易实现：

import math
import statistics
import random

# Generate random points – the parameters to random.uniform are chosen arbitrarily,
# but we just want to make sure we need to do some work at centering the points.
points = [(random.uniform(3, 10), random.uniform(-11, 1)) for x in range(10)]

# Use the "zip splat" trick to transpose the list of 2-tuple coordinates into 2 tuples
xs, ys = zip(*points)

# Get the average of the points as an estimate of the center
x_center = statistics.mean(xs)
y_center = statistics.mean(ys)


# Define a sorting function:
def sort_pt(point):
    # Destructure the point to x and y
    x, y = point

    # Translate the points according to the estimated center
    x -= x_center
    y -= y_center

    # Get the angle of this point from the estimated center
    angle = math.atan2(y, x)

    # Get the distance squared of this point from the estimated center
    dist = (x ** 2) + (y ** 2)

    # Return a 2-tuple; Python will use the values in order for sorting.
    # This means that things are primarily sorted by angle, and in case of a tie
    # (which is unlikely if the coordinates are not integer), the distance.
    # We reverse the angle here since `atan2` returns counter-clockwise coordinates;
    # using `reverse` in `sorted()` would also reverse the `dist` factor.
    return (-angle, dist)


# Sort the points using `sorted` using the above function as a key.
sorted_points = sorted(
    points,
    key=sort_pt,
)

print(points)
print(sorted_points)

Answer 2

在Python中，不能传递sorted（或sort）一个比较两个值的直接比较函数，但可以传递一个key函数，该函数将单个值转换为可以使用常规数字或字符串比较进行比较的值，以获得所需的结果。例如，在这种情况下，您可以编写一个函数，该函数将获取一个点并返回该点的角度：

import math
def angle_to(point):
  # assumes already mapped to (0,0) center
  # modify as needed to get result in desired range
  return math.atan2(point[1],point[0])

然后按如下方式对列表进行排序：

# reverse=True for clockwise, since conventional math angles increase
# going counter-clockwise
sorted_points = sorted(points_list, key=angle_to, reverse=True)