关于GPS轨迹压缩的Douglas-Peucker算法简介

前言

最近在做的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)和海伦公式,海伦公式如下:

假设有一个三角形,边长分别为a、b、c,三角形的面积S可由以下公式求得:GPS轨迹压缩之Douglas-Peucker算法,其中p为半周长:GPS轨迹压缩之Douglas-Peucker算法 。

我们通过海伦公式求得三角形面积,然后就可以求得高的大小,此处高即为距离d。要想用海伦公式,必须求出A、B、C三点两两之间的距离,该距离公式也是一个数学公式。

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

平均误差

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

压缩率

压缩率的计算公式如下: GPS轨迹压缩之Douglas-Peucker算法

具体代码实现

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

2.DP算法实现类

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

0

发表评论

您的电子邮箱地址不会被公开。