Java programming implementation of trajectory compression algorithm open window instance code
- 2020-11-30 08:21:47
- OfStack
Trajectory compression algorithm
Scene description
Given an GPS data record file, each record contains two coordinate fields of longitude and dimension. According to the distance threshold, the records are compressed to form a track of the latitude and longitude coordinates of all the filtered records
Algorithm description
The utility of this algorithm is quite extensive.
Trajectory of compression algorithm is divided into two categories, namely, lossless and lossy compression, lossless compression algorithm including Huffman encoding, lossy compression algorithm is divided into batch mode and online data compression method, batch mode and including DP (Douglas - Peucker) algorithm, the TD - TR (Top - Down Time - Ratio) algorithm and Bellman algorithm, online data compression methods including sliding window, open the window again, the method based on the safety area, etc.
You can also refer to this article: Es25EN-ES26en Algorithm Code for Trajectory Compression by Java Programming
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 defined
double maxDistanceError = 30;
/*
* File to read
* */
// Holds a list of location points read from a file
ArrayList<enpoint> ENPList = new ArrayList<enpoint>();
// The address of the source data file Create file objects
// Here's what needs to change Change the address of your source file Remember if the address contains "\", Remember to add 1 a "\" , the reason "\" It's an escape symbol
// So we can rewrite this as C:/Users/Administrator/Desktop/11.6/2007-10-14-GPS.log
File sourceFile = new File("./2007-10-14-GPS.log");
// Call the file read function Read file data
ENPList = getENPointFromFile(sourceFile);
// Here's the test Did you read it Look at the number of Numbers in the list When you hand in your homework, make sure you comment it out
System.out.println(ENPList.size());
/*
* The data processing
* Methods: Open window trajectory compression method
* */
// Store a collection of target points
ArrayList<enpoint> rePointList = new ArrayList<enpoint>();
rePointList = openWindowTra(ENPList,maxDistanceError);
System.out.println(rePointList.size());
/*
* Write to target file
* */
File targetFile = new File("./2007-10-14-GPSResult.log");
writeTestPointToFile(targetFile,rePointList);
/*
* Compression ratio calculation
*/
double cpL = (double)rePointList.size() / (double)ENPList.size() * 100;
DecimalFormat df = new DecimalFormat("0.000000");
System.out.println(" The compression rate: "+ df.format(cpL) + "%");
/*
* Calculate the mean distance error
* */
double aveDisErr = getMeanDistError(ENPList,rePointList);
System.out.println(aveDisErr);
/*
* Draw a line to form a contrast
* */
//generateImage(ENPList,rePointList);
}
/*
* Extract the location point from the provided file information
* And saves the coordinate value of each point to the conversion function in the list
* The function returns 1 a Store all location points A collection of
*/
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);
// Cache read initialization
String str;
String[] strGPS;
int i = 0;
while((str = bReader.readLine())!=null){
// Every time reading 1 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: convert the original latitude and longitude coordinate data into degrees
* The obtained latitude and longitude data is 1 A string
*/
public static double dfTodu(String str){
int indexD = str.indexOf('.');
// To obtain . The position of the character
String strM = str.substring(0,indexD-2);
// The integer part
String strN = str.substring(indexD-2);
// The decimal part
double d = double.parsedouble(strM)+double.parsedouble(strN)/60;
return d;
}
/*
* Open window method implementation
* return 1 A compressed list of locations
* List each data store ID , coordinates of points
*
* Algorithm description:
* The initial point and the floating point calculate the projection point and judge the distance and threshold between the projection point and the trajectory point If the distance is greater than the threshold
* The initial point is put in targetList , the floating point is retrieved forward 1 Point as the new starting point , The new initial point retrieves the control backwards 2 Two as the new floating point There is a judgment here That's the new starting point position +1 Is it equal to the length of the list This is what determines the float point
* This is done 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 The initial position is zero 0
int startPoint = 0;
// Define the float point position The initial position 2
int floatPoint = 2;
// Defines the current locus point position The initial position is zero 1
int nowPoint = 1;
int len = sourceList.size();
// A collection of information that holds points in all Windows
ArrayList<enpoint> listPoint = new ArrayList<enpoint>();
listPoint.add(sourceList.get(nowPoint));
// The floating point position determines the loop
while(true){
// mark It is used to control whether to update the track point in the window
Boolean flag = false;
// Calculate and determine whether the distance between all points in the window and the projected 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 distance between the points in the window is greater than the threshold
// The initial point is added to the target list
targetList.add(sourceList.get(startPoint));
// Initial point change
startPoint = floatPoint - 1;
// Floating point variation
floatPoint += 1;
if(floatPoint >= len){
targetList.add(sourceList.get(floatPoint-1));
break;
}
// Point change in window
listPoint.clear();
//System.out.println(listPoint.size());
listPoint.add(sourceList.get(startPoint+1));
} else{
// Where the distance is less than the threshold
// Initial point unchanged
// The current window collection joins the current float point
listPoint.add(sourceList.get(floatPoint));
// The floating point moves back 1 position
floatPoint += 1;
// If the floating point is the end point And the current window point distance is less than the threshold value Just ignore window points Add the endpoint directly to the target set
if(floatPoint >= len){
targetList.add(sourceList.get(startPoint));
targetList.add(sourceList.get(floatPoint-1));
break;
}
}
flag = false;
}
return targetList;
}
/* Calculate the distance from the projected point to the locus point
* The entrance is the starting point A And floating point B , the current trajectory point C
* 3 Angular 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 * (p-a) * (p-b) * (p-c));
distance = s * 2.0 / a;
return distance;
}
/*
* ArrayList Copy function
* */
/* Provided functions
* Where you compute the function of distance After modification, the following distance calculation method is obtained
* How do you calculate the distance I didn't study it either
* */
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;
}
/*
* Writes the compressed location point information to a 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: Find the average distance error
* Return 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++){" meandist="sumDist/(pGPSArray.size());" pre="" return="" start="pGPSArrayRe.get(i-1).id;" sumdist=""><pre class="brush:java;">import java.text.DecimalFormat;
public class ENPoint implements Comparable<enpoint>{
public int id;
// point ID
public double pe;
// longitude
public double pn;
// The dimension
public ENPoint(){
}
// Null 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;
}
}conclusion
The above is the Java programming implementation of trajectory compression algorithm open window example code all content, hope to be helpful to you. If there is any deficiency, please let me know.