我有一个由gpxlogger(1)（作为gpsd的客户端提供）制作的 GPS 轨迹。GPS 接收器每 1 秒更新一次坐标，gpxlogger 的逻辑非常简单，它每n秒记录一次从 GPS 接收到的位置 ( lat, lon, ele) 和时间戳 ( ) (在我的例子中n = 3 )。time
在写下几个小时的轨迹后，gpxlogger 保存了几兆字节长的 GPX 文件，其中包含数千个点。之后，我尝试在地图上绘制这条轨迹并将其与OpenLayers一起使用。它可以工作，但是数千个点使使用地图变得草率而缓慢。
我知道有几千个次优点。有无数的点可以删除而几乎不会丢失任何东西：当有几个点大致组成一条直线并且我们以相同的恒定速度移动它们之间时，我们可以留下第一个和最后一个点并扔掉带走其他任何东西。
我曾想过使用gpsbabel进行此类轨道简化/优化工作，但是，唉，它的简化过滤器仅适用于路线，即仅分析路径的几何形状，没有时间戳（即不检查速度是否大致恒定）。
是否有一些现成的实用程序/库/算法可用于优化轨道？或者我可能错过了 gpsbabel 的一些聪明选择？
是的，如前所述，Douglas-Peucker 算法是简化 2D 连接路径的直接方法。但正如您所指出的，您需要将其扩展到 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++ 实现：C++中的 3D Douglas-Peucker
您的 x 和 y 坐标可能以纬度/经度为单位，z（时间）坐标可能以 unix 纪元以来的秒数为单位。您可以通过确定适当的时空关系来解决这种差异；假设您想在 1 平方英里的地图区域内查看一天的活动。将此关系想象为 1 英里 x 1 英里 x 1 天的立方体，您必须预先调整时间变量。从度数到表面距离的转换并非易事，但对于这种情况，我们简化并说 1 度是 60 英里；那么一英里是0.0167度。一天是86400秒；那么为了使单位等效，我们为您的时间戳提供的预分频因子是 0.0167/86400，或大约 1/5,000,000。
例如，如果您想在 2 天内查看同一 1 平方英里地图区域内的 GPS 活动，则时间分辨率的重要性将降低一半，因此将其进一步缩小两倍，至 1/10,000,000。玩得开心。
看看Ramer-Douglas-Peucker平滑复杂多边形的算法，Douglas-Peucker线条简化算法可以帮助您减少点数。
开源 GeoKarambola java 库（无 Android 依赖项，但可在 Android 中使用），其中包含一个 GpxPathManipulator 类，该类可进行路线和轨道简化/减少（3D/海拔感知）。如果这些点有不会被丢弃的时间戳信息。 https://sourceforge.net/projects/geokarambola/
该算法基于通过消除具有最大 XTD（跨轨道距离）误差的点来减少点数，直到满足容许误差或达到最大点数（函数的两个参数），以先到者为准。
对于像轨道简化（我称之为“streamplification”）这样的实时流，另一种算法是：每次将 GPS 点添加到缓冲区（海拔包括）您计算缓冲区中所有点到将缓冲区的第一个点与（新添加的）最后一个点联合起来的线段的最大 XTD（跨轨道距离）。如果具有最大 XTD 的点违反了您的最大容忍 XTD 误差（25m 给了我很好的结果），那么您在该点切割缓冲区，将其注册为要附加到流放大轨道的选定点，修剪尾随部分缓冲到那个切点，然后继续。在轨道的末端，缓冲区的最后一个点也被添加/刷新到溶液中。该算法足够轻巧，可以在 AndroidWear 智能手表上运行，无论您是慢动作还是快动作，或者长时间闲置在同一个地方，都能提供最佳输出。唯一重要的是你的赛道的形状。您可以走很多分钟/公里，只要您沿直线移动（在 +/- 允许的 XTD 误差偏差内的走廊），streamplify 算法将仅输出 2 个点：出口形式最后一条曲线和入口的点在下一条曲线上。
我遇到了类似的问题。gps 单元获得分数的速率比所需的要大得多。许多点在地理上并不相距很远。我采用的方法是使用半正弦公式计算点之间的距离。如果距离不大于我的阈值（在我的情况下为 0.1 英里），我会丢弃该点。这很快将点数降低到可管理的大小。
我不知道你在寻找什么语言。这是我正在处理的一个 C# 项目。在底部，您将找到半正弦代码。
http://blog.bobcravens.com/2010/09/gps-using-the-netduino/
希望这能让你继续前进。
鲍勃
这可能是 NP 难的。假设您有点 A、B、C、D、E。
让我们尝试一个简单的确定性算法。假设您计算从 B 点到 AC 线的距离，并且它小于您的阈值（1 米）。所以你删除了B。然后你对C 线AD 尝试同样的操作，但它更大，而CE 的D 线也更大。
但事实证明，最优解是 A、B、E，因为 C 点和 D 点靠近 BE 线，但在相反的两侧。
如果你删除 1 个点，你不能确定它应该是一个你应该保留的点，除非你尝试每一个可能的解决方案（可以是n^n大小，所以n=80这超过了已知宇宙中的最小原子数） .
下一步：尝试蛮力或分支定界算法。无法扩展，不适用于现实世界的大小。你可以安全地跳过这一步:)
下一步：首先做一个确定性算法，然后使用元启发式算法（禁忌搜索、模拟退火、遗传算法）对其进行改进。在 java 中有几个开源实现，例如Drools Planner。
总而言之，您可能会使用第一个简单的确定性算法获得一个可行的解决方案（尽管不是最优的），因为您只有一个约束。
这个问题的一个远亲可能是旅行推销员问题的变体，其中推销员不能访问所有城市，而必须选择一些城市。
你想扔掉无趣的点。所以你需要一个函数来计算一个点有多有趣，然后你可以计算所有点有多有趣，然后扔掉N个最不感兴趣的点，在这里你选择N来充分精简数据集。听起来您对有趣的定义对应于高加速度（偏离直线运动），这很容易计算。
试试这个，它是免费和开源的在线服务：
我想你需要保持你改变方向的点。如果你将你的轨迹分割成一组恒定方向的区间，你可以只留下这些区间的边界点。
而且，正如 Raedwald 指出的那样，您需要留下加速度不为零的点。
不确定这将如何运作，但如何获取点列表，计算它们之间的距离以及路线的总距离，然后确定分辨率距离，然后根据每一步线性插值位置x 米。即，对于每个修复，您都有一个“距起点的距离”度量，您只需插入整个路线的 n*x 所在的位置。（你可以决定你想要多少点并将总距离除以得到你的分辨率距离）。最重要的是，您可以添加一个窗口函数，可能取当前点 +/- z 点并应用类似 exp(-k* dist^2/accuracy^2) 的权重来获得 dist 的一组点的加权平均值是与原始插值点的距离，精度是 GPS 位置的假定精度。
一种非常简单的方法是重复删除在其邻居之间创建最大角度的点（在 0° 到 180° 的范围内，其中 180° 表示它在其邻居之间的直线上），直到您的点足够少。这将从删除与邻居完全一致的所有点开始，并将从那里开始。
您可以在Ο（n log（n））中通过制作每个索引及其角度的列表，按角度降序对该列表进行排序，从列表的前面保留您需要的数量，将较短的列表排序为索引的降序，并从点列表中删除索引。
def simplify_points(points, how_many_points_to_remove)
angle_map = Array.new
(2..points.length - 1).each { |next_index|
removal_list.add([next_index - 1, angle_between(points[next_index - 2], points[next_index - 1], points[next_index])])
}
removal_list = removal_list.sort_by { |index, angle| angle }.reverse
removal_list = removal_list.first(how_many_points_to_remove)
removal_list = removal_list.sort_by { |index, angle| index }.reverse
removal_list.each { |index| points.delete_at(index) }
return points
end