使用Python按顺时针方向对二维坐标列表进行排序? [英] Sorting list of two-dimensional coordinates by clockwise angle using Python?

问题描述

我有一组带有x和y坐标的点，可以在下图中看到. 9个点的坐标存储在列表中，如下所示:

I have a set of points with x and y coordinates that can be seen in the figure below. The coordinates of the 9 points were stored in a list as follows:

L = [[5,2], [4,1], [3.5,1], [1,2], [2,1], [3,1], [3,3], [4,3] , [2,3]]

想法是从原点开始按顺时针方向对点进行排序.在这种情况下，原点是彩色的点，并且具有指示订购方向的箭头.不必担心创建确定原点的方法，因为它已经解决了.

The idea is to sort the points clockwise from an origin. In this case, the origin is the point that is colored and that has an arrow that indicates the direction of the ordering. Do not worry about creating methodology to determine the origin because it is already solved.

因此，订购后，列表L应如下所示:

Thus, after being ordered, the list L should be as follows:

L = [[2,3], [3,3], [4,3], [5,2], [4,1], [3.5,1], [3,1], [2,1], [1,2]]

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

Note that the x and y coordinates are not changed. What changes is the storage order.

您对使用python语言解决此问题的算法，脚本或方法学有所了解吗?

Do you have any idea of an algorithm, script or methodology for this problem in the python language?

推荐答案

有了一点三角函数，就不那么困难了.也许您知道，但是两个(规范化)向量之间的夹角为acos(vec1 * vec2).但是，这仅计算投影角度，但可以使用atan2来计算方向感知角度.

With a bit of trigonometry it's not that hard. Maybe you know but the angle between two (normalized) vectors is acos(vec1 * vec2). However this calculates only the projected angle but one could use atan2 to calculate the direction-aware angle.

这意味着一个函数可以对其进行计算，然后将其用作key进行排序将是一个好方法:

To this means a function calculating it and then using it as key for sorting would be a good way:

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

，并且在原点周围有一个矩形网格，它也可以按预期工作:

and with a rectangular grid around the origin this works as expected as well:

>>> 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建议.

Thanks @Scott Mermelstein for the better function name and @f5r5e5d for the atan2 suggestion.

这篇关于使用Python按顺时针方向对二维坐标列表进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！