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

Мне нужно отсортировать список координат для прямоугольника против часовой стрелки и сделать северо-восточный угол первой координатой. Это географические координаты (то есть долгота, широта) в десятичной форме.

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

Ответы на вопрос(7)

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

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

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

 Aaron10 нояб. 2009 г., 18:23
@Crescent Fresh - знание направления - это первый шаг к правильной сортировке, не так ли?не так ли? Если вам нужно это в направлении против часовой стрелки и список как есть в порядке по часовой стрелке, то вы переворачиваете список и - та да - у вас есть его в направлении против часовой стрелки.
 Crescent Fresh10 нояб. 2009 г., 17:59
Мне нужно больше, чем направление, мне нужен список, отсортированный в порядке, размещенном для дальнейших операций.
 Crescent Fresh10 нояб. 2009 г., 18:31
Извини я'Я не очень четко заявляю: мне нужно отсортировать список, начиная ск северо-востоку угол. Просто знание направления не говорит мне, какой пункт в списке является северо-восточным.

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

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

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

 Crescent Fresh10 нояб. 2009 г., 18:12
Перестройка» список из двух противоположных углов эквивалентен сортировке всего списка, я полагаю, хотя и немного неортодоксально.

Итак, у вас есть 4 балла.

Вы всегда начинаете с точки NW.

Вы знаете, что точки отсортированы, но не в каком направлении.

Это's простая проверка первых двух точек, является ли список по часовой стрелке или против часовой стрелки.

если (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.I

 Crescent Fresh10 нояб. 2009 г., 17:43
не знать, если список начинается в NW. Извините, если это было неясно.

Предполагая, что ваш "прямоугольники» всегда параллельны экватору и меридианам (что 'Что означает ваш пример, но этоне указано явно), то есть у вас есть только две пары различных значений 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)

 Crescent Fresh16 нояб. 2009 г., 03:52
@Curd: в моем сценарии у меня есть 4 координаты, а не 2. Поиск 2, о котором вы говорите, является попыткой найти 2 из 4, противоположных друг другу.
 Curd11 нояб. 2009 г., 14:22
@Crescent Fresh: в вашем вопросе выше я нене понимаю, что вы подразумеваете под "противоположные углы ... », С "(lat0, lat1) " Я просто имел в виду список ваших двух значений широты. Порядок нене имеет значения.
 Adrian McCarthy10 нояб. 2009 г., 18:24
+1, потому что это объяснение яснее моего и делает предположение явным
 Crescent Fresh10 нояб. 2009 г., 18:29
@Curd: сноска внизу вопроса пыталась передать то, что вы сказали (нене хочу попасть в Lines of Lat / Lng в вопросе). Во всяком случае, нахождение противоположных углов(lat0, lat1) а также(lng0, lng1) являетсясам поиск точек минимума и максимума (с учетом углов SW и NE соответственно), верно?

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

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

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

 Crescent Fresh10 нояб. 2009 г., 19:42
Интересно, работает ли это, пересекая экватор или меридиан (где широта / долгота отражаются от- в+) ...
 u0b34a0f6ae10 нояб. 2009 г., 19:57
это невозможно без обмена: нам нужно отсортировать север перед югом, прежде чем мы узнаем, какие точки являются самыми южными, а затем отсортируем их по направлению восток-запад.
 Crescent Fresh10 нояб. 2009 г., 19:49
Должно работать нормально на самом деле. Хотелось бы, чтобы это лучше без обмена;) +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) важны для получения правильного результата.

 Crescent Fresh10 нояб. 2009 г., 18:49
@SilentGhost: вы говорите, что в вашем ответе список будет отсортирован по часовой стрелке, но неэто на самом деле сортировка против часовой стрелки, как я и просил?
 SilentGhost10 нояб. 2009 г., 18:45
да, убежищене видел его ответа, прежде чем яя реализовал мой код единственная разница действительно заключается в получении этого заказа. и я'я тоже проверил мой код :)
 SilentGhost10 нояб. 2009 г., 20:20
@Crescent Fresh: конечно, он сортирует против часовой стрелки, это была просто опечатка.
 Crescent Fresh10 нояб. 2009 г., 18:39
Ницца. Это похоже на то, что @ tom10 пытался передать (без отображения на[0, 2pi]), это правильно?

Ваш ответ на вопрос