Java编程实现轨迹压缩之Douglas-Peucker算法详细代码_python编程Douglas–Peucker包资源-CSDN文库

轨迹压缩java实现

101 浏览量 2020-08-28 17:13:41 上传评论 1 收藏 222KB PDF 举报

资源推荐

资源详情

资源评论

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

主要介绍了Java编程实现轨迹压缩之Douglas-Peucker算法详细代码，具有一定借鉴价值，需要的朋友可以参

考。

第一部分问题描述

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三

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

内容反馈

weixin_38547151

粉丝: 2
资源: 899

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip