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

更新時(shí)間：2017年11月28日 10:05:28 投稿：mengwei

這篇文章主要介紹了Java編程實(shí)現(xiàn)軌跡壓縮之Douglas-Peucker算法詳細(xì)代碼，具有一定借鑒價(jià)值，需要的朋友可以參考。

第一部分問(wèn)題描述

1.1 具體任務(wù)

　　本次作業(yè)任務(wù)是軌跡壓縮，給定一個(gè)GPS數(shù)據(jù)記錄文件，每條記錄包含經(jīng)度和維度兩個(gè)坐標(biāo)字段，所有記錄的經(jīng)緯度坐標(biāo)構(gòu)成一條軌跡，要求采用合適的壓縮算法，使得壓縮后軌跡的距離誤差小于30m。

1.2 程序輸入

　　本程序輸入是一個(gè)GPS數(shù)據(jù)記錄文件。

1.3 數(shù)據(jù)輸出

　　輸出形式是文件，包括三部分，壓縮后點(diǎn)的ID序列及坐標(biāo)、點(diǎn)的個(gè)數(shù)、平均距離誤差、壓縮率

第二部分問(wèn)題解答

　　根據(jù)問(wèn)題描述，我們對(duì)問(wèn)題進(jìn)行求解，問(wèn)題求解分為以下幾步：

2.1 數(shù)據(jù)預(yù)處理

　　本次程序輸入為GPS數(shù)據(jù)記錄文件，共有3150行記錄，每行記錄又分為若干個(gè)字段，根據(jù)題意，我們只需關(guān)注經(jīng)度和緯度坐標(biāo)字段即可，原始數(shù)據(jù)文件部分記錄如圖2.1所示：

圖2.1 原始數(shù)據(jù)文件部分記錄示意圖

　如圖2.1所示，原始數(shù)據(jù)文件每條記錄中經(jīng)緯度坐標(biāo)字段數(shù)據(jù)的保存格式是典型的GPS坐標(biāo)表達(dá)方式，即度分格式，形式為dddmm.mmmm，其中ddd表示度，mm.mmmm表示分，小數(shù)點(diǎn)前面表示分的整數(shù)部分，小數(shù)點(diǎn)后表示分的小數(shù)部分；本次數(shù)據(jù)預(yù)處理，為方便后面兩個(gè)坐標(biāo)點(diǎn)之間距離的計(jì)算，我們需要將度分格式的經(jīng)緯度坐標(biāo)數(shù)據(jù)換算成度的形式，換算方法是ddd+mm.mmmm/60，此處我們保留小數(shù)點(diǎn)后6位數(shù)字，換算后的形式為ddd.xxxxxx。

　　我們以第一條記錄中經(jīng)緯度坐標(biāo)（11628.2491，3955.6535）為例，換算后的結(jié)果為（116.470818，39.927558），所有記錄中經(jīng)緯度坐標(biāo)都使用方法進(jìn)行，并且可以為每一個(gè)轉(zhuǎn)換后的坐標(biāo)點(diǎn)生成一個(gè)ID，進(jìn)行唯一標(biāo)識(shí)，壓縮后，我們只需輸出所有被保留點(diǎn)的ID即可。

2.2 Douglas-Peucker軌跡壓縮算法

　　軌跡壓縮算法分為兩大類，分別是無(wú)損壓縮和有損壓縮，無(wú)損壓縮算法主要包括哈夫曼編碼，有損壓縮算法又分為批處理方式和在線數(shù)據(jù)壓縮方式，其中批處理方式又包括DP（Douglas-Peucker）算法、TD-TR（Top-Down Time-Ratio）算法和Bellman算法，在線數(shù)據(jù)壓縮方式又包括滑動(dòng)窗口、開(kāi)放窗口、基于安全區(qū)域的方法等。

　　由于時(shí)間有限，本次軌跡壓縮，我們決定采用相對(duì)簡(jiǎn)單的DP算法。

　　DP算法步驟如下：

　　（1）在軌跡曲線在曲線首尾兩點(diǎn)A，B之間連接一條直線AB，該直線為曲線的弦；

