第一部分問題描述
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和點的個數、平均距離誤差、壓縮率等參數都寫入最終的結果文件中，問題解答完成。
第三部分代碼實現
本程序採用Java語言編寫，開發環境為IntelliJ IDEA 14.0.2，代碼共分為兩個類，一個是ENPoint類，用於保存經緯度點信息，一個是TrajectoryCompressionMain類，用於編寫數據處理、DP算法、點到直線距離、求平均誤差等函數。
3.1 程序總流程
整個程序流程主要包括以下幾個步驟：
（1）定義相關ArrayList數組和File對象，其中ArrayList數組對像有三個，分別是原始經緯度坐標數組pGPSArryInit、過濾後的點坐標數組pGPSArrayFilter、過濾並排序後的點坐標數組pGPSArrayFilterSort；File文件對象共有五個，分別是原始數據文件對象fGPS、壓縮後的結果數據文件對象oGPS、保持轉換後的原始經緯度坐標點的數據文件fInitGPSPoint、仿真測試文件fTestInitPoint和fTestFilterPoint。
（2）獲取原始點坐標並將其寫入到文件中，主要包括讀文件和寫文件兩種操作；
（3）進行軌跡壓縮；
（4）對壓縮後的經緯度點坐標進行排序；
（5）生成仿真測試文件，並用R語言工具進行圖形繪製，得到最終的結果；
（6）求平均誤差和壓縮率，平均誤差通過函數求得，壓縮率直接計算獲得；
（7）將最終結果寫入結果文件中，包括過濾後的點的ID，點的個數、平均誤差和壓縮率；
3.2 具體實現代碼
（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;//點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;}}（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、相關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*(pa)*(pb)*(pc)));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;}}第四部分程序結果
4.1 程序輸出結果
壓縮後的結果：
（1）總點數：140個點；（2）平均距離誤差：7.943786；（3）壓縮率：4.4444%
4.2 仿真結果
經過軌跡壓縮，我們將原始經緯度坐標點轉換為壓縮過濾後的經緯度坐標點，我們將這兩種點坐標數據分別寫入兩個文件中，然後根據這兩個文件使用R語言進行圖形繪製，分別畫出壓縮前和壓縮後的軌跡，進行對比，根據對比結果就可以看出我們軌跡壓縮算法是否有效，最終對比結果如圖4.1所示：
第五部分總結
本程序編寫過程中，遇到了各種各樣的問題，也學到了很多編程經驗，下面就遇到的問題及解決方案做一個總結，最後對程序存在的不足提出改進建議。
5.1 遇到的問題及解決方案
問題1：經緯度坐標順序問題
解決：距離公式中的參數是緯度在前經度在後，需要調整下經緯度坐標點的順序。
問題2：距離不能為負值
解決：保證求出的距離不能為負值，加絕對值函數即可。
問題3：DP算法實現細節
解決：開始使用ArrayList數組解決下標問題，遞歸求解時出現巨大誤差，後來改用普通數組下標進行遞歸，結果好多了。
5.2 存在的不足與展望
（1）進行軌跡壓縮時，DP算法是最簡單的一種算法，並不是最優的，可選用一些效果好的算法再次進行軌跡壓縮；
（2）本次實驗數據的記錄為3150條，數據量不算大，如果有10億條數據，該怎麼辦呢？我們可以從硬件、分佈式、數據預處理、數據切分、性能好的數據倉庫等方面考慮。
以上就是本文關於Java編程實現軌跡壓縮之Douglas-Peucker算法詳細代碼的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！