麻辣GIS微信平台

更多 GIS 干货

微信关注不错过

「GIS算法」道格拉斯普克(Douglas-Peuker)算法原理图解

道格拉斯-普克算法(Douglas–Peucker algorithm),也称为拉默-道格拉斯-普克演算法(Ramer–Douglas–Peucker algorithm),从名字就可以看出这个算法是谁提出的,是GIS系统中用于简化曲线的一种常用算法。算法最初由拉默(Urs Ramer)于1972年提出,1973年道格拉斯(David Douglas)和普克(Thomas Peucker)二人又独立于拉默提出了该算法。

PS:看看GIS的前辈们有多卷,一个算法三个人发现了三次,名字都要用三个人的。

算法作用

在GIS系统中如何存储一条曲/折线?常见的方式就是使用使用一系列坐标点的集合来表示,点越多越密集,那么所能表示的精度就越高。在GIS画图的时候理想状况下,我们当然希望精度越高越好,但高精度的数据也会带来一些问题,比如对硬件系统的要求变高;比如在一些可视化场景里造成的渲染问题。

道格拉斯-普克算法正是用来解决这些问题的,它可以在保证一定精度的前提下,简化曲线的绘制过程,也是目前被广泛应用的GIS算法。基于线状实体的点压缩算法,用来压缩简化矢量数据。

算法流程

  1. 输入一系列坐标点组成的曲线。
  2. 曲线第一个点A和最后一个点B连成一条直线AB。
  3. 确认一个阈值(这个值用于控制简化后曲线的精度)
  4. 分别计算曲线上各点到这条直线的距离,并取出其中的最远距离与阈值进行比较。
  5. 如果最远距离大于阈值,则将该点保留,记为C,此时可以生成两条直线AC、CB,重复步骤4
  6. 否则将该点舍弃。

这么描述的有点抽象,我们还是看百科里给的动图。

图解

这个绿色的宽度就代表阈值,红色代表每次算法中最远的点,蓝色表示可以被移除的点,橙色表示最后生成的曲线。

参考

  1. 道格拉斯-普克算法 - 维基百科,自由的百科全书

  2. The Algorithm That Ties Together Google Maps and InfluxData’s Giraffe – The New Stack

  3. 道格拉斯普克(Douglas-Peuker)算法及python实现

相关阅读

麻辣GIS-Sailor

作者:

GIS爱好者,学GIS,更爱玩GIS。

声明

1.本文所分享的所有需要用户下载使用的内容(包括但不限于软件、数据、图片)来自于网络或者麻辣GIS粉丝自行分享,版权归该下载资源的合法拥有者所有,如有侵权请第一时间联系本站删除。

2.下载内容仅限个人学习使用,请切勿用作商用等其他用途,否则后果自负。

手机阅读
公众号关注
知识星球
手机阅读
麻辣GIS微信公众号关注
最新GIS干货
关注麻辣GIS知识星球
私享圈子

留言板(小编看到第一时间回复)