简化/优化GPS轨道 [英] Simplification / optimization of GPS track

问题描述

我有一个GPS轨道，由 gpxlogger（1）产生（作为 gpsd ）。 GPS接收器每隔1秒更新一次坐标，gpxlogger的逻辑非常简单，它写下位置（ lat ， lon ）， n 秒（ ）从GPS接收到的时间戳（ ele ）和时间戳（ time >在我的情况下，n = 3 ）。

在写下了几个小时的跟踪记录后，gpxlogger保存了数兆字节的GPX文件，点。之后，我尝试在地图上绘制此曲目，并将其与 OpenLayers 一起使用。它的工作原理，但数千点使地图使用草率和缓慢的经验。

据我所知，有几千点不理想。有很多点可以被删除而不会丢失任何东西：当几个点大致构成直线和时，我们以相同的恒定速度移动，我们可以离开首先和最后一点，并抛出其他任何东西。

我想用 gpsbabel 用于这种轨道简化/优化工作，但是，唉，它的简化过滤器仅适用于路线，即只分析几何形状的路径，不带时间戳（即不检查速度大致恒定）。

一些现成的实用程序/库/算法可用于优化轨道？或者可能是我缺少一些聪明的选项与gpsbabel？

解决方案

是的，如前所述，Douglas-Peucker算法是简化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在C ++中

您的x和y坐标可能以纬度/经度为度数，而z（时间）坐标可能以秒为单位，因为unix时代。您可以通过确定适当的时空关系来解决这种差异;假设您想在1平方英里的地图区域上查看一天的活动。将这种关系设想为1英里乘1英里乘1天的立方体，则必须对时间变量进行预分频。从度数转换为表面距离并不重要，但对于这种情况，我们简化并说一度是60英里;那么一英里是0.0167度。一天是86400秒;那么为了使这些单位相当，我们的时间戳的预分频因子是.0167 / 86400，或约1 / 5,000,000。

如果您想要查看GPS在同一个1平方英里地图区域内的活动，而不是2天，时间分辨率变得重要一半，因此将其缩小一倍，达到1 / 10,000,000。玩得开心。

I've got a GPS track, produces 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).

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 anything else.

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).

Is there some ready-made utility / library / algorithm available to optimize tracks? Or may be I'm missing some clever option with gpsbabel?

解决方案

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.

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.

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.

You can find a 3D C++ implementation here: 3D Douglas-Peucker in C++

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.

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屋！