場景描述
給定一個GPS數據記錄文件，每條記錄包含經度和維度兩個坐標字段，根據距離閾值壓縮記錄，將過濾后的所有記錄的經緯度坐標構成一條軌跡
算法描述
這種算法的用處還是相當廣泛的。
軌跡壓縮算法分為兩大類，分別是無損壓縮和有損壓縮，無損壓縮算法主要包括哈夫曼編碼，有損壓縮算法又分為批處理方式和在線數據壓縮方式，其中批處理方式又包括DP（Douglas-Peucker）算法、TD-TR（Top-Down Time-Ratio）算法和Bellman算法，在線數據壓縮方式又包括滑動窗口、開放窗口、基于安全區域的方法等。
大家也可參考這篇文章：《Java編程實現軌跡壓縮之Douglas-Peucker算法詳細代碼》
代碼實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
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.log File 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; //定義浮動點位置 最開始初始點位置2 int floatPoint = 2; //定義當前軌跡點位置 最開始初始點位置為1 int 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 * (p-a) * (p-b) * (p-c)); 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 class="brush:java;">import java.text.DecimalFormat; public class ENPoint implements Comparable<enpoint>{ public int id; //點ID public 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編程實現軌跡壓縮算法開放窗口實例代碼的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。
原文鏈接：https://www.2cto.com/kf/201711/700920.html
