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

Question

Я вычисляю следы покрытия спутника на поверхности эллипсоида, и моя функция возвращает список Lat/Lons, который выглядит ниже. Это список словарей на языке python. Теперь, если я разбросаю график в Matlab или Matplotlib, я получаю хороший 3D-след отключенных точек. Однако я хочу иметь возможность использовать команду 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 и использовать distance вашего выбора для поиска ближайшего соседа в каждой точке. Разумеется, вы также можете использовать эвклидовое расстояние, не прибегая к scipy.

Compute все возможные расстояния (должно быть 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 

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