如何從一組GPS點中獲取「最快里程」列表

我試圖解決一個奇怪的問題。也許你們知道一些處理這個問題的算法。如何從一組GPS點中獲取「最快里程」列表

我有一個貨運卡車的數據，並希望提取一些數據。假設我已經獲得了從GPS獲得的排序點列表。這是該卡車的路線：

[ 
    { 
     "lng": "-111.5373066", 
     "lat": "40.7231711", 
     "time": "1970-01-01T00:00:04Z", 
     "elev": "1942.1789265256325" 
    }, 
    { 
     "lng": "-111.5372056", 
     "lat": "40.7228762", 
     "time": "1970-01-01T00:00:07Z", 
     "elev": "1942.109892409177" 
    } 
]

現在，我想要得到的是「最快里程」的列表。我會做一個例子：

考慮到兩點：

A, B, C, D, E, F

從A點到B點的距離爲1英里，貨物了10:32分。從B點到D點我還有其他的一英里，貨物需要10分鐘等。所以，我需要一個按時間排序的清單。類似於：

B -> D: 10 
A -> B: 10:32 
D -> F: 11:02

你知道任何有效的算法可以讓我計算嗎？

謝謝大家。 PS：我使用的是Python。

編輯：

我有距離。我知道如何計算它，並且有很多帖子可以做到這一點。我需要的是一種按英里標記的算法，並從中獲得速度。具有距離功能不夠有用：

results = {} 
for point in points: 
    aux_points = points.takeWhile(point>n) #This doesn't exist, just trying to be simple 
    for aux_point in aux_points: 
    d = distance(point, aux_point) 
    if d == 1_MILE: 
     time_elapsed = time(point, aux_point) 
     results[time_elapsed] = (point, aux_point)

我仍然在做一些非常低效的計算。

來源

2012-07-04 santiagobasulto

你到底需要什麼幫助？首先對英里時間列表進行排序？（可能不是！）計算緯度/長度對之間的英里距離？ –

速度=距離/時間，當然這就是你需要的全部？計算兩個經緯度之間的距離非常簡單，可以在很多網站上找到，計算時間差也很容易。排序真的取決於你將要排序的項目數量。 –

假設直線，我會去與畢達哥拉斯的定理和速度= dist /時間。使用'time.strptime'和'calendar.timegm'來獲得時間到一個標準格式，讓你玩 – inspectorG4dget

如果你有當位置數據爲獲取位置和時間戳，你可以簡單地做這樣的事情：

def CalculateSpeeds(list_of_points_in_time_order): 
    """Calculate a list of (average) speeds for a list of geographic points.""" 

    points = list_of_points_in_time_order 
    segment_start = points[0] 
    speed_list = [] 

    for segment_end in points[1:]: 
    dt = ElapsedTime(segment_start, segment_end) 
    # If you're looking at skipping points, with a slight risk of degraded data 
    # you could do something like "if dt < MIN_ELAPSED_TIME:" and indent 
    # the rest of the loop. However, you'd need to then check if the last point 
    # has been accounted for, as it might've been too close to the last considered 
    # point. 
    d = Distance(segment_start, segment_end) 
    speed_list.append(d/dt) 
    segment_start = segment_end 
    return speed_list

你說（在評論），您可以單對這樣做，所以你需要做的就是對所有連續的對進行。

來源

2012-07-04 09:19:28 Vatine

是的，我已經有這個。我正在尋找更好的算法。對於任何GPS路線，我有不少於1000分。做這種計算幾乎是不可能的。不管怎樣，謝謝你。 – santiagobasulto

我不認爲有任何「魔術捷徑」來獲得你想要的答案。它取決於你實際上想要完成的事情，但是我把這個問題看作是「我想找到所有的點間速度」，如果沒有，計算它們，你就無法得到。通過（例如）跳過中間點，直到你有一個最小的經過時間（因爲經過的時間可能比距離計算更便宜），可以減少你計算的速度的數量。 – Vatine

是的，也許。但那不會很有力。我一直在看分類機制，如K-最近鄰算法（http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm）。我希望有更好的辦法。 – santiagobasulto

所以，如果你有n這樣的分數，那麼在旅途中會出現n - 1「腿」。您可以通過簡單地形成列表：

legs = [] 
for i in xrange(n - 1): 
    legs.append(build_leg(point[i], point[i + 1]))

假設point是一個點的列表，並build_leg()是接受兩分，計算距離和平均速度的函數。

上述循環將調用build_leg，第一個點爲0和1，然後是1和2，依此類推直到n - 2和n - 1這是最後兩點。

來源

2012-07-04 09:20:04 unwind

我已經開始喜歡滑動窗口了，在這裏可能會有所幫助。與其他答案一樣的概念，只是一個稍微不同的方法。

from itertools import islice 
def window(seq, n=2): 
    "Returns a sliding window (of width n) over data from the iterable" 
    " s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...     " 
    it = iter(seq) 
    result = tuple(islice(it, n)) 
    if len(result) == n: 
     yield result  
    for elem in it: 
     result = result[1:] + (elem,) 
     yield result 


results = {} 
# presort your points in time if necessary 
for point_a, point_b in window(points): 
    d = distance(point_a, point_b) 
    if d == 1_MILE: 
     time_elapsed = time(point_a, point_b) 
     results[time_elapsed] = (point_a, point_b)

來源

2012-07-04 12:26:34 monkut

如何從一組GPS點中獲取「最快里程」列表

回答

相關問題