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

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
]

我需要逆时针对它们进行排序并将"锚点"/起点改为东北方向:

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

解决方案似乎非常简单:

>>> 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)的括号对于获得有效结果很重要.

Answer 2

假设你的"矩形"总是与赤道和经线平行(这就是你的例子所暗示的,但它没有明确说明),即你只有两对不同的lat和lng值:(lat0,lat1)和(lng0, lng1).

你得到以下4个角落:

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代码)