跑步轨迹简化

作为一家专业的马拉松技术服务公司，每天都有大量的用户通过我们的app上传跑步记录。 为了能更加直观的感受用户的跑步习惯和分布，我将一段时间内北京的用户跑步记录简化后，通过mapbox地图绘制出来。效果图如下

image

为什么要简化

马拉松跑步用户一般的跑步距离都会大于10公里，而我们的跑步软件一般采样时间为1s，因此一次跑步记录的大小大概为几百kb至几M。如果让mapbox直接加载几万条原始跑步记录（大小估计上G），那么基本上是绘制不出来的。 为了能在mapbox地图引擎上绘制如此多的跑步记录，必须在不影响效果的前提下将跑步记录简化到足够小

如何简化

一般的图形图像算法，提供了直线检测算法，例如hough变换等。 其算法的基本思想是在一个参数空间中通过计算累计结果的局部最大值得到一个符合该特定形状的集合。 但跑步记录有个很大的特征是跑步的起点和终点不能改变，并且跑步轨迹应该由多条收尾相连的线段拟合而成。所以常规的直线检测算法并不合适。

数据结构

线段：对多个点拟合的线段
轨迹：多条线段首尾相连而成
轨迹集合：一次跑步为一个轨迹集合，由多个轨迹的组成

typedef struct LineParam 
{
    double   a; //直线方程参数
    double   b; //直线方程参数
    double   c; //直线方程参数
    double   maxDist; //最大距离
    double   variance; //平均方差
    double   distance; //最后两个点的距离
    double   length; //线段长度
}LineParam;//线段方程参数

typedef struct regressionConfig 
{
    double  minPoints;                  //最少点数量
    double  maxVariance;                //最大方差
    double  maxDist;                    //最大距离
    double  minVariance;                //最小方差
}rgConfig; //线段回归阈值

typedef struct SegmentStruct
{
    LineParam        lParam; //线性回归方差参数
    vector<LTPoint>  points; //组成线段的点集
}Segment; 线段

typedef vector<Segment> Segments;//轨迹
typedef vector<Segments> Tracks; //多条轨迹的集合

简化步骤

1. 计算跑步记录的2D包围盒
2. 将跑步记录由经纬度坐标转换到包围盒顶点为原点的局部坐标系
3. 从跑步记录起点开始跟踪，计算当前线段的参数
4. 若当前线段的任一参数超过线段回归阈值，则重开一条线段
5. 若当前两点距离超过阈值，则重开一条轨迹
6. 重复步骤4、5直至跑步记录终点，得到轨迹集合
7. 将轨迹集合的所有点转换到wgs84坐标系
8. 将数据输出成geojson格式
9. 启动web服务，调用mapbox的api加载geojson格式数据

下图即一条轨迹简化前后对比，红色轨迹是原始的跑步记录，可以看到是由密集的点组成。蓝色的轨迹是简化后的效果，只由几条线段组成，数据量大概减少了95%左右。

image

异常处理

由于以下因素的存在，导致跑步记录中可能会出现近似直线的数据，为不合法的数据

1. 存在定位漂移的情况
2. 跑步引擎的自动补偿（当gps信号恢复时，自动与最近一个点连直线）
3. 用户乘坐轨道交通工具
4. 用户跑直线

通过以下策略进行检测，去除包含直线的跑步记录

1. 跑步记录中存在相邻点距离大于1KM
2. 跑步记录简化成多个线段，存在线段对应的跑步定位点距离线段最大距离小于3cm的线段，且线段长度大于500米
3. 将跑步记录简化成多个线段，存在线段对应的跑步定位点距离拟合的直线平均方差小于2cm的线段，且线段长度大于500米