场景描述
给定一个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
