如何按逆时针排序矩形的坐标列表？

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

给每个点关联一个角度（相对于一个内部点），这样移动起来就简单多了。

要计算这个角度，可以先找出形状的中心点，比如说，(average_lat, average_lng) 就是在中心。然后，使用 atan2(lng - average_lng, lat - average_lat) 就能得到那个点的角度。

Answer 2

假设你的“矩形”总是与赤道和经线平行（这就是你的例子所暗示的，但没有明确说明），也就是说，你只有两对不同的纬度和经度值： (lat0, lat1) 和 (lng0, lng1)。

这样你就可以得到以下四个角：

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 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) 周围加上括号是很重要的，这样才能得到正确的结果。