如何在 python 中以 clokwise 方向排列庞大的 2d 坐标列表?

Question

我想使用 python 顺时针方向排列 2d 坐标列表。我在这里找到了类似的问答，它适用于小规模数据。我有一个大约 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

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