Java编程实现轨迹压缩算法开放窗口实例代码

轨迹压缩算法

场景描述

给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,根据距离阈值压缩记录,将过滤后的所有记录的经纬度坐标构成一条轨迹

算法描述

这种算法的用处还是相当广泛的。

轨迹压缩算法分为两大类,分别是无损压缩和有损压缩,无损压缩算法主要包括哈夫曼编码,有损压缩算法又分为批处理方式和在线数据压缩方式,其中批处理方式又包括DP(Douglas-Peucker)算法、TD-TR(Top-Down Time-Ratio)算法和Bellman算法,在线数据压缩方式又包括滑动窗口、开放窗口、基于安全区域的方法等。

大家也可参考这篇文章:Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

代码实现

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编程实现轨迹压缩算法开放窗口实例代码的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出。

您可能感兴趣的文章:

  • Java编程实现基于用户的协同过滤推荐算法代码示例
  • 70行Java代码实现深度神经网络算法分享
  • 多模字符串匹配算法原理及Java实现代码
  • java算法实现红黑树完整代码示例
  • Java实现与JS相同的Des加解密算法完整实例
  • Java实现分解任意输入数的质因数算法示例
  • Java实现的猴子吃桃问题算法示例
  • Java实现的求逆矩阵算法示例
(0)

