第一部分 問題描述
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
|
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
|
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; else return0;}} |
（2）trajectorycompressionmain.java
|
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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
|
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*(p-a)*(p-b)*(p-c))); 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算法詳細代碼的全部內容，希望對大家有所幫助。如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://www.mamicode.com/info-detail-1170156.html
