Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

第一部分 问题描述

1 具体任务

　　本次作业任务是轨迹压缩，给定一个GPS数据记录文件，每条记录包含经度和维度两个坐标字段，所有记录的经纬度坐标构成一条轨迹，要求采用合适的压缩算法，使得压缩后轨迹的距离误差小于30m。

2 程序输入

　　本程序输入是一个GPS数据记录文件。

3 数据输出

　　输出形式是文件，包括三部分，压缩后点的ID序列及坐标、点的个数、平均距离误差、压缩率

第二部分 问题解答

　　根据问题描述，我们对问题进行求解，问题求解分为以下几步：

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 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）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即为原始曲线的路径。

3 点到直线的距离

　　DP算法中需要求点到直线的距离，该距离指的是垂直欧式距离，即直线AB外的点C到直线AB的距离d，此处A、B、C三点均为经纬度坐标；我们采用三角形面积相等法求距离d，具体方法是：A、B、C三点构成三角形，该三角形的面积有两种求法，分别是普通方法（底x高/2）和海伦公式，海伦公式如下：

　　假设有一个三角形，边长分别为a、b、c，三角形的面积S可由以下公式求得：

其中p为半周长：

我们通过海伦公式求得三角形面积，然后就可以求得高的大小，此处高即为距离d。要想用海伦公式，必须求出A、B、C三点两两之间的距离，该距离公式是由老师给出的，直接调用距离函数即可。

注意：求出距离后，要加上绝对值，以防止距离为负数。

4 平均误差求解

　　平均误差指的是压缩时忽略的那些点到对应线段的距离之和除以总点数得到的数值。

5 压缩率求解

　　压缩率的计算公式如下：

6 数据结果文件的生成

　　经过上面的处理和计算，我们将压缩后剩余点的ID和点的个数、平均距离误差、压缩率等参数都写入最终的结果文件中，问题解答完成。

第三部分 代码实现

　　本程序采用Java语言编写，开发环境为IntelliJ idea 14.0.2，代码共分为两个类，一个是ENPoint类，用于保存经纬度点信息，一个是TrajectoryCompressionMain类，用于编写数据处理、DP算法、点到直线距离、求平均误差等函数。

1 程序总流程

　　整个程序流程主要包括以下几个步骤：

　　（1）定义相关ArrayList数组和File对象，其中ArrayList数组对象有三个，分别是原始经纬度坐标数组pGPSArryInit、过滤后的点坐标数组pGPSArrayFilter、过滤并排序后的点坐标数组pGPSArrayFilterSort；File文件对象共有五个，分别是原始数据文件对象fGPS、压缩后的结果数据文件对象oGPS、保持转换后的原始经纬度坐标点的数据文件fInitGPSPoint、仿真测试文件fTestInitPoint和fTestFilterPoint。

　　（2）获取原始点坐标并将其写入到文件中，主要包括读文件和写文件两种操作；

　　（3）进行轨迹压缩；

　　（4）对压缩后的经纬度点坐标进行排序；

　　（5）生成仿真测试文件，并用R语言工具进行图形绘制，得到最终的结果；

　　（6）求平均误差和压缩率，平均误差通过函数求得，压缩率直接计算获得；

　　（7）将最终结果写入结果文件中，包括过滤后的点的ID，点的个数、平均误差和压缩率；

2 具体实现代码

　　（1）ENPoint.java

package cc.xidian.main;import java.text.DecimalFORMat;public class ENPoint implements Comparable<ENPoint>{public int id;//点IDpublic double pe;//经度public double pn;//维度public ENPoint(){}//空构造函数public String toString(){//DecimalFormat df = new DecimalFormat("0.000000");return this.id+"#"+this.pn+","+this.pe;}public String getTestString(){DecimalFormat df = new DecimalFormat("0.000000");return df.format(this.pn)+","+df.format(this.pe);}public String getResultString(){DecimalFormat df = new DecimalFormat("0.000000");return this.id+"#"+df.format(this.pn)+","+df.format(this.pe);}@Overridepublic int compareTo(ENPoint other) {if(this.id<other.id) return -1; else if(this.id>other.id) return1; elsereturn0;}}