按照顺时针点坐标排序

Question

给定一个Python列表，包含4个点的8个x,y坐标值（全部为正数），如[x1, x2, x3, x4, y1, y2, y3, y4]（(xi, yi)是第i个点的x和y坐标）， 如何对其进行排序，使新的列表[a1, a2, a3, a4, b1, b2, b3, b4]中1，2，3，4的坐标(ai, bi)按顺序在xy平面上以顺时针方向排列，其中1最靠近原点，即像这样

          2--------3
          |        |
          |        |
          |        |
          1--------4

点的大致形状将为平行四边形。

目前，我的想法是将具有最小值（x+y）的点作为1，然后在其余坐标中找到最小x的点作为2，通过最大值（x+y）找到3，并将剩下的点作为4。

- john doe

---

从中心获取atan2。 - Ignacio Vazquez-Abrams

不需要直接计算角度。只需使用二维叉积的符号作为比较器对它们进行排序即可。 - meowgoesthedog

@meowgoesthedog 那个方案也可以，但是与计算角度相比，效率不会很高，因为使用2D叉积的符号意味着需要一次比较列表中的两个坐标，这需要使用cmp函数。计算角度意味着我们可以将它们用作key参数的比较值，这更加高效。请参阅为什么在Python3.0中删除了sort/sorted的cmp参数？ - blhsing

@meowgoesthedog 二话不说，那样做是行不通的，因为对于列表上的每个坐标，总会有另一个坐标，其向质心的矢量是顺时针于该坐标的矢量，因此没有“底部”可供比较。在 OP 的情况下，我们需要将 -135 度作为坐标排序列表的“底部”。2D 叉积的符号只能帮助确定一个向量是否顺时针于另一个向量，但不能帮助确定一个向量距离“底部”（即 -135 度）有多远。 - blhsing

@meowgoesthedog 我不太确定你对点的顺序唯一性和数组旋转的意思（很想看看你的逻辑伪代码），但我刚刚意识到，对于两个方向相反的向量，叉积将为零（没有符号），与两个方向相同的向量相同，因此我们无法使用叉积对这两组向量进行排序。 - blhsing

Answer 1

你应该使用一个由两个元素组成的元组列表作为数据结构，以有意义的方式表示可变数量的坐标。

