|
第一部分 问题描述
1.1 具体任务
本次作业任务是轨迹压缩，给定一个GPS数据记录文件，每条记录包含经度和维度两个坐标字段，所有记录的经纬度坐标构成一条轨迹，要求采用合适的压缩算法，使得压缩后轨迹的距离误差小于30m。
1.2 程序输入
本程序输入是一个GPS数据记录文件。
1.3 数据输出
输出形式是文件，包括三部分，压缩后点的ID序列及坐标、点的个数、平均距离误差、压缩率
第二部分 问题解答
根据问题描述，我们对问题进行求解，问题求解分为以下几步：
2.1 数据预处理
本次程序输入为GPS数据记录文件，共有3150行记录，每行记录又分为若干个字段，根据题意，我们只需关注经度和纬度坐标字段即可，原始数据文件部分记录如图2.1所示：
图2.1 原始数据文件部分记录示意图
如图2.1所示，原始数据文件每条记录中经纬度坐标字段数据的保存格式是典型的GPS坐标表达方式，即度分格式，形式为dddmm.mmmm，其中ddd表示度，mm.mmmm表示分，小数点前面表示分的整数部分，小数点后表示分的小数部分；本次数据预处理，为方便后面两个坐标点之间距离的计算，我们需要将度分格式的经纬度坐标数据换算成度的形式，换算方法是ddd+mm.mmmm/60，此处我们保留小数点后6位数字，换算后的形式为ddd.xxxxxx。
我们以第一条记录中经纬度坐标（11628.2491，3955.6535）为例，换算后的结果为（116.470818，39.927558），所有记录中经纬度坐标都使用方法进行，并且可以为每一个转换后的坐标点生成一个ID，进行唯一标识，压缩后，我们只需输出所有被保留点的ID即可。
2.2 Douglas-Peucker轨迹压缩算法
轨迹压缩算法分为两大类，分别是无损压缩和有损压缩，无损压缩算法主要包括哈夫曼编码，有损压缩算法又分为批处理方式和在线数据压缩方式，其中批处理方式又包括DP（Douglas-Peucker）算法、TD-TR（Top-Down Time-Ratio）算法和Bellman算法，在线数据压缩方式又包括滑动窗口、开放窗口、基于安全区域的方法等。
由于时间有限，本次轨迹压缩，我们决定采用相对简单的DP算法。
DP算法步骤如下：
（1）在轨迹曲线在曲线首尾两点A，B之间连接一条直线AB，该直线为曲线的弦；
（2）遍历曲线上其他所有点，求每个点到直线AB的距离，找到最大距离的点C，最大距离记为dmax；
（3）比较该距离dmax与预先定义的阈值Dmax大小，如果dmax<Dmax，则将该直线AB作为曲线段的近似，曲线段处理完毕；
（4）若dmax>=Dmax，则使C点将曲线AB分为AC和CB两段，并分别对这两段进行（1）~（3）步处理；
（5）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即为原始曲线的路径。
2.3 点到直线的距离
DP算法中需要求点到直线的距离，该距离指的是垂直欧式距离，即直线AB外的点C到直线AB的距离d，此处A、B、C三点均为经纬度坐标；我们采用三角形面积相等法求距离d，具体方法是：A、B、C三点构成三角形，该三角形的面积有两种求法，分别是普通方法（底x高/2）和海伦公式，海伦公式如下：
假设有一个三角形，边长分别为a、b、c，三角形的面积S可由以下公式求得：
其中p为半周长：
我们通过海伦公式求得三角形面积，然后就可以求得高的大小，此处高即为距离d。要想用海伦公式，必须求出A、B、C三点两两之间的距离，该距离公式是由老师给出的，直接调用距离函数即可。
注意：求出距离后，要加上绝对值，以防止距离为负数。
2.4 平均误差求解
平均误差指的是压缩时忽略的那些点到对应线段的距离之和除以总点数得到的数值。
2.5 压缩率求解
压缩率的计算公式如下：
2.6 数据结果文件的生成
经过上面的处理和计算，我们将压缩后剩余点的ID和88 | 
转播