　　（2）遍歷曲線上其他所有點(diǎn)，求每個(gè)點(diǎn)到直線AB的距離，找到最大距離的點(diǎn)C，最大距離記為dmax；

　　（3）比較該距離dmax與預(yù)先定義的閾值Dmax大小，如果dmax<Dmax，則將該直線AB作為曲線段的近似，曲線段處理完畢；

　　（4）若dmax>=Dmax，則使C點(diǎn)將曲線AB分為AC和CB兩段，并分別對(duì)這兩段進(jìn)行（1）~（3）步處理；

　　（5）當(dāng)所有曲線都處理完畢時(shí)，依次連接各個(gè)分割點(diǎn)形成的折線，即為原始曲線的路徑。

2.3 點(diǎn)到直線的距離

　　DP算法中需要求點(diǎn)到直線的距離，該距離指的是垂直歐式距離，即直線AB外的點(diǎn)C到直線AB的距離d，此處A、B、C三點(diǎn)均為經(jīng)緯度坐標(biāo)；我們采用三角形面積相等法求距離d，具體方法是：A、B、C三點(diǎn)構(gòu)成三角形，該三角形的面積有兩種求法，分別是普通方法（底x高/2）和海倫公式，海倫公式如下：

　　假設(shè)有一個(gè)三角形，邊長(zhǎng)分別為a、b、c，三角形的面積S可由以下公式求得：

其中p為半周長(zhǎng)：

我們通過(guò)海倫公式求得三角形面積，然后就可以求得高的大小，此處高即為距離d。要想用海倫公式，必須求出A、B、C三點(diǎn)兩兩之間的距離，該距離公式是由老師給出的，直接調(diào)用距離函數(shù)即可。

注意：求出距離后，要加上絕對(duì)值，以防止距離為負(fù)數(shù)。

2.4 平均誤差求解

　　平均誤差指的是壓縮時(shí)忽略的那些點(diǎn)到對(duì)應(yīng)線段的距離之和除以總點(diǎn)數(shù)得到的數(shù)值。

2.5 壓縮率求解

　　壓縮率的計(jì)算公式如下：

2.6 數(shù)據(jù)結(jié)果文件的生成

　　經(jīng)過(guò)上面的處理和計(jì)算，我們將壓縮后剩余點(diǎn)的ID和點(diǎn)的個(gè)數(shù)、平均距離誤差、壓縮率等參數(shù)都寫(xiě)入最終的結(jié)果文件中，問(wèn)題解答完成。

第三部分代碼實(shí)現(xiàn)

　　本程序采用Java語(yǔ)言編寫(xiě)，開(kāi)發(fā)環(huán)境為IntelliJ IDEA 14.0.2，代碼共分為兩個(gè)類，一個(gè)是ENPoint類，用于保存經(jīng)緯度點(diǎn)信息，一個(gè)是TrajectoryCompressionMain類，用于編寫(xiě)數(shù)據(jù)處理、DP算法、點(diǎn)到直線距離、求平均誤差等函數(shù)。

3.1 程序總流程

　　整個(gè)程序流程主要包括以下幾個(gè)步驟：

　?。?）定義相關(guān)ArrayList數(shù)組和File對(duì)象，其中ArrayList數(shù)組對(duì)象有三個(gè)，分別是原始經(jīng)緯度坐標(biāo)數(shù)組pGPSArryInit、過(guò)濾后的點(diǎn)坐標(biāo)數(shù)組pGPSArrayFilter、過(guò)濾并排序后的點(diǎn)坐標(biāo)數(shù)組pGPSArrayFilterSort；File文件對(duì)象共有五個(gè)，分別是原始數(shù)據(jù)文件對(duì)象fGPS、壓縮后的結(jié)果數(shù)據(jù)文件對(duì)象oGPS、保持轉(zhuǎn)換后的原始經(jīng)緯度坐標(biāo)點(diǎn)的數(shù)據(jù)文件fInitGPSPoint、仿真測(cè)試文件fTestInitPoint和fTestFilterPoint。

　　（2）獲取原始點(diǎn)坐標(biāo)并將其寫(xiě)入到文件中，主要包括讀文件和寫(xiě)文件兩種操作；

