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
]

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

[
  { "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 纬度的形状不是问题。}

score 10 · Accepted Answer

解决方案似乎很简单：

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

score 5 · Accepted Answer

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

你得到以下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代码）

score 3 · Accepted Answer

您可以按照您想要的任何顺序“重建”矩形，而不是排序。

从原始集合中，收集最小和最大纬度以及最小和最大经度。然后以您想要的任何顺序构建矩形。

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

score 3 · Accepted Answer

将每个点与一个角度相关联（相对于一个内部点），然后四处移动是微不足道的。

要计算角度，请在形状中间找到一个点，例如，(average_lat, average_lng)将在中心。然后，atan2(lng - average_lng, lat - average_lat)将是该点的角度。

score 1 · Accepted Answer

如果你从一个角取两个向量的叉积，那么结果的符号会告诉你它是顺时针还是逆时针。

score 1 · Accepted Answer

这很容易。首先，我们对坐标进行排序，以便我们知道它们的顺序，然后我们只需将它们挑选出来：

首先按 lat 然后按 lng 对它们进行排序，最大的在前。然后我们交换最后两个：

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


L = sorted(L, key=lambda k: (-k["lat"], -k["lng"]))

L[-2], L[-1] = L[-1], L[-2]
import pprint
pprint.pprint(L)

输出

[{'lat': 34.495238999999998, 'lng': -117.147217},
 {'lat': 34.495238999999998, 'lng': -118.127747},
 {'lat': 34.095174, 'lng': -118.127747},
 {'lat': 34.095174, 'lng': -117.147217}]

（key 函数的缺点在于，较大的值排在较小的值之前。通过排序，我们将北放在南之前，然后将东放在西之前；为了获得所需的顺序，我们只需交换最后两个（南）值。）

score 0 · Accepted Answer

所以，你有4分。

您总是从 NW 点开始。

你知道这些点是排序的，只是不是在哪个方向上。

这是列表是顺时针还是逆时针的前两点的简单测试。

如果 (pt1.y != pt2.y) 那么方向 = 顺时针。

如果您检测到这些点是顺时针方向的，只需反转列表中的最后 3 个点。

所以。

逆时针点：(0,1), (0,0), (1,0), (1,1)

顺时针点：(0,1), (1,1), (1,0), (0,0)

您可以查看是否将 pts2-4 反转，您的顺时针列表变为逆时针。

编辑：我的观点从 NE 开始，fixt。

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

7 回答 7

Related

Reference