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

StackOverflow https://stackoverflow.com/questions/1709283

题

我要逆时针排序为矩形的坐标列表，使东北角的第一个坐标。这些是地理坐标（即经度，纬度）在十进制形式。 1

例如，这里有一个矩形的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
]

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

1 <子>这不是当映射到地球的表面，但是因为我有2个相对的角我打电话它用于可读性矩形真正矩形。形状的涡卷+ 180 / -180经度或+ 90 / -90纬度是不是一个问题。

有帮助吗？

解决方案

解决方案似乎相当简单：

>>> 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）是重要的是得到一个有效的结果。

其他提示

假设你的“矩形”总是平行于赤道和经络（这是你的榜样意味着什么，但它没有明确地说明），也就是你刚才2双不同的纬度和经度值：（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代码）

而不是分选，可以只在所需的任何次序“重建”的矩形。

从原始集合，收集最小和最大纬度和最小和最大经度。然后构造在任何想要的次序的矩形。

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

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

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

如果您从一个角落里拿两个向量的叉积，则结果的符号会告诉你，如果它是顺时针或逆时针。

这是很容易。首先，我们所以我们知道我们有他们这顺序排序的坐标，那么我们干脆挑出来：

，第一最大首先由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}]

（中键功能的优缺点有那么这更大值排在较小的值通过整理我们西之前把南北之前，再向东;以获得所需的订单，我们只是交换了最后两个（南部）值。 ）

所以，你得4分。

您始终与NW点开始。

您知道点进行排序，只是没有在哪个方向。

这是第2点的一个简单的测试列表是否为顺时针顺时针或逆时针。

如果（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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top