python - 如何逆时针对矩形的坐标列表进行排序？

Question

我需要对一个矩形的坐标列表进行逆时针排序，并使东北角成为第一个坐标。这些是十进制形式的地理坐标(即经度、纬度)。¹

例如，这是一个矩形的 4 个角，从西北角开始顺时针移动:

[
  { "lat": 34.495239, "lng": -118.127747 }, # north-west
  { "lat": 34.495239, "lng": -117.147217 }, # north-east
  { "lat": 34.095174, "lng": -117.147217 }, # south-east
  { "lat": 34.095174, "lng": -118.127747 }  # south-west
]

我需要逆时针排序并将“ anchor ”/起点更改为东北:

[
  { "lat": 34.495239, "lng": -117.147217 }, # north-east
  { "lat": 34.495239, "lng": -118.127747 }, # north-west
  { "lat": 34.095174, "lng": -118.127747 }, # south-west
  { "lat": 34.095174, "lng": -117.147217 }  # south-east
]

我不知道列表最初的顺序是什么(即顺时针或逆时针)。我不知道列表中的第一个坐标代表哪个角。

---

¹_{当映射到地球表面时，这不是真正的矩形，但是由于我确实有 2 个相对的角，为了便于阅读，我将其称为矩形。包裹 +180/-180 经度或 +90/-90 纬度的形状不是问题。}

Answer 1

解决方案似乎很简单:

>>> import math
>>> mlat = sum(x['lat'] for x in l) / len(l)
>>> mlng = sum(x['lng'] for x in l) / len(l)
>>> def algo(x):
    return (math.atan2(x['lat'] - mlat, x['lng'] - mlng) + 2 * math.pi) % (2*math.pi)

>>> l.sort(key=algo)

基本上，algo 将输入归一化到 [0, 2pi] 空间，它会自然地“逆时针”排序。请注意，% 运算符和 * 运算符具有相同的优先级，因此 (2*math.pi) 周围的括号对于获得有效结果很重要。