首页 > 编程语言 >GPS轨迹压缩之Douglas-Peucker算法

GPS轨迹压缩之Douglas-Peucker算法

时间:2024-04-11 10:47:05浏览次数:19  
标签:轨迹 Peucker double 距离 Douglas dMax param Math GPS

前言

最近在做的IOT平台涉及到画轨迹线的业务。谈到轨迹线,设备上报上来的数据量巨大,甚至活跃的设备一天上报来的数据都甚至几十万。前端没法对这个数据去处理进行画线取轨迹图像。所以就有了轨迹压缩。

轨迹压缩算法

轨迹压缩算法分为两大类,分别是无损压缩和有损压缩,无损压缩算法主要包括哈夫曼编码,有损压缩算法又分为批处理方式和在线数据压缩方式,其中批处理方式又包括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)当所有曲线都处理完毕时,依次连接各个分割点形成的折线,即为原始曲线的路径。

海伦公式

DP算法中需要求点到直线的距离,该距离指的是垂直欧式距离,即直线AB外的点C到直线AB的距离d,此处A、B、C三点均为经纬度坐标;我们采用三角形面积相等法求距离d,具体方法是:A、B、C三点构成三角形,该三角形的面积有两种求法,分别是普通方法(底x高/2)和海伦公式,海伦公式如下:,其中p为半周长:

 

假设有一个三角形,边长分别为a、b、c,三角形的面积S可由以下公式求得:
我们通过海伦公式求得三角形面积,然后就可以求得高的大小,此处高即为距离d。要想用海伦公式,必须求出A、B、C三点两两之间的距离,该距离公式也是一个数学公式。

​ 注意:求出距离后,要加上绝对值,以防止距离为负数。

平均误差

平均误差指的是压缩时忽略的那些点到对应线段的距离之和除以总点数得到的数值。

压缩率

压缩率的计算公式如下:

具体代码实现

1.为了DP算法压缩之后能匹配到本身数据库查询出的结果记录,(因为结果记录列表的每一条字段是可伸缩的KV对且不固定)准备一个点的实体。

@Data
@NoArgsConstructor
@AllArgsConstructor
@ToString
public class TYPoint {
    public String id;//点ID
    public double lng;//经度
    public double lat;//纬度
}

2.DP算法实现类

public class DPUtil {

    /**
     * 默认的点到轨迹线最大距离误差阈值(单位:米)
     */
    private static double defaultDMax = 30.0;

    /**
     * DP算法入口
     * 传入压缩前的轨迹点集合
     * 输出压缩后的结果轨迹点集合
     * @param originPoints 压缩前的轨迹点集合
     * @param dMax 点到轨迹线最大距离误差阈值
     * @return
     */
    public static List<TYPoint> dpAlgorithm(List<TYPoint> originPoints, Double dMax){
        List<TYPoint> resultPoints = new ArrayList<>();
        resultPoints.add(originPoints.get(0));//获取第一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(originPoints.size()-1));//获取最后一个原始经纬度点坐标并添加到过滤后的数组中
        //最大距离误差阈值
        if(dMax == null){
            dMax = defaultDMax;
        }
        int start = 0;
        int end = originPoints.size()-1;
        compression(originPoints,resultPoints,start,end,dMax);

        return resultPoints;
    }

    /**
     * 函数功能:根据最大距离限制,采用DP方法递归的对原始轨迹进行采样,得到压缩后的轨迹
     * @param originPoints:原始经纬度坐标点数组
     * @param resultPoints:保持过滤后的点坐标数组
     * @param start:起始下标
     * @param end:终点下标
     * @param dMax:预先指定好的最大距离误差 计算
     */
    public static void compression(List<TYPoint> originPoints, List<TYPoint> resultPoints,
                                     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(originPoints.get(start),originPoints.get(end),originPoints.get(i));
                if(curDist > maxDist){
                    maxDist = curDist;
                    cur_pt = i;
                }//求出最大距离及最大距离对应点的下标
            }
            //若当前最大距离大于最大距离误差
            if(maxDist >= dMax){
                resultPoints.add(originPoints.get(cur_pt));//将当前点加入到过滤数组中
                //将原来的线段以当前点为中心拆成两段,分别进行递归处理
                compression(originPoints,resultPoints,start,cur_pt,dMax);
                compression(originPoints,resultPoints,cur_pt,end,dMax);
            }
        }
    }

    /**
     * 函数功能:使用三角形面积(使用海伦公式求得)相等方法计算点pX到点pA和pB所确定的直线的距离
     * @param pA:起始点
     * @param pB:结束点
     * @param pX:第三个点
     * @return distance:点pX到pA和pB所在直线的距离
     */
    public static double distToSegment(TYPoint pA,TYPoint pB,TYPoint 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(TYPoint pA,TYPoint pB){
        double radLat1 = Rad(pA.lat);
        double radLat2 = Rad(pB.lat);
        double delta_lon = Rad(pB.lng - pA.lng);
        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;
    }

}

