軌跡壓縮算法
場景描述
給定一個GPS數據記錄文件，每條記錄包含經度和維度兩個坐標字段，根據距離閾值壓縮記錄，將過濾後的所有記錄的經緯度坐標構成一條軌跡
算法描述
這種算法的用處還是相當廣泛的。
軌跡壓縮算法分為兩大類，分別是無損壓縮和有損壓縮，無損壓縮算法主要包括哈夫曼編碼，有損壓縮算法又分為批處理方式和在線數據壓縮方式，其中批處理方式又包括DP（Douglas-Peucker）算法、TD-TR（Top-Down Time-Ratio）算法和Bellman算法，在線數據壓縮方式又包括滑動窗口、開放窗口、基於安全區域的方法等。
大家也可參考這篇文章： 《 Java編程實現軌跡壓縮之Douglas-Peucker算法詳細代碼》
代碼實現
import java.awt.Color;import java.awt.Graphics;import java.awt.Point;import java.awt.Toolkit;import java.io.BufferedReader;import java.io.File;import java.io.FileInputStream;import java.io.InputStreamReader;import java.io.RandomAccessFile;import java.text.DecimalFormat;import java.util.ArrayList;import java.util.Iterator;import javax.swing.JFrame;import javax.swing.JPanel;public class TrajectoryCom {public static void main(String[] args) throws Exception{//閾值定義double maxDistanceError = 30;/* * 文件讀取* *///存放從文件讀取的位置點的信息列表ArrayList<enpoint> ENPList = new ArrayList<enpoint>();//源數據文件的地址建立文件對象//這裡是需要更改的地方改你源文件的存放地址記住如果地址中含"/",記得再加一個"/"，原因"/"是轉義符號//這裡可以寫成C:/Users/Administrator/Desktop/11.6/2007-10-14-GPS.logFile sourceFile = new File("./2007-10-14-GPS.log");//調用文件讀取函數讀取文件數據ENPList = getENPointFromFile(sourceFile);//這裡是測試有沒有讀到裡面看看列表裡的數據個數交作業的時候記得註釋掉System.out.println(ENPList.size());/* * 數據處理* 方法：開放窗口軌跡壓縮法* *///存放目標點的集合ArrayList<enpoint> rePointList = new ArrayList<enpoint>();rePointList = openWindowTra(ENPList,maxDistanceError);System.out.println(rePointList.size());/* * 寫入目標文件* */File targetFile = new File("./2007-10-14-GPSResult.log");writeTestPointToFile(targetFile,rePointList);/* * 壓縮率計算*/double cpL = (double)rePointList.size() / (double)ENPList.size() * 100;DecimalFormat df = new DecimalFormat("0.000000");System.out.println("壓縮率："+ df.format(cpL) + "%");/* * 計算平均距離誤差* */double aveDisErr = getMeanDistError(ENPList,rePointList);System.out.println(aveDisErr);/* * 畫線形成對比圖* *///generateImage(ENPList,rePointList);}/* * 從提供的文件信息裡提取位置點* 並將每個點的坐標數值調用轉換函數存到列表裡* 函數返回一個存放所有位置點的集合*/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;}/** * 函數功能：將原始經緯度坐標數據轉換成度* 獲取的經緯度數據為一個字符串*/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;}/* * 開放窗口方法實現* 返回一個壓縮後的位置列表* 列表每條數據存放ID、點的坐標* * 算法描述： * 初始點和浮動點計算出投影點，判斷投影點和軌跡點的距離與閾值若存在距離大於閾值* 則初始點放入targetList，浮動點向前檢索一點作為新的初始點,新的初始點向後檢索第二個作為新的浮動點這裡存在判斷即新的初始點位置+1是不是等於列表長度這裡決定了浮動點的選取* 如此處理至終點* */public static ArrayList<enpoint> openWindowTra(ArrayList<enpoint> sourceList,double maxDis){ArrayList<enpoint> targetList = new ArrayList<enpoint>();//定義初始點位置最開始初始點位置為0 int startPoint = 0;//定義浮動點位置最開始初始點位置2int floatPoint = 2;//定義當前軌跡點位置最開始初始點位置為1int nowPoint = 1;int len = sourceList.size();//存放所有窗口內的點的信息集合ArrayList<enpoint> listPoint = new ArrayList<enpoint>();listPoint.add(sourceList.get(nowPoint));//浮動點位置決定循環while(true){//標誌用來控制判斷是否進行窗口內軌跡點更新Boolean flag = false;//計算並判斷窗口內所有點和投影點的距離是否大於閾值for (ENPoint point:listPoint){double disOfTwo = getDistance(sourceList.get(startPoint),sourceList.get(floatPoint),point);if(disOfTwo >= 30){flag = true;break;}}if(flag){//窗口內點距離都大於閾值//初始點加到目標列表targetList.add(sourceList.get(startPoint));//初始點變化startPoint = floatPoint - 1;//浮動點變化floatPoint += 1;if(floatPoint >= len){targetList.add(sourceList.get(floatPoint-1));break;}//窗口內點變化listPoint.clear();//System.out.println(listPoint.size());listPoint.add(sourceList.get(startPoint+1));} else{//距離小於閾值的情況//初始點不變//當前窗口集合加入當前浮動點listPoint.add(sourceList.get(floatPoint));//浮動點後移一位floatPoint += 1;//如果浮動點是終點且當前窗口點距離都小於閾值就直接忽略窗口點直接將終點加入目標點集合if(floatPoint >= len){targetList.add(sourceList.get(startPoint));targetList.add(sourceList.get(floatPoint-1));break;}}flag = false;}return targetList;}/*計算投影點到軌跡點的距離* 入口是初始點A、浮動點B、當前軌跡點C * 三角形面積公式*/public static double getDistance(ENPoint A,ENPoint B,ENPoint C){double distance = 0;double a = Math.abs(geoDist(A,B));double b = Math.abs(geoDist(B,C));double c = Math.abs(geoDist(A,C));double p = (a + b + c)/2.0;double s = Math.sqrt(p * (pa) * (pb) * (pc));distance = s * 2.0 / a;return distance;}/* * ArrayList 拷貝函數* *//*提供的函數* 其中計算距離的函數經過改造得到下面的距離計算方法* 具體是怎麼計算距離的我也沒研究了* */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;}public static double Rad(double d){return d * Math.PI / 180.0;}/* * 將壓縮後的位置點信息寫入到文件中* */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.getResultString();byte[] bFilter = sFilter.getBytes();rFilter.write(bFilter);}rFilter.close();}/** * 函數功能：求平均距離誤差* 返回平均距離*/public static double getMeanDistError(ArrayList<enpoint> pGPSArray,ArrayList<enpoint> pGPSArrayRe){double sumDist = 0.0;for (int i=1;i<pgpsarrayre.size();i++){double="" end="pGPSArrayRe.get(i).id;" int="" j="start+1;j<end;j++){" meandist="sumDist/(pGPSArray.size());" pre="" return="" start="pGPSArrayRe.get(i-1).id;" sumdist=""><pre>import java.text.DecimalFormat;public class ENPoint implements Comparable<enpoint>{ public int id;//點IDpublic double pe;//經度public double pn;//維度public ENPoint(){}//空構造函數public String toString(){return this.id+"#"+this.pn+","+this.pe;}public String getResultString(){DecimalFormat df = new DecimalFormat("0.000000");return this.id+"#"+df.format(this.pe)+","+df.format(this.pn)+" /n";}@Override public int compareTo(ENPoint other) {if(this.id<other.id) else="" return="" this.id="">other.id) return 1; else return 0;}}總結
以上就是本文關於Java編程實現軌跡壓縮算法開放窗口實例代碼的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。