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

package cc.xidian.main;
import java.text.DecimalFormat;
/**
* Created by hadoop on 2015/12/20.
*/
public class ENPoint implements Comparable<ENPoint>{
public int id;
//点ID
public 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);
}
@Override
public int compareTo(ENPoint other) {
	if(this.id<other.id) return -1; else if(this.id>other.id) return1; else
	return0;
}
}

package cc.xidian.main;
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;
import java.util.List;
/**
* Created by hadoop on 2015/12/19.
*/
public class TrajectoryCompressionMain{
	public static void main(String[] args)throws Exception{
		//-----------------------1、相关ArrayList数组和File对象的声明和定义-------------------------------------------------//
		ArrayList<ENPoint> pGPSArrayInit = new ArrayList<ENPoint>();
		//原纪录经纬度坐标数组
		ArrayList<ENPoint> pGPSArrayFilter = new ArrayList<ENPoint>();
		//过滤后的经纬度坐标数组
		ArrayList<ENPoint> pGPSArrayFilterSort = new ArrayList<ENPoint>();
		//过滤并排序后的经纬度坐标数组
		File fGPS = new File("2007-10-14-GPS.log");
		//原始数据文件对象
		File oGPS = new File("2015-12-25-GPS-Result.log");
		//过滤后的结果数据文件对象
		//保持转换成度后的原始经纬度数据文件，保持格式为“ID#经纬值，纬度值”，其中经度和维度单位为度，并保留小数点后6位数字
		File fInitGPSPoint = new File("2007-10-14-GPS-ENPoint.log");
		//保持转换后的原始经纬度坐标点的数据文件
		File fTestInitPoint = new File("2007-10-14-GPS-InitTestPoint.log");
		//用于仿真的原始经纬度坐标点数据文件
		File fTestFilterPoint = new File("2015-12-25-GPS-FilterTestPoint.log");
		//用于仿真的过滤后的经纬度坐标点数据文件
		//-------------------------2、获取原始点坐标并将其写入到文件中-------------------------------------------------------//
		pGPSArrayInit = getENPointFromFile(fGPS);
		//从原始数据文件中获取转换后的经纬度坐标点数据，存放到ArrayList数组中
		writeInitPointToFile(fInitGPSPoint, pGPSArrayInit);
		//将转换后的原始经纬度点数据写入文件中
		System.out.println(pGPSArrayInit.size());
		//输出原始经纬度点坐标的个数
		//-------------------------3、进行轨迹压缩-----------------------------------------------------------------------//
		double DMax = 30.0;
		//设定最大距离误差阈值
		pGPSArrayFilter.add(pGPSArrayInit.get(0));
		//获取第一个原始经纬度点坐标并添加到过滤后的数组中
		pGPSArrayFilter.add(pGPSArrayInit.get(pGPSArrayInit.size()-1));
		//获取最后一个原始经纬度点坐标并添加到过滤后的数组中
		ENPoint[] enpInit = new ENPoint[pGPSArrayInit.size()];
		//使用一个点数组接收所有的点坐标，用于后面的压缩
		Iterator<ENPoint> iInit = pGPSArrayInit.iterator();
		int jj=0;
		while(iInit.hasNext()){
			enpInit[jj] = iInit.next();
			jj++;
		}
		//将ArrayList中的点坐标拷贝到点数组中
		int start = 0;
		//起始下标
		int end = pGPSArrayInit.size()-1;
		//结束下标
		TrajCompressC(enpInit,pGPSArrayFilter,start,end,DMax);
		//DP压缩算法
		System.out.println(pGPSArrayFilter.size());
		//输出压缩后的点数
		//-------------------------4、对压缩后的经纬度点坐标数据按照ID从小到大排序---------------------------------------------//
		ENPoint[] enpFilter = new ENPoint[pGPSArrayFilter.size()];
		//使用一个点数组接收过滤后的点坐标，用于后面的排序
		Iterator<ENPoint> iF = pGPSArrayFilter.iterator();
		int i = 0;
		while(iF.hasNext()){
			enpFilter[i] = iF.next();
			i++;
		}
		//将ArrayList中的点坐标拷贝到点数组中
		Arrays.sort(enpFilter);
		//进行排序
		for (int j=0;j<enpFilter.length;j++){
			pGPSArrayFilterSort.add(enpFilter[j]);
			//将排序后的点坐标写到一个新的ArrayList数组中
		}
		//-------------------------5、生成仿真测试文件--------------------------------------------------------------------//
		writeTestPointToFile(fTestInitPoint,pGPSArrayInit);
		//将原始经纬度数据点写入仿真文件中，格式为“经度，维度”
		writeTestPointToFile(fTestFilterPoint, pGPSArrayFilterSort);
		//将过滤后的经纬度数据点写入仿真文件中，格式为“经度，维度”
		//-------------------------6、求平均误差-------------------------------------------------------------------------//
		double mDError = getMeanDistError(pGPSArrayInit,pGPSArrayFilterSort);
		//求平均误差
		System.out.println(mDError);
		//-------------------------7、求压缩率--------------------------------------------------------------------------//
		double cRate = (double)pGPSArrayFilter.size()/pGPSArrayInit.size()*100;
		//求压缩率
		System.out.println(cRate);
		//-------------------------8、生成最终结果文件--------------------------------------------------------------------//
		//将最终结果写入结果文件中，包括过滤后的点的ID，点的个数、平均误差和压缩率
		writeFilterPointToFile(oGPS,pGPSArrayFilterSort,mDError,cRate);
		//------------------------------------------------------------------------------------------------------------//
	}
	/**
*函数功能：从源文件中读出所以记录中的经纬度坐标，并存入到ArrayList数组中，并将其返回
* @param fGPS：源数据文件
* @return pGPSArrayInit：返回保存所有点坐标的ArrayList数组
* @throws Exception
*/
	public static ArrayList<ENPoint> getENPointFromFile(File fGPS)throws Exception{
		ArrayList<ENPoint> pGPSArray = new ArrayList<ENPoint>();
		if(fGPS.exists()&&fGPS.isFile()){
			InputStreamReader read = new InputStreamReader(new FileInputStream(fGPS));
			BufferedReader bReader = new BufferedReader(read);
			String str;
			String[] strGPS;
			int i = 0;
			while((str = bReader.readLine())!=null){
				strGPS = str.split(" ");
				ENPoint p = new ENPoint();
				p.id = i;
				i++;
				p.pe = (dfTodu(strGPS[3]));
				p.pn = (dfTodu(strGPS[5]));
				pGPSArray.add(p);
			}
			bReader.close();
		}
		return pGPSArray;
	}
	/**
* 函数功能：将过滤后的点的经纬度坐标、平均距离误差、压缩率写到结果文件中
* @param outGPSFile：结果文件
* @param pGPSPointFilter：过滤后的点
* @param mDerror：平均距离误差
* @param cRate：压缩率
* @throws Exception
*/
	public static void writeFilterPointToFile(File outGPSFile,ArrayList<ENPoint> pGPSPointFilter,
	double mDerror,double cRate)throws Exception{
		Iterator<ENPoint> iFilter = pGPSPointFilter.iterator();
		RandomAccessFile rFilter = new RandomAccessFile(outGPSFile,"rw");
		while(iFilter.hasNext()){
			ENPoint p = iFilter.next();
			String sFilter = p.getResultString()+"\n";
			byte[] bFilter = sFilter.getBytes();
			rFilter.write(bFilter);
		}
		String strmc = "#"+Integer.toString(pGPSPointFilter.size())+","+
		double.toString(mDerror)+","+double.toString(cRate)+"%"+"#"+"\n";
		byte[] bmc = strmc.getBytes();
		rFilter.write(bmc);
		rFilter.close();
	}
	/**
* 函数功能：将转换后的原始经纬度数据点存到文件中
* @param outGPSFile
* @param pGPSPointFilter
* @throws Exception
*/
	public static void writeInitPointToFile(File outGPSFile,ArrayList<ENPoint> pGPSPointFilter)throws Exception{
		Iterator<ENPoint> iFilter = pGPSPointFilter.iterator();
		RandomAccessFile rFilter = new RandomAccessFile(outGPSFile,"rw");
		while(iFilter.hasNext()){
			ENPoint p = iFilter.next();
			String sFilter = p.toString()+"\n";
			byte[] bFilter = sFilter.getBytes();
			rFilter.write(bFilter);
		}
		rFilter.close();
	}
	/**
* 函数功能：将数组中的经纬度点坐标数据写入测试文件中，用于可视化测试
* @param outGPSFile：文件对象
* @param pGPSPointFilter：点数组
* @throws Exception
*/
	public static void writeTestPointToFile(File outGPSFile,ArrayList<ENPoint> pGPSPointFilter)throws Exception{
		Iterator<ENPoint> iFilter = pGPSPointFilter.iterator();
		RandomAccessFile rFilter = new RandomAccessFile(outGPSFile,"rw");
		while(iFilter.hasNext()){
			ENPoint p = iFilter.next();
			String sFilter = p.getTestString()+"\n";
			byte[] bFilter = sFilter.getBytes();
			rFilter.write(bFilter);
		}
		rFilter.close();
	}
	/**
* 函数功能：将原始经纬度坐标数据转换成度
* @param str：原始经纬度坐标
* @return ：返回对于的度数据
*/
	public static double dfTodu(String str){
		int indexD = str.indexOf(‘.‘);
		String strM = str.substring(0,indexD-2);
		String strN = str.substring(indexD-2);
		double d = double.parsedouble(strM)+double.parsedouble(strN)/60;
		return d;
	}
	/**
* 函数功能：保留一个double数的小数点后六位
* @param d：原始double数
* @return 返回转换后的double数
*/
	public static double getPointSix(double d){
		DecimalFormat df = new DecimalFormat("0.000000");
		return double.parsedouble(df.format(d));
	}
	/**
* 函数功能：使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
* @param pA：起始点
* @param pB：结束点
* @param pX：第三个点
* @return distance：点pX到pA和pB所在直线的距离
*/
	public static double distToSegment(ENPoint pA,ENPoint pB,ENPoint pX){
		double a = Math.abs(geoDist(pA, pB));
		double b = Math.abs(geoDist(pA, pX));
		double c = Math.abs(geoDist(pB, pX));
		double p = (a+b+c)/2.0;
		double s = Math.sqrt(Math.abs(p*(p-a)*(p-b)*(p-c)));
		double d = s*2.0/a;
		return d;
	}
	/**
* 函数功能：用老师给的看不懂的方法求两个经纬度点之间的距离
* @param pA：起始点
* @param pB：结束点
* @return distance：距离
*/
	public static double geoDist(ENPoint pA,ENPoint pB)
	{
		double radLat1 = Rad(pA.pn);
		double radLat2 = Rad(pB.pn);
		double delta_lon = Rad(pB.pe - pA.pe);
		double top_1 = Math.cos(radLat2) * Math.sin(delta_lon);
		double top_2 = Math.cos(radLat1) * Math.sin(radLat2) - Math.sin(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
		double top = Math.sqrt(top_1 * top_1 + top_2 * top_2);
		double bottom = Math.sin(radLat1) * Math.sin(radLat2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.cos(delta_lon);
		double delta_sigma = Math.atan2(top, bottom);
		double distance = delta_sigma * 6378137.0;
		return distance;
	}
	/**
* 函数功能：角度转弧度
* @param d：角度
* @return 返回的是弧度
*/
	public static double Rad(double d)
	{
		return d * Math.PI / 180.0;
	}
	/**
* 函数功能：根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
* @param enpInit：原始经纬度坐标点数组
* @param enpArrayFilter：保持过滤后的点坐标数组
* @param start：起始下标
* @param end：终点下标
* @param DMax：预先指定好的最大距离误差
*/
	public static void TrajCompressC(ENPoint[] enpInit,ArrayList<ENPoint> enpArrayFilter,
	int start,int end,double DMax){
		if(start < end){
			//递归进行的条件
			double maxDist = 0;
			//最大距离
			int cur_pt = 0;
			//当前下标
			for (int i=start+1;i<end;i++){
				double curDist = distToSegment(enpInit[start],enpInit[end],enpInit[i]);
				//当前点到对应线段的距离
				if(curDist > maxDist){
					maxDist = curDist;
					cur_pt = i;
				}
				//求出最大距离及最大距离对应点的下标
			}
			//若当前最大距离大于最大距离误差
			if(maxDist >= DMax){
				enpArrayFilter.add(enpInit[cur_pt]);
				//将当前点加入到过滤数组中
				//将原来的线段以当前点为中心拆成两段，分别进行递归处理
				TrajCompressC(enpInit,enpArrayFilter,start,cur_pt,DMax);
				TrajCompressC(enpInit,enpArrayFilter,cur_pt,end,DMax);
			}
		}
	}
	/**
* 函数功能：求平均距离误差
* @param pGPSArrayInit：原始数据点坐标
* @param pGPSArrayFilterSort：过滤后的数据点坐标
* @return ：返回平均距离
*/
	public static double getMeanDistError(
	ArrayList<ENPoint> pGPSArrayInit,ArrayList<ENPoint> pGPSArrayFilterSort){
		double sumDist = 0.0;
		for (int i=1;i<pGPSArrayFilterSort.size();i++){
			int start = pGPSArrayFilterSort.get(i-1).id;
			int end = pGPSArrayFilterSort.get(i).id;
			for (int j=start+1;j<end;j++){
				sumDist += distToSegment(
				pGPSArrayInit.get(start),pGPSArrayInit.get(end),pGPSArrayInit.get(j));
			}
		}
		double meanDist = sumDist/(pGPSArrayInit.size());
		return meanDist;
	}
}