代码之家 › 专栏 › 技术社区 › Crescent Fresh nosklo

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

geospatial coordinates sorting algorithm python

Crescent Fresh nosklo · 技术社区 · 14 年前

我需要对矩形的坐标列表进行逆时针排序,并将东北角作为第一个坐标。这些是十进制形式的地理坐标(即经度、纬度)。

例如,以下是矩形的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. _{当映射到地球表面时,这不是一个真正的矩形,但是因为我有两个相对的角,为了可读性,我称它为矩形。环绕经度+180/-180或纬度+90/-90的形状不是问题。}

7 回复 | 直到 14 年前

rold2007 9 年前

解决方案似乎非常简单:

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

Curd Erin Yueh 14 年前

您将获得以下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代码)

Adrian McCarthy 14 年前

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

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

tom10 14 年前

将角度与每个点(相对于内部点)关联,然后四处移动是很简单的。

为了计算角度,在形状的中间找到一个点,例如, (average_lat, average_lng) atan2(lng - average_lng, lat - average_lat) 将是该点的角度。

Aaron 14 年前

u0b34a0f6ae 14 年前

首先按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}]

(键函数中有负数,因此较大的值在较小的值之前排序。通过排序,我们将北放在南之前,然后将东放在西之前;为了获得所需的顺序,我们只需交换最后两个(南部)值。)

Will Hartung 14 年前

所以,你得4分。

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

如果检测到点为顺时针方向,只需反转列表中的最后3个点即可。

逆时针点:(0,1)、(0,0)、(1,0)、(1,1)

顺时针点:(0,1)、(1,1)、(1,0)、(0,0)

编辑:我的观点是从东北方向开始的。