GPS轨迹的简化/优化

Question

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

记录了数小时的轨迹后，gpxlogger保存了几兆字节长的GPX文件，其中包含数千个点。然后，我尝试在地图上绘制这条轨迹，并与OpenLayers一起使用。它可以工作，但是数千个点使得使用地图变得缓慢。

我理解多个点的存在是不太优化的。有许多点可以删除而几乎不会失去任何内容：当有几个点大致组成直线并且我们在它们之间以相同的恒定速度移动时，我们只需保留第一个和最后一个点，然后丢弃其他任何东西。

我考虑使用gpsbabel来进行此类轨迹简化/优化工作，但是它的简化过滤器仅适用于路线，即仅分析路径的几何形状，而不考虑时间戳（即未检查速度是否大致恒定）。

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

- GreyCat

Answer 1

如前所述，道格拉斯-普克算法是简化2D连接路径的直接方法。但正如您所指出的那样，您需要将它扩展到3D情况下，以正确简化具有每个点相关的固有时间维度的GPS轨迹。我使用Douglas-Peucker的PHP实现为自己的Web应用程序做到了这一点。

只需稍微了解算法的工作原理，就很容易将其扩展到3D情况。假设您有一个由26个标记为A到Z的输入路径。这条路径的最简版本有两个点，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平方英里的地图区域内查看一天的活动。将这种关系想象成一个1英里乘1英里乘1天的立方体，你必须预先缩放时间变量。从度数到表面距离的转换是不易的，但对于这种情况，我们简化为一度等于60英里;然后一英里等于0.0167度。一天是86400秒;然后为了使单位相等，我们的预缩放因子为您的时间戳是0.0167/86400，约为1/5,000,000。

例如，如果你要在同样的1平方英里地图区域内观察2天的GPS活动，时间分辨率就变得不那么重要了，所以要进一步缩小两倍，为1/10,000,000。祝玩得愉快。

- Matt Montag

---

如果你正在寻找一个PHP类，可以做到这一点，这里有两个我找到的： https://github.com/david-r-edgar/RDP-PHP https://github.com/gregallensworth/PHP-Geometry在这里，你可以在线测试文件简化，玩转配置，并立即查看结果和更改：https://labs.easyblog.it/maps/gpx-simplify-optimizer/ - artisare

Answer 2

请查看 Ramer-Douglas-Peucker 算法以平滑复杂的多边形，同时 Douglas-Peucker 线简化算法可以帮助您减少点数。

- ismail

---

谢谢，我以为已经有一些可用的算法了，只是错过了！ 我是否正确地理解，我在这里唯一需要的就是将该算法适应于三维空间（即“（x，y，t）”坐标），并以某种方式定义在这样的空间中的“正交距离”？ - GreyCat

是的，你需要想办法映射 time 参数 :) - ismail

Answer 3

这是一个开源的GeoKarambola Java库（不依赖于Android，但可以在Android中使用），其中包括一个GpxPathManipulator类，可进行路线和轨迹简化/减少（3D /高程感知）。 如果点具有时间戳信息，则不会丢弃该信息。 https://sourceforge.net/projects/geokarambola/

以下是该算法的交互式演示： https://lh3.googleusercontent.com/-hvHFyZfcY58/Vsye7nVrmiI/AAAAAAAAHdg/2-NFVfofbd4ShZcvtyCDpi2vXoYkZVFlQ/w360-h640-no/movie360x640_05_82_05.gif

该算法基于通过消除具有最大XTD（横向距离）误差的点来减少点数，直到满足所容忍的误差或达到最大点数（函数的两个参数），以先达到哪个为止。

另一种即时流轨迹简化的替代算法（我称之为“流式化”）是： 您将保留GPS传感器提供的点的小缓冲区，每次添加GPS点到缓冲区（包括高程）时，都会计算所有点到连接第一个点与缓冲区的（新添加的）最后一个点的线段的最大XTD（横向距离）。如果具有最大XTD的点违反了您的最大容忍XTD误差（25m给了我很好的结果），则您会在该点处剪切缓冲区，将其注册为要附加到流轨迹中的选定点，修剪缓冲区的尾部直到该剪切点，并继续进行。在轨迹的结尾，缓冲区的最后一个点也会被添加/刷新到解决方案中。 该算法足够轻便，可以在AndroidWear智能手表上运行，并且无论您移动速度快慢或停留在同一地点多长时间，都会产生最佳输出。唯一重要的事情是您的轨迹形状。您可以继续多分钟/公里，只要您沿着直线移动（在+/-容忍XTD误差偏差范围内的走廊），则流化算法仅输出2个点：上一个曲线的退出点和下一个曲线的入口点。

- Afonso Santos

Answer 4

你想要丢弃那些不感兴趣的点。因此，你需要一个计算点的有趣程度的函数，然后你可以计算所有点的有趣程度并丢弃最不有趣的N个点，其中你选择的N足以减少数据集。听起来你对有趣的定义相当于高加速度（偏离直线运动），这很容易计算。

- Raedwald

---

我事先不知道我的目标分数是多少。但一般来说，相当简单的解决方案是为每个点设置一个简单的度量标准，以确定它有多有趣（最好基于其前面和后面的“k”个点的滑动窗口）。你有想过这个指标可能会是什么样子吗？我已经尝试过了，但是无法想出一个合适的。 - GreyCat

