如何从一组GPS点中获取“最快英里”列表

Question

我希望解决一个奇怪的问题，也许你们知道一些可以解决这个问题的算法。

我有一辆货运卡车的数据，并想要提取一些数据。假设我从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)

我仍在做一些相当低效的计算。

- santiagobasulto

---

你需要什么帮助？是要对英里时间列表进行排序吗？（可能不是！）还是要计算经纬度对之间的英里距离？ - High Performance Mark

速度 = 距离 / 时间，这就是你需要的全部吗？计算两个经纬度之间的距离非常容易，在许多网站上都可以找到，计算时间差也很容易。排序取决于你要排序的项目数量。 - Jon Taylor

假设是直线，我会使用勾股定理和速度=距离/时间公式。使用 time.strptime 和 calendar.timegm 将时间转换为标准格式以便您处理。 - inspectorG4dget

我已经得到了距离。我可以手动计算或使用geopy。这不是问题。也许我没有很好地表达我的问题。我会编辑它，使其更加清晰。 - santiagobasulto

完成。看到我的问题了吗？我有一种方法可以获取两个点之间的距离和经过的时间。但是我没有一个好的方法来计算所有点之间的距离和时间。 - santiagobasulto

Answer 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

您在评论中提到过可以为单个配对执行此操作，因此您只需要为所有连续的配对执行此操作即可。

- Vatine

---

是的，我已经有这个了。我正在寻找更好的算法。对于任何GPS路线，我至少有1000个点。做这种计算几乎是不可能的。无论如何，还是谢谢你。 - santiagobasulto

我认为没有任何“魔法捷径”可以得到你想要的答案。这取决于你实际想要实现什么，但我理解这个问题是“我想找到所有点之间的速度”，而你不能不计算它们就得到这个答案。也许可以通过跳过中间点直到达到最小经过时间（因为经过时间可能比距离更便宜）来减少计算速度的段数。 - Vatine

是的，也许可以。但那并不是真正健壮的方法。我一直在研究分类机制，比如K最近邻算法（http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm）。希望有更好的方法。 - santiagobasulto

你实际上试过以上所示的计算吗？我认为对一千个点执行此操作不应该超过一秒钟。 - mtrw

Answer 2

因此，如果您有n个这样的点，则旅程上将有n-1条“腿”。 您可以通过以下方式形成该列表：

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

假设point是点的列表，并且build_leg()是一个接受两个点并计算距离和平均速度的函数。

上述循环将使用第一个点0和1调用build_leg，然后是1和2，依此类推，直到n-2和n-1，它们是最后两个点。

- unwind

Answer 3

我已经喜欢上了滑动窗口，它在这里可能会有帮助。与其他答案相同的概念，只是稍微不同的方法。

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)

- monkut