利用道格拉斯·普客法(DP法)压缩矢量多边形(C++)
发布日期:2022-02-10 11:37:03 浏览次数:27 分类:技术文章

本文共 2128 字,大约阅读时间需要 7 分钟。

1.算法描述

经典的Douglas-Peucker算法(简称DP法)描述如下:

(1)在曲线首尾两点A,B之间连接一条直线AB,该直线为曲线的弦;

(2)得到曲线上离该直线段距离最大的点C,计算其与AB的距离d;

(3)比较该距离与预先给定的阈值threshold的大小,如果小于threshold,则该直线段作为曲线的近似,该段曲线处理完毕。

(4)如果距离大于阈值,则用C将曲线分为两段AC和BC,并分别对两段取信进行1~3的处理。

(5)当所有曲线都处理完毕时,依次连接各个分割点形成的折线,即可以作为曲线的近似

 

2.算法分析

①显然,整个过程是一个迭代过程,第四步时迭代,再次回到第一步。

②由于计算开方耗时,所以直接取d²作为评判值更加方便。

③DP法一般是化简一条曲线,本次化简的是多边形,实质是一条首尾相连的多边形,意味着曲线首尾两点的坐标相等。如果两点坐标相等,则第二步计算距离时会出现分母为0的问题。因此要换一个就近的点。

 

3.算法实现

①计算某点到已知两点的距离。

// 计算一点到一条直线(已知两点)的距离double disP2L(CMyPoint* first, CMyPoint* last, CMyPoint* third) //first和last分别为线的两端,third是第三点																//CMyPoint是点的类型,可以换成CPoint{	double x0 = first->Getx();	double y0 = first->Gety();	double x1 = last->Getx();	double y1 = last->Gety();	double x = third->Getx();	double y = third->Gety();	//diSquare是d²,不开方,耗时更短。	double disSuqare = ((y0 - y1)*x + (x1 - x0)*y + (x0*y1 - x1*y0))*((y0 - y1)*x + (x1 - x0)*y + (x0*y1 - x1*y0)) / ((x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0));	return disSuqare;}

②压缩算法

// Douglas–Peucker法,20190220,压缩,zfvoid DP(vector
inputLine) //输入是包含指针的数组,vector类型{ if (inputLine.size() <= 2) //若少于两点,直接返回 return; int size = inputLine.size(); CMyPoint *first = inputLine[0]; //定义首点 CMyPoint *last = inputLine[size - 1]; //定义尾点 while (last->Getx() == first->Getx() && last->Gety() == first->Gety()) {//若首尾相同,则换点 size = size - 1; last = inputLine[size - 1]; } int flag = 0; //标记距离最大的点的下标 double disSquare = 0; for (int i = 1; i
disSquare) { //记录最大距离及编号 disSquare = temp; flag = i; } } if (disSquare<4) { //判断值与阈值的关系,阈值自己设定 out_DP.push_back(first); //如果小于阈值,则保留首尾点 out_DP.push_back(last); //out_DP是一个全局变量,vector
out_DP //用于存储留下来的点,是最后的成果 } else { //否则分成两段 vector
head, rear; for (int j = 0; j
= flag) rear.push_back(inputLine[j]); } DP(head); //迭代进行 DP(rear); }}

4.实验效果

分别是后、前:

在保持图形和面积基本不变的前提下,多边形的点变少,压缩具有较好效果。

转载地址:https://blog.csdn.net/Fan_z_0802/article/details/87875617 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:shp系列(七)——利用C++进行Shx文件的写(创建)
下一篇:算法学习(2)--数组、链表和跳表的基本实现与特性

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2023年06月02日 12时09分24秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

spssχ2检验_spss交叉表分析方法与步骤 + SPSS卡方检验结果的阅读 2019-12-02 03:25:36
element 搜索匹配_Vue Element 分组+多选+可搜索Select选择器实现示例 2019-12-02 03:25:36
进程线程python_Python 进程 线程总结 2019-12-02 03:25:36
将gridcontrol的值传到textedit中_船舶自动化中的开关量、模拟量、数字量是什么?... 2019-12-02 03:25:33
接口隔离原则_趣谈设计模式之接口隔离原则 2019-12-02 03:25:34
table.reload 只刷新table_EXCEL也能实时刷新股票信息~太神奇了 2019-12-02 03:25:34
判断是否是完全二叉树_二叉树高频面试题和答案 2019-12-02 03:25:34
servlet访问中文文件访问不到_电脑小技巧远程访问共享文件夹 2019-12-02 03:25:34
sql 插入新数据 如何处理>等字符_条码打印软件之如何在条码数据插入字符而不被扫描... 2019-12-02 03:25:35
pythonscrollbar布局_python GUI库图形界面开发之PyQt5滚动条控件QScrollBar详细使用方法与实例... 2019-12-02 03:25:35
电影推荐系统 python简书_推荐系统实战 2019-12-02 03:25:35
phpmyadmin漏洞_CVE201912922 phpMyAdmin 4.9.0.1跨站请求伪造漏洞复现 2019-12-02 03:25:31
python 下划线_我终于把Python中下划线的含义弄清楚了(憋了很久了) 2019-12-02 03:25:32
串口数据解析_物联网基础:EC20 连接阿里云进行数据收发 2019-12-02 03:25:32
反arp攻击软件_甜橙安全头条第23期技术干货之透析中间人攻击 2019-12-02 03:25:32
storm 机器上日志查询_达达基于Kubernetes混部的日志系统演变 2019-12-02 03:25:33
高精度事件计时器怎么关闭_Node.js 事件循环的工作流程 &amp; 生命周期 2019-12-02 03:25:33
行业网站设计策划书_2020年餐饮开店方案策划书 2019-12-02 03:25:33
计算机基础知识_计算机基础知识的最小集合 2019-12-02 03:25:33
composer升级_Composer 2.0 发布带来的性能优化、新特性和升级指南 2019-12-02 03:25:30