　　（3）進(jìn)行軌跡壓縮；

　?。?）對(duì)壓縮后的經(jīng)緯度點(diǎn)坐標(biāo)進(jìn)行排序；

　?。?）生成仿真測(cè)試文件，并用R語(yǔ)言工具進(jìn)行圖形繪制，得到最終的結(jié)果；

　?。?）求平均誤差和壓縮率，平均誤差通過(guò)函數(shù)求得，壓縮率直接計(jì)算獲得；

　?。?）將最終結(jié)果寫(xiě)入結(jié)果文件中，包括過(guò)濾后的點(diǎn)的ID，點(diǎn)的個(gè)數(shù)、平均誤差和壓縮率；

3.2 具體實(shí)現(xiàn)代碼

　　（1）ENPoint.java

package cc.xidian.main;
import java.text.DecimalFormat;
/**
* Created by hadoop on 2015/12/20.
*/
public class ENPoint implements Comparable<ENPoint>{
public int id;
//點(diǎn)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;
}
}

（2）TrajectoryCompressionMain.java

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

第四部分程序結(jié)果

4.1 程序輸出結(jié)果

　　壓縮后的結(jié)果：

　　（1）總點(diǎn)數(shù)：140個(gè)點(diǎn)；（2）平均距離誤差：7.943786；（3）壓縮率：4.4444%

4.2 仿真結(jié)果

　　經(jīng)過(guò)軌跡壓縮，我們將原始經(jīng)緯度坐標(biāo)點(diǎn)轉(zhuǎn)換為壓縮過(guò)濾后的經(jīng)緯度坐標(biāo)點(diǎn)，我們將這兩種點(diǎn)坐標(biāo)數(shù)據(jù)分別寫(xiě)入兩個(gè)文件中，然后根據(jù)這兩個(gè)文件使用R語(yǔ)言進(jìn)行圖形繪制，分別畫(huà)出壓縮前和壓縮后的軌跡，進(jìn)行對(duì)比，根據(jù)對(duì)比結(jié)果就可以看出我們軌跡壓縮算法是否有效，最終對(duì)比結(jié)果如圖4.1所示：

第五部分總結(jié)

　　本程序編寫(xiě)過(guò)程中，遇到了各種各樣的問(wèn)題，也學(xué)到了很多編程經(jīng)驗(yàn)，下面就遇到的問(wèn)題及解決方案做一個(gè)總結(jié)，最后對(duì)程序存在的不足提出改進(jìn)建議。

5.1 遇到的問(wèn)題及解決方案

　　問(wèn)題1：經(jīng)緯度坐標(biāo)順序問(wèn)題

　　解決：距離公式中的參數(shù)是緯度在前經(jīng)度在后，需要調(diào)整下經(jīng)緯度坐標(biāo)點(diǎn)的順序。

　　問(wèn)題2：距離不能為負(fù)值

　　解決：保證求出的距離不能為負(fù)值，加絕對(duì)值函數(shù)即可。

　　問(wèn)題3：DP算法實(shí)現(xiàn)細(xì)節(jié)

　　解決：開(kāi)始使用ArrayList數(shù)組解決下標(biāo)問(wèn)題，遞歸求解時(shí)出現(xiàn)巨大誤差，后來(lái)改用普通數(shù)組下標(biāo)進(jìn)行遞歸，結(jié)果好多了。

5.2 存在的不足與展望

　　（1）進(jìn)行軌跡壓縮時(shí)，DP算法是最簡(jiǎn)單的一種算法，并不是最優(yōu)的，可選用一些效果好的算法再次進(jìn)行軌跡壓縮；

　?。?）本次實(shí)驗(yàn)數(shù)據(jù)的記錄為3150條，數(shù)據(jù)量不算大，如果有10億條數(shù)據(jù)，該怎么辦呢？我們可以從硬件、分布式、數(shù)據(jù)預(yù)處理、數(shù)據(jù)切分、性能好的數(shù)據(jù)倉(cāng)庫(kù)等方面考慮。

以上就是本文關(guān)于Java編程實(shí)現(xiàn)軌跡壓縮之Douglas-Peucker算法詳細(xì)代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: