Java編程實現(xiàn)軌跡壓縮之Douglas-Peucker算法詳細(xì)代碼

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;
//經(jīng)度
public double pn;
//維度
public ENPoint(){
}
//空構(gòu)造函數(shù)
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、相關(guān)ArrayList數(shù)組和File對象的聲明和定義-------------------------------------------------//
		ArrayList<ENPoint> pGPSArrayInit = new ArrayList<ENPoint>();
		//原紀(jì)錄經(jīng)緯度坐標(biāo)數(shù)組
		ArrayList<ENPoint> pGPSArrayFilter = new ArrayList<ENPoint>();
		//過濾后的經(jīng)緯度坐標(biāo)數(shù)組
		ArrayList<ENPoint> pGPSArrayFilterSort = new ArrayList<ENPoint>();
		//過濾并排序后的經(jīng)緯度坐標(biāo)數(shù)組
		File fGPS = new File("2007-10-14-GPS.log");
		//原始數(shù)據(jù)文件對象
		File oGPS = new File("2015-12-25-GPS-Result.log");
		//過濾后的結(jié)果數(shù)據(jù)文件對象
		//保持轉(zhuǎn)換成度后的原始經(jīng)緯度數(shù)據(jù)文件，保持格式為“ID#經(jīng)緯值，緯度值”，其中經(jīng)度和維度單位為度，并保留小數(shù)點后6位數(shù)字
		File fInitGPSPoint = new File("2007-10-14-GPS-ENPoint.log");
		//保持轉(zhuǎn)換后的原始經(jīng)緯度坐標(biāo)點的數(shù)據(jù)文件
		File fTestInitPoint = new File("2007-10-14-GPS-InitTestPoint.log");
		//用于仿真的原始經(jīng)緯度坐標(biāo)點數(shù)據(jù)文件
		File fTestFilterPoint = new File("2015-12-25-GPS-FilterTestPoint.log");
		//用于仿真的過濾后的經(jīng)緯度坐標(biāo)點數(shù)據(jù)文件
		//-------------------------2、獲取原始點坐標(biāo)并將其寫入到文件中-------------------------------------------------------//
		pGPSArrayInit = getENPointFromFile(fGPS);
		//從原始數(shù)據(jù)文件中獲取轉(zhuǎn)換后的經(jīng)緯度坐標(biāo)點數(shù)據(jù)，存放到ArrayList數(shù)組中
		writeInitPointToFile(fInitGPSPoint, pGPSArrayInit);
		//將轉(zhuǎn)換后的原始經(jīng)緯度點數(shù)據(jù)寫入文件中
		System.out.println(pGPSArrayInit.size());
		//輸出原始經(jīng)緯度點坐標(biāo)的個數(shù)
		//-------------------------3、進(jìn)行軌跡壓縮-----------------------------------------------------------------------//
		double DMax = 30.0;
		//設(shè)定最大距離誤差閾值
		pGPSArrayFilter.add(pGPSArrayInit.get(0));
		//獲取第一個原始經(jīng)緯度點坐標(biāo)并添加到過濾后的數(shù)組中
		pGPSArrayFilter.add(pGPSArrayInit.get(pGPSArrayInit.size()-1));
		//獲取最后一個原始經(jīng)緯度點坐標(biāo)并添加到過濾后的數(shù)組中
		ENPoint[] enpInit = new ENPoint[pGPSArrayInit.size()];
		//使用一個點數(shù)組接收所有的點坐標(biāo)，用于后面的壓縮
		Iterator<ENPoint> iInit = pGPSArrayInit.iterator();
		int jj=0;
		while(iInit.hasNext()){
			enpInit[jj] = iInit.next();
			jj++;
		}
		//將ArrayList中的點坐標(biāo)拷貝到點數(shù)組中
		int start = 0;
		//起始下標(biāo)
		int end = pGPSArrayInit.size()-1;
		//結(jié)束下標(biāo)
		TrajCompressC(enpInit,pGPSArrayFilter,start,end,DMax);
		//DP壓縮算法
		System.out.println(pGPSArrayFilter.size());
		//輸出壓縮后的點數(shù)
		//-------------------------4、對壓縮后的經(jīng)緯度點坐標(biāo)數(shù)據(jù)按照ID從小到大排序---------------------------------------------//
		ENPoint[] enpFilter = new ENPoint[pGPSArrayFilter.size()];
		//使用一個點數(shù)組接收過濾后的點坐標(biāo)，用于后面的排序
		Iterator<ENPoint> iF = pGPSArrayFilter.iterator();
		int i = 0;
		while(iF.hasNext()){
			enpFilter[i] = iF.next();
			i++;
		}
		//將ArrayList中的點坐標(biāo)拷貝到點數(shù)組中
		Arrays.sort(enpFilter);
		//進(jìn)行排序
		for (int j=0;j<enpFilter.length;j++){
			pGPSArrayFilterSort.add(enpFilter[j]);
			//將排序后的點坐標(biāo)寫到一個新的ArrayList數(shù)組中
		}
		//-------------------------5、生成仿真測試文件--------------------------------------------------------------------//
		writeTestPointToFile(fTestInitPoint,pGPSArrayInit);
		//將原始經(jīng)緯度數(shù)據(jù)點寫入仿真文件中，格式為“經(jīng)度，維度”
		writeTestPointToFile(fTestFilterPoint, pGPSArrayFilterSort);
		//將過濾后的經(jīng)緯度數(shù)據(jù)點寫入仿真文件中，格式為“經(jīng)度，維度”
		//-------------------------6、求平均誤差-------------------------------------------------------------------------//
		double mDError = getMeanDistError(pGPSArrayInit,pGPSArrayFilterSort);
		//求平均誤差
		System.out.println(mDError);
		//-------------------------7、求壓縮率--------------------------------------------------------------------------//
		double cRate = (double)pGPSArrayFilter.size()/pGPSArrayInit.size()*100;
		//求壓縮率
		System.out.println(cRate);
		//-------------------------8、生成最終結(jié)果文件--------------------------------------------------------------------//
		//將最終結(jié)果寫入結(jié)果文件中，包括過濾后的點的ID，點的個數(shù)、平均誤差和壓縮率
		writeFilterPointToFile(oGPS,pGPSArrayFilterSort,mDError,cRate);
		//------------------------------------------------------------------------------------------------------------//
	}
	/**
*函數(shù)功能：從源文件中讀出所以記錄中的經(jīng)緯度坐標(biāo)，并存入到ArrayList數(shù)組中，并將其返回
* @param fGPS：源數(shù)據(jù)文件
* @return pGPSArrayInit：返回保存所有點坐標(biāo)的ArrayList數(shù)組
* @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;
	}
	/**
* 函數(shù)功能：將過濾后的點的經(jīng)緯度坐標(biāo)、平均距離誤差、壓縮率寫到結(jié)果文件中
* @param outGPSFile：結(jié)果文件
* @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();
	}
	/**
* 函數(shù)功能：將轉(zhuǎn)換后的原始經(jīng)緯度數(shù)據(jù)點存到文件中
* @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();
	}
	/**
* 函數(shù)功能：將數(shù)組中的經(jīng)緯度點坐標(biāo)數(shù)據(jù)寫入測試文件中，用于可視化測試
* @param outGPSFile：文件對象
* @param pGPSPointFilter：點數(shù)組
* @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();
	}
	/**
* 函數(shù)功能：將原始經(jīng)緯度坐標(biāo)數(shù)據(jù)轉(zhuǎn)換成度
* @param str：原始經(jīng)緯度坐標(biāo)
* @return ：返回對于的度數(shù)據(jù)
*/
	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;
	}
	/**
* 函數(shù)功能：保留一個double數(shù)的小數(shù)點后六位
* @param d：原始double數(shù)
* @return 返回轉(zhuǎn)換后的double數(shù)
*/
	public static double getPointSix(double d){
		DecimalFormat df = new DecimalFormat("0.000000");
		return double.parsedouble(df.format(d));
	}
	/**
* 函數(shù)功能：使用三角形面積（使用海倫公式求得）相等方法計算點pX到點pA和pB所確定的直線的距離
* @param pA：起始點
* @param pB：結(jié)束點
* @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;
	}
	/**
* 函數(shù)功能：用老師給的看不懂的方法求兩個經(jīng)緯度點之間的距離
* @param pA：起始點
* @param pB：結(jié)束點
* @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;
	}
	/**
* 函數(shù)功能：角度轉(zhuǎn)弧度
* @param d：角度
* @return 返回的是弧度
*/
	public static double Rad(double d)
	{
		return d * Math.PI / 180.0;
	}
	/**
* 函數(shù)功能：根據(jù)最大距離限制，采用DP方法遞歸的對原始軌跡進(jìn)行采樣，得到壓縮后的軌跡
* @param enpInit：原始經(jīng)緯度坐標(biāo)點數(shù)組
* @param enpArrayFilter：保持過濾后的點坐標(biāo)數(shù)組
* @param start：起始下標(biāo)
* @param end：終點下標(biāo)
* @param DMax：預(yù)先指定好的最大距離誤差
*/
	public static void TrajCompressC(ENPoint[] enpInit,ArrayList<ENPoint> enpArrayFilter,
	int start,int end,double DMax){
		if(start < end){
			//遞歸進(jìn)行的條件
			double maxDist = 0;
			//最大距離
			int cur_pt = 0;
			//當(dāng)前下標(biāo)
			for (int i=start+1;i<end;i++){
				double curDist = distToSegment(enpInit[start],enpInit[end],enpInit[i]);
				//當(dāng)前點到對應(yīng)線段的距離
				if(curDist > maxDist){
					maxDist = curDist;
					cur_pt = i;
				}
				//求出最大距離及最大距離對應(yīng)點的下標(biāo)
			}
			//若當(dāng)前最大距離大于最大距離誤差
			if(maxDist >= DMax){
				enpArrayFilter.add(enpInit[cur_pt]);
				//將當(dāng)前點加入到過濾數(shù)組中
				//將原來的線段以當(dāng)前點為中心拆成兩段，分別進(jìn)行遞歸處理
				TrajCompressC(enpInit,enpArrayFilter,start,cur_pt,DMax);
				TrajCompressC(enpInit,enpArrayFilter,cur_pt,end,DMax);
			}
		}
	}
	/**
* 函數(shù)功能：求平均距離誤差
* @param pGPSArrayInit：原始數(shù)據(jù)點坐標(biāo)
* @param pGPSArrayFilterSort：過濾后的數(shù)據(jù)點坐標(biāo)
* @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;
	}
}