从入口代码可知dMax是可以传进来的,也就是点到轨迹直线的偏移量阈值是可以设置的。这里我设置默认dMax为30.0测试了一下,4135条数据查询出来有500条,当设置dMax为100时查询出只有289条记录了。具体看业务方需要以多大的压缩限度去压缩。

 

标签:轨迹,Peucker,double,距离,Douglas,dMax,param,Math,GPS
From: https://www.cnblogs.com/fangts/p/18128289

相关文章

  • GPS时钟服务器(北斗对时服务器)在地铁自控系统应用方案
    GPS时钟服务器(北斗对时服务器)在地铁自控系统应用方案GPS时钟服务器(北斗对时服务器)在地铁自控系统应用方案京准电子科技官微——ahjzsz一、时钟系统基本描述1、时钟系统概述时钟系统是轨道交通系统的重要组成部份之一,其主要作用是为控制中心调度员、车站值班员、各部门工作人......
  • 基于STM32单片机汽车防盗GPS定位GSM短信加速度检测设计21-880
    21-880、STM32汽车防盗系统设计-震动-ADXL345-GPS-GSM-RELAY产品功能描述:本设计由STM32F103C8T6单片机核心板电路+震动传感器电路+ADXL345重力加速度传感器电路+GPS模块电路+GSM模块电路+继电器控制电路组成。1、系统将是否有震动以及是否有倾倒以及对应的GPS经纬度信息,每隔......
  • GPS坐标转换为BIM
    将GPS坐标转换为BIM(BuildingInformationModeling)坐标通常涉及几个步骤,因为这两种坐标系统服务于不同的目的并具有不同的参考框架。GPS坐标是基于全球定位系统(WGS84)的地理坐标,而BIM坐标通常是基于项目特定的局部坐标系统。以下是一个基本的转换流程:一、理解坐标系统:GPS坐标:通......
  • 北-东-地坐标系下的低精度的SINS/GPS组合导航系统中初始航向对准技术
     推导了一篇严恭敏老师的论文《低精度的SINS/GPS组合导航系统中初始航向对准技术》主要思想:为了降低航向的非线性,直接估计sin(航向)和cos(航向)文中仿真了两种场景:场景1:初始速度:0m/s,加速度:1m/s^2,GPS水平定位精度:10m;场景2:初始速度:10m/s,拐弯半径为100m,GPS水平定位......
  • 钓鱼_精准定位GPS
    目录一、Seeker(一)简介二、实验环境三、实验操作(一)下载安装(二)运行和使用(三)隧道代理1.登录平台2.下载代理客户端3.使用代理客户端......
  • 从入门到精通:GPS北斗卫星校时服务器 操作指南
    从入门到精通:GPS北斗卫星校时服务器操作指南从入门到精通:GPS北斗卫星校时服务器操作指南京准电子科技官微——ahjzsz一、产品功能卫星时钟服务器是一款采用GPS或北斗卫星提供高精度网络时间服务的产品。卫星天线安装简便(根据天线所放位置提示实时卫星颗数),接口可支持以太网1......
  • NTP网络授时器(GPS北斗对时装置)在分布式网络系统方案
    NTP网络授时器(GPS北斗对时装置)在分布式网络系统方案NTP网络授时器(GPS北斗对时装置)在分布式网络系统方案京准电子科技官微——ahjzsz因为分布式系统使用分布式算法,所以它的同步机制比集中式系统更为复杂。在集中式系统中能够做到的,在某一位置上能集收到系统的所有信息,然后由某些......
  • GPS接收机概况和接收天线
    一、GPS接收机的概况:GPS接收机作为一种传感器,主要任务在于感应、测量GPS卫星相对于接收机本身的距离以及卫星信号的多普勒频移,并从卫星信号中解调出导航电文。GPS接收机的内部结构按其工作流程的先后顺序,通常分为射频(RF)前端处理、基带数字信号处理(DSP)和定位导航运算三大......
  • GPS北斗授时服务器(NTP时间服务器)在5G网络系统的应用
    GPS北斗授时服务器(NTP时间服务器)在5G网络系统的应用GPS北斗授时服务器(NTP时间服务器)在5G网络系统的应用京准电子科技官微——ahjzsz摘要:5G网络部署和垂直行业应用对于时间同步提出了新的需求。为了更满足高精度的同步需求,需要采用高精度同步源技术、高精度同步传送技术、同步监......
  • 车载GPS自建服务-软硬件搭配实践全记录
    全文以汽车GPS定位器为例来探讨:配置GPS系统服务结合配套的硬件实现全流程私有化gps服务朗读全文Yourbrowserdoesnotsupporttheaudioelement.据说,据说2G设备只能用到2027年,运营商(移动)随时可能退网2G网络。具体时间不明确,后期设备和方案可以往4G设备和卡上面升......