Как я могу отсортировать список координат для прямоугольника против часовой стрелки?

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 широты, не являются проблемой.}

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)

Answer 3

Свяжите угол с каждой точкой (относительно внутренней точки), и затем движение вокруг тривиально.

Чтобы рассчитать угол, найдите точку в середине фигуры, например, (average_lat, average_lng) будет в центре. Тогда atan2(lng - average_lng, lat - average_lat) будет углом этой точки.

Answer 4

Вместо сортировки вы можете просто «перестроить» прямоугольник в любом порядке.

Из исходного набора соберите минимальную и максимальную широту и минимальную и максимальную долготу. Затем создайте прямоугольник в любом порядке.

Северо-западный угол - максимальная широта и минимальная долгота. Юго-западный угол - минимальная широта и минимальная долгота. И т.д.

Answer 5

Это легко. Сначала мы сортируем координаты, чтобы знать, в каком порядке они у нас есть, затем просто выбираем их:

Сортируйте их сначала по лат, затем по 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}]

(Минусы в ключевой функции существуют для того, чтобы большие значения сортировались перед меньшими значениями. При сортировке мы помещаем север перед югом, затем восток перед западом; чтобы получить желаемый порядок, мы просто меняем два последних (южных) значения. )

Answer 6

Если вы берете перекрестное произведение двух векторов из угла, знак результата скажет вам, по часовой стрелке или против часовой стрелки.

Answer 7

Итак, у вас 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.