GPS轨迹的简化/优化 [英] Simplification / optimization of GPS track
问题描述
我有一个由 gpxlogger(1) 生成的 GPS 轨迹(作为 gpsd).GPS接收器每1秒更新一次坐标，gpxlogger的逻辑很简单，它记下位置(lat, lon, ele)和时间戳(time) 每 n 秒(在我的例子中为 n = 3)从 GPS 接收.
I've got a GPS track produced by gpxlogger(1) (supplied as a client for gpsd). GPS receiver updates its coordinates every 1 second, gpxlogger's logic is very simple, it writes down location (lat, lon, ele) and a timestamp (time) received from GPS every n seconds (n = 3 in my case).
在写下几个小时的轨迹后，gpxlogger 保存了几兆字节长的 GPX 文件，其中包含数千个点.之后，我尝试在地图上绘制这条轨迹并将其与 OpenLayers 一起使用.它有效，但数千个点使使用地图变得草率而缓慢.
After writing down a several hours worth of track, gpxlogger saves several megabyte long GPX file that includes several thousands of points. Afterwards, I try to plot this track on a map and use it with OpenLayers. It works, but several thousands of points make using the map a sloppy and slow experience.
我知道有几千个次优点.有无数的点可以删除而几乎不会丢失任何东西:当有几个点大致组成直线并且我们在它们之间以相同的恒定速度移动时，我们可以离开第一点和最后一点，其他的都扔掉.
I understand that having several thousands of points of suboptimal. There are myriads of points that can be deleted without losing almost anything: when there are several points making up roughly the straight line and we're moving with the same constant speed between them, we can just leave the first and the last point and throw away anything else.
我曾想过使用 gpsbabel 进行这样的轨道简化/优化工作，但是，唉，它是
I thought of using gpsbabel for such track simplification / optimization job, but, alas, it's simplification filter works only with routes, i.e. analyzing only geometrical shape of path, without timestamps (i.e. not checking that the speed was roughly constant).
是否有一些现成的实用程序/库/算法可用于优化曲目?或者我可能错过了 gpsbabel 的一些聪明选择?
Is there some ready-made utility / library / algorithm available to optimize tracks? Or may be I'm missing some clever option with gpsbabel?
推荐答案
是的，如前所述，Douglas-Peucker 算法是简化 2D 连接路径的直接方法.但正如您所指出的，您需要将其扩展到 3D 案例，以正确简化具有与每个点相关联的固有时间维度的 GPS 轨迹.我已经使用 Douglas-Peucker 的 PHP 实现为我自己的 Web 应用程序这样做了.
Yes, as mentioned before, the Douglas-Peucker algorithm is a straightforward way to simplify 2D connected paths. But as you have pointed out, you will need to extend it to the 3D case to properly simplify a GPS track with an inherent time dimension associated with every point. I have done so for a web application of my own using a PHP implementation of Douglas-Peucker.
只要稍微了解一下算法的工作原理，就很容易将算法扩展到 3D 案例.假设您的输入路径由标记为 A 到 Z 的 26 个点组成.这条路径的最简单版本有两个点，A 和 Z，所以我们从那里开始.想象一下 A 和 Z 之间的线段.现在扫描所有剩余的点 B 到 Y 以找到离线段 AZ 最远的点.假设最远的点是 J.然后，您扫描 B 和 I 之间的点以找到离线段 AJ 最远的点，并扫描点 K 到 Y 以找到离线段 JZ 最远的点，依此类推，直到剩下的点都位于某个所需的距离阈值内.
It's easy to extend the algorithm to the 3D case with a little understanding of how the algorithm works. Say you have input path consisting of 26 points labeled A to Z. The simplest version of this path has two points, A and Z, so we start there. Imagine a line segment between A and Z. Now scan through all remaining points B through Y to find the point furthest away from the line segment AZ. Say that point furthest away is J. Then, you scan the points between B and I to find the furthest point from line segment AJ and scan points K through Y to find the point furthest from segment JZ, and so on, until the remaining points all lie within some desired distance threshold.
这将需要一些简单的向量操作.从逻辑上讲，3D 中的过程与 2D 中的过程相同.如果您发现用您的语言实现的 Douglas-Peucker 算法，它可能已经实现了一些 2D 矢量数学，您需要扩展它们以使用 3 维.
This will require some simple vector operations. Logically, it's the same process in 3D as in 2D. If you find a Douglas-Peucker algorithm implemented in your language, it might have some 2D vector math implemented, and you'll need to extend those to use 3 dimensions.
您可以在此处找到 3D C++ 实现:3DC++ 中的 Douglas-Peucker
You can find a 3D C++ implementation here: 3D Douglas-Peucker in C++
您的 x 和 y 坐标可能以纬度/经度为单位，z(时间)坐标可能以 unix 纪元以来的秒数为单位.您可以通过确定适当的时空关系来解决这种差异；假设您想在 1 平方英里的地图区域内查看一天的活动.将此关系想象为 1 英里 x 1 英里 x 1 天的立方体，您必须预先调整时间变量.从度数到表面距离的转换并非易事，但对于这种情况，我们简化并说 1 度是 60 英里；那么一英里是0.0167度.一天是86400秒；那么为了使单位相等，我们为您的时间戳设置的预分频因子是 0.0167/86400，或大约 1/5,000,000.
Your x and y coordinates will probably be in degrees of latitude/longitude, and the z (time) coordinate might be in seconds since the unix epoch. You can resolve this discrepancy by deciding on an appropriate spatial-temporal relationship; let's say you want to view one day of activity over a map area of 1 square mile. Imagining this relationship as a cube of 1 mile by 1 mile by 1 day, you must prescale the time variable. Conversion from degrees to surface distance is non-trivial, but for this case we simplify and say one degree is 60 miles; then one mile is .0167 degrees. One day is 86400 seconds; then to make the units equivalent, our prescale factor for your timestamp is .0167/86400, or about 1/5,000,000.
例如，如果您想在 2 天内查看同一 1 平方英里地图区域内的 GPS 活动，那么时间分辨率的重要性将降低一半，因此将其进一步缩小两倍，至 1/10,000,000.玩得开心.
If, say, you want to view the GPS activity within the same 1 square mile map area over 2 days instead, time resolution becomes half as important, so scale it down twice further, to 1/10,000,000. Have fun.
这篇关于GPS轨迹的简化/优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
