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

Question

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

例如，以下是矩形的四个角，从西北角开始并顺时针移动：

[
  { "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
]

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

[
  { "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
]

我不知道列表最初的顺序（即顺时针或逆时针）。我不知道列表中第一个坐标代表哪个角。

---

¹_{当映射到地球表面时，这不是一个真正的矩形，但是因为我有两个相反的角，所以我称它为矩形以便于阅读。环绕+180/-180经度或+90/-90纬度的形状不是问题。}

Answer 1

假设你的“矩形”总是平行于赤道和子午线（这就是你的例子所暗示的，但没有明确说明），即你只有两对不同的纬度和液化天然气值：（纬度0，纬度1）和（纬度0，纬度1）。

你可以得到以下四个角：

NE: (lat = max(lat0, lat1), lng = max(lng0, lng1))
NW: (lat = max(lat0, lat1), lng = min(lng0, lng1))
SW: (lat = min(lat0, lat1), lng = min(lng0, lng1))
SE: (lat = min(lat0, lat1), lng = max(lng0, lng1))

（这不应该是python代码）

Answer 2

你只需要按照你想要的顺序“重建”矩形，而不是排序。

从原始集合中，收集最小和最大纬度以及最小和最大经度。然后按任意顺序构造矩形。

西北角是最大纬度和最小经度。西南角是最小纬度和最小经度。等等

Answer 3

解决方案似乎非常简单：

>>> 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）周围的括号对于获得有效结果很重要。