如何在python中按顺时针方向排列庞大的二维坐标列表？

Question

我想使用 python 按顺时针方向排列二维坐标列表。我发现了类似的问答，它适用于小规模数据。我有一个大约 200k 点的坐标列表，并尝试执行相同的代码，但它无法执行。

    from functools import reduce
    import operator
    import math

    coords = [(1,1),(3,2),...] # Around 200k points    
    coords = list(dict.fromkeys(coords))
    center = tuple(map(operator.truediv, functools.reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
    final_list = (sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360))

上面代码中计算中心失败，程序自动退出。对于庞大的坐标列表，保存和计算有什么要改变的吗？

Answer 1

一种方法是首先按角度对坐标进行参数化。像这样：

centroid = sum(points)/len(points)
angles = map(lambda x: -atan2(x[1], x[0]), points)
tuples_to_sort = zip(angles, points)
sorted_points = map(lambda x: x[1], sorted(tuples_to_sort))

之所以有效，是因为： 1. 角度只是从原点来的角度。 2. 我们构造一个元组列表，其中第一个元素是角度，第二个元素是点。我们这样做是为了稍后对其进行排序，并且对元组的排序是逐个元素执行的，因此它将按角度排序。 3.我们得到了我们想要的原始积分。

但是，您是说可能存在性能问题，因此您可以尝试使用 numpy 进行计算。 Numpy 更快，因为它在引擎盖下使用较低级别的概念，并且针对进行高效的数组计算进行了优化。下面是上面使用 numpy 编写的简单版本。

import numpy as np

coords = np.array(coords)
center = coords.mean(axis=0)
centered = coords - center
angles = -np.arctan2(centered[:,1], centered[:,0])
sorted_coords = coords[np.argsort(angles)]
result = coords + center

您显然可以让它更简洁，并为变量提供更合适的名称，但它应该可以工作，而且应该更快一点。

如何在python中按顺时针方向排列庞大的二维坐标列表？

How to arrange the huge list of 2d coordinates in a clokwise direction in python?

python

map-function

functools