Trajectory compression algorithm
Scene description
Given a GPS data record file, each record contains two coordinate fields, longitude and dimension, and compresses the records according to the distance threshold, and forms a track with the latitude and longitude coordinates of all filtered records.
Algorithm description
This algorithm has a wide range of uses.
Trajectory compression algorithms are divided into two categories, namely lossless compression and lossy compression. Lossless compression algorithms mainly include Huffman coding, and lossy compression algorithms are divided into batch processing method and online data compression method. The batch processing method includes DP (Douglas-Peucker) algorithm, TD-TR (Top-Down Time-Ratio) algorithm and Bellman algorithm. Online data compression methods include sliding windows, open windows, safe area-based methods, etc.
You can also refer to this article: " Detailed Code of Douglas-Peucker Algorithm for Java Programming Implementing Trajectory Compression "
Code implementation
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{//Threshold definition double maxDistanceError = 30;/* * File reading* *///Storage information list of position points read from the file ArrayList<enpoint> ENPList = new ArrayList<enpoint>();//Create the file object of the address of the source data file//This is where you need to change the storage address of your source file. Remember if the address contains "/", remember to add another "/", the reason "/" is an escape symbol//This can be written as C:/Users/Administrator/Desktop/11.6/2007-10-14-GPS.logFile sourceFile = new File("./2007-10-14-GPS.log");//Calculating the file reading function to read file data ENPList = getENPointFromFile(sourceFile);//This is to test whether you have read the data in the list and check the number of data in the list. Remember to comment out System.out.println(ENPList.size());/* * Data processing* Method: Open window track compression method* *////Set of storing target points ArrayList<enpoint> rePointList = new ArrayList<enpoint>();rePointList = openWindowTra(ENPList,maxDistanceError);System.out.println(rePointList.size());/* * Write to the target file* */File targetFile = new File("./2007-10-14-GPSResult.log"); writeTestPointToFile(targetFile,rePointList);/* * Compact rate calculation*/double cpL = (double)rePointList.size() / (double)ENPList.size() * 100;DecimalFormat df = new DecimalFormat("0.000000");System.out.println("Compression rate: "+ df.format(cpL) + "%");/* * Calculate the average distance error* */double aveDisErr = getMeanDistError(ENPList,rePointList);System.out.println(aveDisErr);/* * Draw lines to form a comparison chart* *///generateImage(ENPList,rePointList);}/* * Extract position points from the provided file information* and call the conversion function to store the coordinate value of each point in the list* The function returns a collection of all position points*/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));//Input stream initialization BufferedReader bReader = new BufferedReader(read);//Cached read initialization String str;String[] strGPS;int i = 0;while((str = bReader.readLine())!=null){//A line is read per line 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;}/** * Function function: convert the original latitude and longitude coordinate data into degrees* The obtained latitude and longitude data is a string*/public static double dfTodu(String str){int indexD = str.indexOf('.');//get. The position of the character String strM = str.substring(0,indexD-2);//Integer part String strN = str.substring(indexD-2);//Decimal part double d = double.parsedouble(strM)+double.parsedouble(strN)/60;return d;}/* * Open window method implementation* Return a compressed position list* List of data stored ID and point coordinates* * Algorithm description: * Initial point and floating point calculate the projection point, judge the distance between the projection point and the trajectory point and the threshold value. If the distance is greater than the threshold value*, the initial point is placed in the targetList, the floating point searches forward as the new initial point, and the new initial point searches backward as the second as the new floating point. Here there is a judgment that is whether the new initial point position +1 is equal to the list length. This determines the selection of the floating point* This is handled to the end point* */public static ArrayList<enpoint> openWindowTra(ArrayList<enpoint> sourceList,double maxDis){ArrayList<enpoint> targetList = new ArrayList<enpoint>();//Define the initial point position of the initial point as 0 int startPoint = 0;//Define the initial point position of the floating point position 2int floatPoint = 2;//Define the initial point position of the current track point position as 1int nowPoint = 1;int len = sourceList.size();//Storage the information set of points in all windows ArrayList<enpoint> listPoint = new ArrayList<enpoint>();listPoint.add(sourceList.get(nowPoint));//Floating point position determines the loop while(true){//Flag is used to control whether to update the track point in the window Boolean flag = false;//Calculate and judge whether the distance between all points in the window and the projection point is greater than the threshold for (ENPoint point:listPoint){double disOfTwo = getDistance(sourceList.get(startPoint),sourceList.get(floatPoint),point); if(disOfTwo >= 30){flag = true;break;}}if(flag){//The distances of points in the window are greater than the threshold//The initial point is added to the target list targetList.add(sourceList.get(startPoint));//The initial point change startPoint = floatPoint - 1;//The floating point change floatPoint += 1; if(floatPoint >= len){targetList.add(sourceList.get(floatPoint-1));break;}//The point in the window changes listPoint.clear();//System.out.println(listPoint.size()); listPoint.add(sourceList.get(startPoint+1));} else{//The distance is less than the threshold//The initial point remains unchanged//The current window collection adds the current floating point listPoint.add(sourceList.get(floatPoint));//The floating point moves one by one floatPoint += 1;//If the floating point is the end point and the distance of the current window point is less than the threshold, ignore the window point and directly add the end point to the target point set if(floatPoint >= len){targetList.add(sourceList.get(startPoint));targetList.add(sourceList.get(floatPoint-1));break;}}flag = false;}return targetList;}/*calculate the distance between the projection point and the track point* The entrance is the initial point A, floating point B, and the current track point C * Triangular area formula*/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 Copy function* *//* Functions provided* The function that calculates the distance has been modified to obtain the following distance calculation method* I have not studied how to calculate the 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;}public static double Rad(double d){return d * Math.PI / 180.0;}/* * Write compressed position point information to the file* */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();}/** * Function function: Find the average distance error* Return the average distance*/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++){" means="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;//Point IDpublic double pe;//Longitude public double pn;//Dimension public ENPoint(){}//Empty constructor 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;}}Summarize
The above is the entire content of this article about the open window instance code of Java programming implementation trajectory compression algorithm. I hope it will be helpful to everyone. If there are any shortcomings, please leave a message to point it out.