from functools import reduce
import operator
import math
coords = [(0, 1), (1, 0), (1, 1), (0, 0)]
center = tuple(map(operator.truediv, reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
print(sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360))

这将输出：

[(0, 0), (0, 1), (1, 1), (1, 0)]

- blhsing

---

请问您能否解释一下这个解决方案？ - user6038900

有必要转换为度数吗？这似乎会增加很多复杂性。 - Pablo

Answer 2

import math

def centeroidpython(data):
    x, y = zip(*data)
    l = len(x)
    return sum(x) / l, sum(y) / l

xy = [405952.0, 408139.0, 407978.0, 405978.0, 6754659.0, 6752257.0, 6754740.0, 6752378.0]
xy_pairs = list(zip(xy[:int(len(xy)/2)], xy[int(len(xy)/2):]))

centroid_x, centroid_y = centeroidpython(xy_pairs)
xy_sorted = sorted(xy_pairs, key = lambda x: math.atan2((x[1]-centroid_y),(x[0]-centroid_x)))
xy_sorted_x_first_then_y = [coord for pair in list(zip(*xy_sorted)) for coord in pair]

- BERA

Answer 3

# P4=8,10 P1=3,5   P2=8,5   P3=3,10
points=[8,3,8,3,10,5,5,10]
k=0
#we know these numbers are extreme and data won't be bigger than these
xmin=1000
xmax=-1000
ymin=1000
ymax=-1000
#finding min and max values of x and y
for i in points:
    if  k<4:
        if (xmin>i): xmin=i
        if (xmax<i): xmax=i        
    else:
        if (ymin>i): ymin=i
        if (ymax<i): ymax=i        
    k +=1

sortedlist=[xmin,xmin,xmax,xmax,ymin,ymax,ymax,ymin]
print(sortedlist)

输出结果：[3, 3, 8, 8, 5, 10, 10, 5] 对于其他区域，您需要更改sortedlist行。如果中心在框内，则需要更多的条件控制。

- Hamid Mir

Answer 4

我们希望按照从起始坐标开始的角度进行排序。我在这里使用了numpy将每个向量从起始坐标解释为一个复数，对于复数有一种简单的方法来计算角度（沿着单位球逆时针方向）。

def angle_with_start(coord, start):
    vec = coord - start
    return np.angle(np.complex(vec[0], vec[1]))

完整代码：

import itertools
import numpy as np


def angle_with_start(coord, start):
    vec = coord - start
    return np.angle(np.complex(vec[0], vec[1]))


def sort_clockwise(points):
    # convert into a coordinate system
    # (1, 1, 1, 2) -> (1, 1), (1, 2)
    coords = [np.array([points[i], points[i+4]]) for i in range(len(points) // 2)]

    # find the point closest to the origin,
    # this becomes our starting point
    coords = sorted(coords, key=lambda coord: np.linalg.norm(coord))
    start = coords[0]
    rest = coords[1:]

    # sort the remaining coordinates by angle
    # with reverse=True because we want to sort by clockwise angle
    rest = sorted(rest, key=lambda coord: angle_with_start(coord, start), reverse=True)

    # our first coordinate should be our starting point
    rest.insert(0, start)
    # convert into the proper coordinate format
    # (1, 1), (1, 2) -> (1, 1, 1, 2)
    return list(itertools.chain.from_iterable(zip(*rest)))

在一些样本输入上的行为:

In [1]: a
Out[1]: [1, 1, 2, 2, 1, 2, 1, 2]

In [2]: sort_clockwise(a)
Out[2]: [1, 1, 2, 2, 1, 2, 2, 1]

In [3]: b
Out[3]: [1, 2, 0, 2, 1, 2, 3, 1]

In [4]: sort_clockwise(b)
Out[4]: [1, 0, 2, 2, 1, 3, 2, 1]

- captaincapsaicin

Answer 5

基于BERA的回答，但作为一个类：

代码

import math

def class Sorter:
    @staticmethod    
    def centerXY(xylist):
        x, y = zip(*xylist)
        l = len(x)
        return sum(x) / l, sum(y) / l  

    @staticmethod    
    def sortPoints(xylist):  
        cx, cy = Sorter.centerXY(xylist)
        xy_sorted = sorted(xylist, key = lambda x: math.atan2((x[1]-cy),(x[0]-cx)))
        return xy_sorted

测试

def test_SortPoints():
    points=[(0,0),(0,1),(1,1),(1,0)]
    center=Sorter.centerXY(points)
    assert center==(0.5,0.5)
    sortedPoints=Sorter.sortPoints(points)
    assert sortedPoints==[(0, 0), (1, 0), (1, 1), (0, 1)]

- Wolfgang Fahl

Answer 6

如IgnacioVazquez-Abrams所建议的，我们也可以根据atan2角度进行排序：

代码：

import math
import copy
import matplotlib.pyplot as plt

a = [2, 4, 5, 1, 0.5, 4, 0, 4]
print(a)


def clock(a):
    angles = []
    (x0, y0) = ((a[0]+a[1]+a[2]+a[3])/4, (a[4]+ a[5] + a[6] + a[7])/4)  # centroid
    for j in range(4):
        (dx, dy) = (a[j] - x0, a[j+4] - y0)
        angles.append(math.degrees(math.atan2(float(dy), float(dx))))
    for k in range(4):
        angles.append(angles[k] + 800)
    # print(angles)

    z = [copy.copy(x) for (y,x) in sorted(zip(angles,a), key=lambda pair: pair[0])]
    print("z is: ", z)

plt.scatter(a[:4], a[4:8])
plt.show()

clock(a)

输出结果为：

[2, 4, 5, 1, 0.5, 4, 0, 4]
[-121.60750224624891, 61.92751306414704, -46.73570458892839, 136.8476102659946, 678.3924977537511, 861.9275130641471, 753.2642954110717, 936.8476102659946]
z is:  [2, 5, 4, 1, 0.5, 0, 4, 4]

- john doe

Answer 7

尝试这行代码

def sort_clockwise(pts):
    rect = np.zeros((4, 2), dtype="float32")
    s = pts.sum(axis=1)
    rect[0] = pts[np.argmin(s)]
    rect[2] = pts[np.argmax(s)]
    diff = np.diff(pts, axis=1)
    rect[1] = pts[np.argmin(diff)]
    rect[3] = pts[np.argmax(diff)]
    return rect

- Prashant