4

私は奇妙な問題を解決しようとしています。おそらく、これを処理するアルゴリズムを知っているでしょう。

貨物貨物トラックのデータがあり、いくつかのデータを抽出したいと考えています。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 まではもう 1 マイルあり、貨物には 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)

私はまだかなり非効率的な計算を行っています。

4

3 に答える 3

1

ロケーションデータがフェッチされたときのロケーションとタイムスタンプがある場合は、次のように簡単に実行できます。

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-04T09:19:28.360 に答える
0

ですから、そのnようなポイントがあればn - 1、旅の途中に「足」ができます。次の方法でそのリストを作成できます。

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

pointはポイントのリストであり、build_leg()2つのポイントを受け入れ、距離と平均速度を計算する関数であると仮定します。

上記のループは、最初のポイント0と1、次に1と2、というように、最後の2つのポイントであるまでbuild_leg呼び出します。n - 2n - 1

于 2012-07-04T09:20:04.930 に答える
0

私はスライド式の窓が大好きになりました。ここで役立つかもしれません。他の回答と同じ概念ですが、方法が少し異なります。

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-04T12:26:34.143 に答える