Python сортировать словарь Lat / Lons для Footprint

Question

Я вычисляю зоны покрытия спутника на поверхности эллипсоида, и моя функция возвращает список широт / долгот, который выглядит ниже. Это список словарей Python. Теперь, если я рассею график в Matlab или Matplotlib, я получу хороший трехмерный отпечаток отсоединенных точек. Однако я хочу иметь возможность использовать команду plot (not scatter), чтобы создать плавный трехмерный круг для представления отпечатка. Для этого мне нужно как-то их отсортировать. Я пробовал Haversine (наибольшее расстояние по кругу), чтобы найти ближайшего соседа для каждой точки, но это все равно дает мне иногда отключенную линию, когда у меня есть больший набор значений (GEO sats). Я также попытался разделить значения на широты N и S, когда зона охвата пересекает экватор, а затем отсортировать по долготе. Я, вероятно, что-то упускаю. У кого-нибудь есть идея получше / быстрее отсортировать список таким образом, чтобы, если бы я соединил все последовательные точки в списке, я получил бы полный упорядоченный круг?

latLons = [{'lat': -33.783781327, 'lon': 137.47747747700001}, {'lat': -33.783781326899998, 'lon': 139.63963964000001}, {'lat': -33.603601166200001, 'lon': 136.03603603600001}, {'lat': -33.423421005500003, 'lon': 134.59459459499999}, {'lat': -32.882880523399997, 'lon': 132.43243243200001}, {'lat': -32.522520202199999, 'lon': 131.71171171200001}, {'lat': -32.342340041600004, 'lon': 145.40540540500001}, {'lat': -31.261259078399998, 'lon': 147.56756756799999}, {'lat': -31.081078917799999, 'lon': 128.828828829}, {'lat': -29.459457473099999, 'lon': 126.666666667}, {'lat': -28.558556670200002, 'lon': 125.94594594599999}, {'lat': -27.657655866700001, 'lon': 125.225225225}, {'lat': -26.936935223300001, 'lon': 151.89189189199999}, {'lat': -26.7567550624, 'lon': 124.504504504}, {'lat': -25.6756740961, 'lon': 152.61261261300001}, {'lat': -25.3153137736, 'lon': 123.78378378399999}, {'lat': -23.873872481599999, 'lon': 153.33333333300001}, {'lat': -23.333331995999998, 'lon': 123.063063063}, {'lat': -19.3693684138, 'lon': 154.05405405400001}, {'lat': -15.765765115600001, 'lon': 123.063063063}, {'lat': -15.2252246167, 'lon': 153.33333333300001}, {'lat': -13.243242777300001, 'lon': 152.61261261300001}, {'lat': -12.162161767000001, 'lon': 124.504504505}, {'lat': -11.801801428999999, 'lon': 151.89189189199999}, {'lat': -10.9009005815, 'lon': 125.225225225}, {'lat': -8.1981980155999992, 'lon': 149.00900900900001}, {'lat': -6.9369368056800003, 'lon': 147.56756756799999}, {'lat': -6.5765764584799999, 'lon': 129.54954954999999}, {'lat': -6.5765764584799999, 'lon': 146.84684684699999}, {'lat': -5.6756755875199998, 'lon': 130.99099099099999}, {'lat': -4.7747747122700002, 'lon': 143.24324324299999}, {'lat': -4.23423418502, 'lon': 141.08108108100001}, {'lat': -3.8738738326600002, 'lon': 138.198198198}]

Answer 1

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

Вот простая реализация:

import matplotlib.pyplot as plt
import math

def polar_sort(l):
    x, y = zip(*((c['lat'], c['lon']) for c in l))
    ave_x = float(sum(x))/len(x)
    ave_y = float(sum(y))/len(y)

    return sorted(l, key=lambda c: math.atan2(c['lat']-ave_x, c['lon']-ave_y))

latLons = [{'lat': -33.783781327, 'lon': 137.47747747700001}, {'lat': -33.783781326899998, 'lon': 139.63963964000001}, {'lat': -33.603601166200001, 'lon': 136.03603603600001}, {'lat': -33.423421005500003, 'lon': 134.59459459499999}, {'lat': -32.882880523399997, 'lon': 132.43243243200001}, {'lat': -32.522520202199999, 'lon': 131.71171171200001}, {'lat': -32.342340041600004, 'lon': 145.40540540500001}, {'lat': -31.261259078399998, 'lon': 147.56756756799999}, {'lat': -31.081078917799999, 'lon': 128.828828829}, {'lat': -29.459457473099999, 'lon': 126.666666667}, {'lat': -28.558556670200002, 'lon': 125.94594594599999}, {'lat': -27.657655866700001, 'lon': 125.225225225}, {'lat': -26.936935223300001, 'lon': 151.89189189199999}, {'lat': -26.7567550624, 'lon': 124.504504504}, {'lat': -25.6756740961, 'lon': 152.61261261300001}, {'lat': -25.3153137736, 'lon': 123.78378378399999}, {'lat': -23.873872481599999, 'lon': 153.33333333300001}, {'lat': -23.333331995999998, 'lon': 123.063063063}, {'lat': -19.3693684138, 'lon': 154.05405405400001}, {'lat': -15.765765115600001, 'lon': 123.063063063}, {'lat': -15.2252246167, 'lon': 153.33333333300001}, {'lat': -13.243242777300001, 'lon': 152.61261261300001}, {'lat': -12.162161767000001, 'lon': 124.504504505}, {'lat': -11.801801428999999, 'lon': 151.89189189199999}, {'lat': -10.9009005815, 'lon': 125.225225225}, {'lat': -8.1981980155999992, 'lon': 149.00900900900001}, {'lat': -6.9369368056800003, 'lon': 147.56756756799999}, {'lat': -6.5765764584799999, 'lon': 129.54954954999999}, {'lat': -6.5765764584799999, 'lon': 146.84684684699999}, {'lat': -5.6756755875199998, 'lon': 130.99099099099999}, {'lat': -4.7747747122700002, 'lon': 143.24324324299999}, {'lat': -4.23423418502, 'lon': 141.08108108100001}, {'lat': -3.8738738326600002, 'lon': 138.198198198}]

x,y = zip(*((c['lat'], c['lon']) for c in polar_sort(latLons)))

plt.plot(x,y)
plt.show()

Answer 2

Не думаю, что вам нужен обычный вид.В обычном порядке вы используете абсолютный порядок между элементами.Здесь у вас нет абсолютного порядка (что такое «первая» координата?), Только относительный.

Сначала я бы вывел данные из словарей в список кортежей:

latlonslist = [ (x['lat'],x['lon']) for x in latLons ]

Затем import scipy.spatial и используйте расстояние по вашему выбору для поиска ближайшего соседа к каждой точке.Вы также можете использовать евклидово расстояние, не прибегая к scipy, конечно.

Вычислить все возможные расстояния (должно быть n^2 ops) примерно так:

distances = {}  
for n1 in latlonslist:
  for n2 in latlonslist:
    if n1 == n2:
      continue
    thisdist = scipy.spatial.distance.euclidean(n1,n2)
    distances[n1,n2] = thisdist

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