optimization - GPS轨迹的简化/优化

Question

我有一个由 gpxlogger(1) 制作的 GPS 轨迹(作为 gpsd 的客户端提供)。 GPS 接收器每 1 秒更新一次坐标，gpxlogger 的逻辑非常简单，它记录下位置( lat 、 lon 、 ele )和每 n 秒(n = 3)从 GPS 接收到的时间戳( time )在我的情况下)。

在写下几个小时的轨迹后，gpxlogger 保存了几兆字节长的 GPX 文件，其中包含数千个点。之后，我尝试在 map 上绘制这条路线并将其与 OpenLayers 一起使用。 .它有效，但数千个点使使用 map 成为一种草率和缓慢的体验。

我知道有几千个次优点。有无数个点可以删除而几乎不会丢失任何东西:当有几个点大致组成一条直线并且我们在它们之间以相同的恒定速度移动时，我们可以只留下第一个和最后一个点并抛出带走任何其他东西。

我想过用gpsbabel对于这样的轨道简化/优化工作，但是，唉，它是 simplification filter仅适用于路线，即仅分析路径的几何形状，没有时间戳(即不检查速度是否大致恒定)。

是否有一些现成的实用程序/库/算法可用于优化轨道？或者我可能错过了 gpsbabel 的一些聪明选择？

Answer 1

是的，如前所述，Douglas-Peucker 算法是一种简化二维连接路径的直接方法。但正如您所指出的，您需要将其扩展到 3D 案例，以适本地简化 GPS 轨迹，并具有与每个点相关联的固有时间维度。我已经使用 Douglas-Peucker 的 PHP 实现为我自己的 Web 应用程序这样做了。

只要稍微了解算法的工作原理，就可以轻松地将算法扩展到 3D 案例。假设您的输入路径由标记为 A 到 Z 的 26 个点组成。此路径的最简单版本有两个点，A 和 Z，因此我们从这里开始。想象一下 A 和 Z 之间的线段。现在扫描所有剩余的点 B 到 Y，以找到距离线段 AZ 最远的点。假设最远的点是 J。 然后，你扫描 B 和 I 之间的点，找到离线段 AJ 最远的点，扫描点 K 到 Y，找到离线段 JZ 最远的点，依此类推，直到剩下的点都位于某个所需的距离阈值内。

这将需要一些简单的向量操作。从逻辑上讲，3D 中的过程与 2D 中的过程相同。如果您发现用您的语言实现了 Douglas-Peucker 算法，它可能实现了一些 2D 向量数学，您需要扩展它们以使用 3 维。

您可以在此处找到 3D C++ 实现:3D Douglas-Peucker in C++

您的 x 和 y 坐标可能以纬度/经度为单位，而 z(时间)坐标可能以 unix 纪元以来的秒为单位。您可以通过确定适当的时空关系来解决这种差异；假设您想在 1 平方英里的 map 区域内查看一天的事件。将此关系想象为 1 英里 x 1 英里 x 1 天的立方体，您必须预先调整时间变量。从度数到表面距离的转换是很重要的，但对于这种情况，我们简化并说 1 度是 60 英里；那么一英里是 0.0167 度。一天是 86400 秒；然后为了使单位相等，我们为您的时间戳记的预分频因子是 0.0167/86400，或大约 1/5,000,000。

例如，如果您想在 2 天内查看同一 1 平方英里 map 区域内的 GPS 事件，则时间分辨率的重要性减半，因此将其进一步缩小两次，达到 1/10,000,000。玩得开心。