让兴趣点为x_2，前一个点为x_1，下一个点为x_3。假设你在这些点的时间分别为t_1、t_2、t_3。那么该点之前的速度为v_12 = (x_2 - x_1) / (t_2 - t_1)，之后的速度为v_23 = (x_3 - x_2) / (t_3 - t_2)。加速度向量为a = (v_23 - v_13) / (t_3 - t_1)。你需要使用该向量的大小，即|a|。 - Raedwald

这将是瞬时加速度的近似值，而不是滑动窗口中加权平均加速度。我不确定这会起作用 - 即它将准确显示非有趣点，但保证所有有趣点都会留下。 - GreyCat

Answer 5

我遇到了类似的问题。GPS设备获取点的速率比实际需要的要快得多。许多点在地理上彼此之间并不远。我采取的方法是使用Haversine公式计算点之间的距离。如果距离不大于我的阈值（在我的情况下为0.1英里），我就抛弃这个点。这可以快速将点的数量减少到可管理的大小。

我不知道您需要什么语言。这是我正在开发的一个C#项目。在底部，您会找到Haversine代码。

http://blog.bobcravens.com/2010/09/gps-using-the-netduino/

希望这能帮助你入门。

Bob

- rcravens

---

谢谢，但是你的例子比我需要的简单得多。如果我正确理解了你的代码，你只是过滤掉与前一个点距离差不大的点。我想更简化，通过检查我们是否在一段时间内保持相同的恒定速度来实现。最后，你使用的是 Haversine 公式，而最好使用 Vincenty 公式 - OpenLayers 包括该公式的实现。无论如何，感谢您的回答 :) - GreyCat

@GreyCat 为什么使用Vicinity公式比Haversine更好？ - NickG

Haversine的精度要低得多：它假设行星是球体，而Vincenty则假设是扁球体，这更接近地球的实际情况。 - GreyCat

@GreyCat 在这种情况下，准确性几乎是无关紧要的。当你已经在一开始丢弃大部分数据时，你并不需要准确性 :) 对于我们所讨论的简化GPS轨迹的微小距离（小于1英里），如果判断该轨迹点是否需要时，点偏出几英尺是否真的很重要呢？哈弗辛算法更快... - NickG

真的，但如果我们回到原始问题的上下文中，我们最终不会使用它们中的任何一个 - 实际上，只需在Douglas-Peucker 3D算法中使用多边形坐标+时间即可获得很好的结果。 - GreyCat

对于非常接近的点，使用Haversine公式计算距离是绰绰有余的。你甚至可以使用简单的勾股定理来计算。https://www.mkompf.com/gps/distcalc.html - Christian Rapp

Answer 6

这可能是NP难问题。假设您有A、B、C、D、E点。

让我们尝试一个简单的确定性算法。假设您计算从点B到线段A-C的距离小于您的阈值（1米）。所以您删除B。然后您尝试相同的操作，将C移动到A-D的线上，但它更大，D则向C-E的线移动，这也更大。

但事实证明，最优解是A、B、E，因为点C和D靠近线B-E，但位于相反的侧面。

如果您删除一个点，您不能确定它应该保留哪些点，除非您尝试每个可能的解决方案（在n=80上，大小可以为n^n，这超过了已知宇宙中最少的原子数）。

下一步：尝试暴力或分支限界算法。不可扩展，在实际规模中不起作用。您可以安全地跳过此步骤 :)

下一步：首先使用确定性算法，然后再改进为元启发式算法（禁忌搜索、模拟退火、遗传算法）。在Java中有几个开源实现，例如Drools Planner。

总的来说，你可能会得到一个可行的解决方案（虽然不是最优解），因为你只有一个约束条件。

这个问题的远亲可能是旅行商问题变体，其中销售员不能访问所有城市，而是必须选择一些城市。

- Geoffrey De Smet

---

如果我们努力寻找一个真正最优的解决方案（给定应该留下的目标点数），那么是的，它可能是NP难问题，但对我来说“足够好”的解决方案就可以了。基本上，它归结为在由直线段组成的“（x，y，t）”三维空间中找到一条线的足够好的近似值。 - GreyCat

Answer 7

试试这个免费的开源在线服务：

https://opengeo.tech/maps/gpx-simplify-optimizer/

- stefcud

---

你能解释一下我在哪里可以找到那个服务的源代码吗？ - GreyCat

啊，原来是RDP实现。谢谢！ - GreyCat

是的，如果你想尝试其他算法，请fork该Github仓库代码！ - stefcud

Answer 8

一个非常简单的方法是反复删除创建其邻居之间最大角度（在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

- Olathe

Answer 9

不确定这个方法能否奏效，但是可以先将您的点列表中的距离计算出来，从而得到整个路线的总距离，然后决定一个分辨率距离，根据每个x米的步长进行位置的线性插值。也就是说，对于每个固定点，您都有一个“距离起点”的度量，您只需插值整个路线上n*x处的位置即可（您可以决定需要多少个点，并将总距离除以此来获得分辨率距离）。在此基础上，您还可以添加一个窗口函数，取当前点+/-z个点，并应用加权，例如exp(-k*dist^2/accuracy^2)，以获取一组点的加权平均值，其中dist是从原始插值点到距离的距离，accuracy是GPS位置的假定精度。

- aronp

Answer 10

我猜你需要保留改变方向的点。如果你将轨迹分割成一组具有恒定方向的区间，你可以只保留这些区间的边界点。
而且，正如Raedwald所指出的那样，你需要保留加速度不为零的点。

- Victor Sorokin