相关推荐

  • Java编程实现基于用户的协同过滤推荐算法代码示例

    协同过滤简单来说是利用某兴趣相投.拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要. 协同过滤又可分为评比(rating)或者群体过滤(social filtering)协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热 UserCF的核心思想即为根据用户数据模拟向量相似度,我们根据这个相似度,来找出指定用户的相似用户,然后将相似用

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • java算法实现红黑树完整代码示例

    红黑树 定义 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组. 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接:没有任何一个结点同时和两条红链接相连:该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同. 满足这样定义的红黑树和相应的2-3树是一一对应的. 旋转 旋转又分为左旋和右旋.通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接.对比操作前后,可以看出,该操作

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

  • Java实现的求逆矩阵算法示例

    本文实例讲述了Java实现的求逆矩阵算法.分享给大家供大家参考,具体如下: package demo; public class MatrixInverse { public static double Det(double [][]Matrix,int N)//计算n阶行列式(N=n-1) { int T0; int T1; int T2; double Num; int Cha; double [][] B; if(N>0) { Cha=0; B=new double[N][N]; Num=

  • Java实现与JS相同的Des加解密算法完整实例

    本文实例讲述了Java实现与JS相同的Des加解密算法.分享给大家供大家参考,具体如下: 这里演示java与js实现相同的des加解密算法,不多说,不废话,直接上代码 一.java实现 package com.lyz.base.des; import java.util.ArrayList; import java.util.List; /** * DES加密/解密 * * @Copyright Copyright (c) 2015 * @author liuyazhuang * @see DE

  • Java实现分解任意输入数的质因数算法示例

    本文实例讲述了Java实现分解任意输入数的质因数算法.分享给大家供大家参考,具体如下: 分解任意输入数的质因数: 质因数概念:任何一个合数都可以写成几个质数相乘的形式.其中每个质数都是这个合数的因数,叫做这个合数的分解质因数.分解质因数只针对合数. 例如:12 = 2x2x3  18 = 2 x 3 x 3等等 下面来讲解一下这个算法的思路:第一:我们首先写一个求素数的函数:第二;我们做一个分解质因数的函数,然后在其中引入素数函数来判断是否为素数: 下面给出代码(仅供参考): package j

  • 70行Java代码实现深度神经网络算法分享

    对于现在流行的深度学习,保持学习精神是必要的--程序员尤其是架构师永远都要对核心技术和关键算法保持关注和敏感,必要时要动手写一写掌握下来,先不用关心什么时候用到--用不用是政治问题,会不会写是技术问题,就像军人不关心打不打的问题,而要关心如何打赢的问题. 程序员如何学习机器学习 对程序员来说,机器学习是有一定门槛的(这个门槛也是其核心竞争力),相信很多人在学习机器学习时都会为满是数学公式的英文论文而头疼,甚至可能知难而退.但实际上机器学习算法落地程序并不难写,下面是70行代码实现的反向多层(BP

  • Java编程实现轨迹压缩算法开放窗口实例代码

    轨迹压缩算法 场景描述 给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,根据距离阈值压缩记录,将过滤后的所有记录的经纬度坐标构成一条轨迹 算法描述 这种算法的用处还是相当广泛的. 轨迹压缩算法分为两大类,分别是无损压缩和有损压缩,无损压缩算法主要包括哈夫曼编码,有损压缩算法又分为批处理方式和在线数据压缩方式,其中批处理方式又包括DP(Douglas-Peucker)算法.TD-TR(Top-Down Time-Ratio)算法和Bellman算法,在线数据压缩方式又包括滑动窗口.

  • Java编程实现NBA赛事接口调用实例代码

    第一步:找别人提供的接口,比如在这里我选择的是聚合数据提供的接口 第二步:要申请相应的AppKey方可使用,此参数会作为接口的参数调用. 第三步:调用别人提供的接口方法 代码如下: package juheapi.nba; /** * Created by Administrator on 2017/11/19/019. */ import net.sf.json.JSONObject; import java.io.*; import java.net.HttpURLConnection; i

  • Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

    第一部分 问题描述 1.1 具体任务 本次作业任务是轨迹压缩,给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,所有记录的经纬度坐标构成一条轨迹,要求采用合适的压缩算法,使得压缩后轨迹的距离误差小于30m. 1.2 程序输入 本程序输入是一个GPS数据记录文件. 1.3 数据输出 输出形式是文件,包括三部分,压缩后点的ID序列及坐标.点的个数.平均距离误差.压缩率 第二部分 问题解答 根据问题描述,我们对问题进行求解,问题求解分为以下几步: 2.1 数据预处理 本次程序输入为GPS

  • Java编程实现多线程TCP服务器完整实例

    相关Java类 Socket public class Socket extends Object ·功能:TCP客户端套接字 ·构造方法: Socket(InetAddress address, int port) 创建一个流套接字并将其连接到指定 IP 地址的指定端口号 ·常用方法: 1.getInetAddress 获得InetAddress的相关信息 2.getInputStream 获得此TCP连接的输入流 3.getOutPutStream 获得此TCP连接的输出流 ServerSo

  • Java编程实现从尾到头打印链表代码实例

    问题描述:输入一个链表的头结点,从尾巴到头反过来打印出每个结点的值. 首先定义链表结点 public class ListNode { int val; ListNode next = null; ListNode(int val){ this.val = val; } } 思路1:此题明显想到是利用栈的思想,后进先出,先遍历链表,依次将结点值进栈.最后在遍历栈出栈. public static Stack<Integer> printListReverse_Stack(ListNode li

  • Java并发编程Callable与Future的应用实例代码

    本文主要探究的是java并发编程callable与future的使用,分享了相关实例代码,具体介绍如下. 我们都知道实现多线程有2种方式,一种是继承Thread,一种是实现Runnable,但这2种方式都有一个缺陷,在任务完成后无法获取返回结果.要想获得返回结果,就得使用Callable,Callable任务可以有返回值,但是没法直接从Callable任务里获取返回值:想要获取Callabel任务的返回值,需要用到Future.所以Callable任务和Future模式,通常结合起来使用. 试想

  • Java编程使用UDP建立群聊系统代码实例

    相关java类介绍 DatagramSocket public class DatagramSocket extends Object 此类表示用来发送和接收数据报包的套接字. 数据报套接字是包投递服务的发送或接收点.每个在数据报套接字上发送或接收的包都是单独编址和路由的.从一台机器发送到另一台机器的多个包可能选择不同的路由,也可能按不同的顺序到达. 在DatagramSocket上总是启用UDP广播发送.为了接收广播包,应该将DatagramSocket绑定到通配符地址,在某些实现中,将Dat

  • 使用Java和WebSocket实现网页聊天室实例代码

    在没介绍正文之前,先给大家介绍下websocket的背景和原理: 背景 在浏览器中通过http仅能实现单向的通信,comet可以一定程度上模拟双向通信,但效率较低,并需要服务器有较好的支持; flash中的socket和xmlsocket可以实现真正的双向通信,通过 flex ajax bridge,可以在javascript中使用这两项功能. 可以预见,如果websocket一旦在浏览器中得到实现,将会替代上面两项技术,得到广泛的使用.面对这种状况,HTML5定义了WebSocket协议,能更

  • java Swing基础教程之图形化实例代码

    java  Swing基础教程之图形化实例代码 与多线程.泛型等不同,Swing主要在于使用. 下面主要放代码和注释,少说话. (一)基本框架 package Swing; import java.awt.*; import javax.swing.*; /** * * @author QuinnNorris * 基本框架 */ public class FrameTest { /** * @param args */ public static void main(String[] args)

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

随机推荐