python - 使用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 语言解决此问题的算法、脚本或方法？

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