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

问题描述

我有一组带有 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 语言中针对此问题的算法、脚本或方法有什么想法吗?

解决方案

有了一点三角学，这并不难.也许你知道，但两个(归一化)向量之间的角度是 acos(vec1 * vec2).然而，这仅计算投影角度，但可以使用 atan2 来计算方向感知角度.

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

导入数学pts = [[2,3], [5,2],[4,1],[3.5,1],[1,2],[2,1],[3,1],[3,3],[4,3]]原点 = [2, 3]refvec = [0, 1]定义顺时针角度和距离(点):# 点和原点之间的向量:v = p - o向量 = [point[0]-origin[0], point[1]-origin[1]]# 向量长度: ||v||lenvector = math.hypot(vector[0], vector[1])# 如果长度为零，则没有角度如果 lenvector == 0:返回 -math.pi, 0# 归一化向量:v/||v||归一化 = [vector[0]/lenvector, vector[1]/lenvector]dotprod = 归一化[0]*refvec[0] + 归一化[1]*refvec[1] # x1*x2 + y1*y2diffprod = refvec[1]*normalized[0] - refvec[0]*normalized[1] # x1*y2 - y1*x2角度 = math.atan2(diffprod, dotprod)# 负角代表逆时针角度，所以我们需要减去它们# 来自 2*pi(360 度)如果角度＜0:返回 2*math.pi+angle, lenvector# 我首先返回角度，因为这是主要的排序标准# 但如果两个向量具有相同的角度，那么较短的距离应该先出现.返回角，透镜向量

A sorted 运行:

<预><代码>>>>排序(点，键=顺时针角度和距离)[[2, 3], [3, 3], [4, 3], [5, 2], [4, 1], [3.5, 1], [3, 1], [2, 1], [1, 2]]

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

<预><代码>>>>原点 = [2,3]>>>refvec = [0, 1]>>>pts = [[1,4],[2,4],[3,4],[1,3],[2,3],[3,3],[1,2],[2,2],[3,2]]>>>排序(点，键=顺时针角度和距离)[[2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [2, 2], [1, 2], [1, 3], [1, 4]]

即使你改变了参考向量:

<预><代码>>>>原点 = [2,3]>>>refvec = [1,0] # 向右而不是向上>>>pts = [[1,4],[2,4],[3,4],[1,3],[2,3],[3,3],[1,2],[2,2],[3,2]]>>>排序(点，键=顺时针角度和距离)[[2, 3], [3, 3], [3, 2], [2, 2], [1, 2], [1, 3], [1, 4], [2, 4], [3, 4]]

感谢 @Scott Mermelstein 提供更好的函数名称和 @f5r5e5d 对 atan2 的建议.

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.

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

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

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

解决方案

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.

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

A sorted run:

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

even if you change the reference vector:

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

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

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