文档章节

曲线点抽稀算法-Python实现

j_hao104
 j_hao104
发布于 2017/08/18 09:44
字数 1616
阅读 1288
收藏 87
点赞 2
评论 3

何为抽稀

在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间,另一方面造成所要表达的图形不光滑或不符合标准。因此要通过某种规则,在保证矢量曲线形状不变的情况下, 最大限度地减少数据点个数,这个过程称为抽稀。

通俗的讲就是对曲线进行采样简化,即在曲线上取有限个点,将其变为折线,并且能够在一定程度保持原有形状。比较常用的两种抽稀算法是:道格拉斯-普克(Douglas-Peuker)算法和垂距限值法。

道格拉斯-普克(Douglas-Peuker)算法

Douglas-Peuker算法(DP算法)过程如下:

  • 1、连接曲线首尾两点A、B;
  • 2、依次计算曲线上所有点到A、B两点所在曲线的距离;
  • 3、计算最大距离D,如果D小于阈值threshold,则去掉曲线上出A、B外的所有点;如果D大于阈值threshold,则把曲线以最大距离分割成两段;
  • 4、对所有曲线分段重复1-3步骤,知道所有D均小于阈值。即完成抽稀。

这种算法的抽稀精度与阈值有很大关系,阈值越大,简化程度越大,点减少的越多;反之简化程度越低,点保留的越多,形状也越趋于原曲线。

下面是Python代码实现:

# -*- coding: utf-8 -*-
"""
-------------------------------------------------
  File Name:    DouglasPeuker
  Description :  道格拉斯-普克抽稀算法
  Author :        J_hao
  date:          2017/8/16
-------------------------------------------------
  Change Activity:
                  2017/8/16: 道格拉斯-普克抽稀算法
-------------------------------------------------
"""
from __future__ import division

from math import sqrt, pow

__author__ = 'J_hao'

THRESHOLD = 0.0001  # 阈值


def point2LineDistance(point_a, point_b, point_c):
    """
    计算点a到点b c所在直线的距离
    :param point_a:
    :param point_b:
    :param point_c:
    :return:
    """
    # 首先计算b c 所在直线的斜率和截距
    if point_b[0] == point_c[0]:
        return 9999999
    slope = (point_b[1] - point_c[1]) / (point_b[0] - point_c[0])
    intercept = point_b[1] - slope * point_b[0]

    # 计算点a到b c所在直线的距离
    distance = abs(slope * point_a[0] - point_a[1] + intercept) / sqrt(1 + pow(slope, 2))
    return distance


class DouglasPeuker(object):
    def __init__(self):
        self.threshold = THRESHOLD
        self.qualify_list = list()
        self.disqualify_list = list()

    def diluting(self, point_list):
        """
        抽稀
        :param point_list:二维点列表
        :return:
        """
        if len(point_list) < 3:
            self.qualify_list.extend(point_list[::-1])
        else:
            # 找到与收尾两点连线距离最大的点
            max_distance_index, max_distance = 0, 0
            for index, point in enumerate(point_list):
                if index in [0, len(point_list) - 1]:
                    continue
                distance = point2LineDistance(point, point_list[0], point_list[-1])
                if distance > max_distance:
                    max_distance_index = index
                    max_distance = distance

            # 若最大距离小于阈值,则去掉所有中间点。 反之,则将曲线按最大距离点分割
            if max_distance < self.threshold:
                self.qualify_list.append(point_list[-1])
                self.qualify_list.append(point_list[0])
            else:
                # 将曲线按最大距离的点分割成两段
                sequence_a = point_list[:max_distance_index]
                sequence_b = point_list[max_distance_index:]

                for sequence in [sequence_a, sequence_b]:
                    if len(sequence) < 3 and sequence == sequence_b:
                        self.qualify_list.extend(sequence[::-1])
                    else:
                        self.disqualify_list.append(sequence)

    def main(self, point_list):
        self.diluting(point_list)
        while len(self.disqualify_list) > 0:
            self.diluting(self.disqualify_list.pop())
        print self.qualify_list
        print len(self.qualify_list)


if __name__ == '__main__':
    d = DouglasPeuker()
    d.main([[104.066228, 30.644527], [104.066279, 30.643528], [104.066296, 30.642528], [104.066314, 30.641529],
            [104.066332, 30.640529], [104.066383, 30.639530], [104.066400, 30.638530], [104.066451, 30.637531],
            [104.066468, 30.636532], [104.066518, 30.635533], [104.066535, 30.634533], [104.066586, 30.633534],
            [104.066636, 30.632536], [104.066686, 30.631537], [104.066735, 30.630538], [104.066785, 30.629539],
            [104.066802, 30.628539], [104.066820, 30.627540], [104.066871, 30.626541], [104.066888, 30.625541],
            [104.066906, 30.624541], [104.066924, 30.623541], [104.066942, 30.622542], [104.066960, 30.621542],
            [104.067011, 30.620543], [104.066122, 30.620086], [104.065124, 30.620021], [104.064124, 30.620022],
            [104.063124, 30.619990], [104.062125, 30.619958], [104.061125, 30.619926], [104.060126, 30.619894],
            [104.059126, 30.619895], [104.058127, 30.619928], [104.057518, 30.620722], [104.057625, 30.621716],
            [104.057735, 30.622710], [104.057878, 30.623700], [104.057984, 30.624694], [104.058094, 30.625688],
            [104.058204, 30.626682], [104.058315, 30.627676], [104.058425, 30.628670], [104.058502, 30.629667],
            [104.058518, 30.630667], [104.058503, 30.631667], [104.058521, 30.632666], [104.057664, 30.633182],
            [104.056664, 30.633174], [104.055664, 30.633166], [104.054672, 30.633289], [104.053758, 30.633694],
            [104.052852, 30.634118], [104.052623, 30.635091], [104.053145, 30.635945], [104.053675, 30.636793],
            [104.054200, 30.637643], [104.054756, 30.638475], [104.055295, 30.639317], [104.055843, 30.640153],
            [104.056387, 30.640993], [104.056933, 30.641830], [104.057478, 30.642669], [104.058023, 30.643507],
            [104.058595, 30.644327], [104.059152, 30.645158], [104.059663, 30.646018], [104.060171, 30.646879],
            [104.061170, 30.646855], [104.062168, 30.646781], [104.063167, 30.646823], [104.064167, 30.646814],
            [104.065163, 30.646725], [104.066157, 30.646618], [104.066231, 30.645620], [104.066247, 30.644621], ])

垂距限值法

垂距限值法其实和DP算法原理一样,但是垂距限值不是从整体角度考虑,而是依次扫描每一个点,检查是否符合要求。

算法过程如下:

  • 1、以第二个点开始,计算第二个点到前一个点和后一个点所在直线的距离d;
  • 2、如果d大于阈值,则保留第二个点,计算第三个点到第二个点和第四个点所在直线的距离d;若d小于阈值则舍弃第二个点,计算第三个点到第一个点和第四个点所在直线的距离d;
  • 3、依次类推,直线曲线上倒数第二个点。

下面是Python代码实现:

# -*- coding: utf-8 -*-
"""
-------------------------------------------------
  File Name:    LimitVerticalDistance
  Description :  垂距限值抽稀算法
  Author :        J_hao
  date:          2017/8/17
-------------------------------------------------
  Change Activity:
                  2017/8/17:
-------------------------------------------------
"""
from __future__ import division

from math import sqrt, pow

__author__ = 'J_hao'

THRESHOLD = 0.0001  # 阈值


def point2LineDistance(point_a, point_b, point_c):
    """
    计算点a到点b c所在直线的距离
    :param point_a:
    :param point_b:
    :param point_c:
    :return:
    """
    # 首先计算b c 所在直线的斜率和截距
    if point_b[0] == point_c[0]:
        return 9999999
    slope = (point_b[1] - point_c[1]) / (point_b[0] - point_c[0])
    intercept = point_b[1] - slope * point_b[0]

    # 计算点a到b c所在直线的距离
    distance = abs(slope * point_a[0] - point_a[1] + intercept) / sqrt(1 + pow(slope, 2))
    return distance


class LimitVerticalDistance(object):
    def __init__(self):
        self.threshold = THRESHOLD
        self.qualify_list = list()

    def diluting(self, point_list):
        """
        抽稀
        :param point_list:二维点列表
        :return:
        """
        self.qualify_list.append(point_list[0])
        check_index = 1
        while check_index < len(point_list) - 1:
            distance = point2LineDistance(point_list[check_index],
                                          self.qualify_list[-1],
                                          point_list[check_index + 1])

            if distance < self.threshold:
                check_index += 1
            else:
                self.qualify_list.append(point_list[check_index])
                check_index += 1
        return self.qualify_list


if __name__ == '__main__':
    l = LimitVerticalDistance()
    diluting = l.diluting([[104.066228, 30.644527], [104.066279, 30.643528], [104.066296, 30.642528], [104.066314, 30.641529],
            [104.066332, 30.640529], [104.066383, 30.639530], [104.066400, 30.638530], [104.066451, 30.637531],
            [104.066468, 30.636532], [104.066518, 30.635533], [104.066535, 30.634533], [104.066586, 30.633534],
            [104.066636, 30.632536], [104.066686, 30.631537], [104.066735, 30.630538], [104.066785, 30.629539],
            [104.066802, 30.628539], [104.066820, 30.627540], [104.066871, 30.626541], [104.066888, 30.625541],
            [104.066906, 30.624541], [104.066924, 30.623541], [104.066942, 30.622542], [104.066960, 30.621542],
            [104.067011, 30.620543], [104.066122, 30.620086], [104.065124, 30.620021], [104.064124, 30.620022],
            [104.063124, 30.619990], [104.062125, 30.619958], [104.061125, 30.619926], [104.060126, 30.619894],
            [104.059126, 30.619895], [104.058127, 30.619928], [104.057518, 30.620722], [104.057625, 30.621716],
            [104.057735, 30.622710], [104.057878, 30.623700], [104.057984, 30.624694], [104.058094, 30.625688],
            [104.058204, 30.626682], [104.058315, 30.627676], [104.058425, 30.628670], [104.058502, 30.629667],
            [104.058518, 30.630667], [104.058503, 30.631667], [104.058521, 30.632666], [104.057664, 30.633182],
            [104.056664, 30.633174], [104.055664, 30.633166], [104.054672, 30.633289], [104.053758, 30.633694],
            [104.052852, 30.634118], [104.052623, 30.635091], [104.053145, 30.635945], [104.053675, 30.636793],
            [104.054200, 30.637643], [104.054756, 30.638475], [104.055295, 30.639317], [104.055843, 30.640153],
            [104.056387, 30.640993], [104.056933, 30.641830], [104.057478, 30.642669], [104.058023, 30.643507],
            [104.058595, 30.644327], [104.059152, 30.645158], [104.059663, 30.646018], [104.060171, 30.646879],
            [104.061170, 30.646855], [104.062168, 30.646781], [104.063167, 30.646823], [104.064167, 30.646814],
            [104.065163, 30.646725], [104.066157, 30.646618], [104.066231, 30.645620], [104.066247, 30.644621], ])
    print len(diluting)
    print(diluting)

最后

其实DP算法和垂距限值法原理一样,DP算法是从整体上考虑一条完整的曲线,实现时较垂距限值法复杂,但垂距限值法可能会在某些情况下导致局部最优。另外在实际使用中发现采用点到另外两点所在直线距离的方法来判断偏离,在曲线弧度比较大的情况下比较准确。如果在曲线弧度比较小,弯曲程度不明显时,这种方法抽稀效果不是很理想,建议使用三点所围成的三角形面积作为判断标准。下面是抽稀效果:

博文地址:http://www.spiderpy.cn/blog/detail/29

© 著作权归作者所有

共有 人打赏支持
j_hao104
粉丝 199
博文 67
码字总数 101848
作品 2
程序员
加载中

评论(3)

gonnavis
gonnavis
kernel64
kernel64
轮廓提取
公孙二狗
公孙二狗
好文章
道格拉斯-普克 抽稀算法 附javascript实现

道格拉斯-普克抽稀算法,是用来对大量冗余的图形数据点进行压缩以提取必要的数据点。该算法实现抽稀的过程是:先将一条曲线首尾点虚连一条直线,求其余各点到该直线的距离,取其最大者与规定...

行列
07/06
0
0
曲线点抽稀算法- Python 实现

原文出处:jhao104 何为抽稀 在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间,另一方面造成所要表达的图形不光滑或...

j_hao104
2017/11/19
0
0
几个Python小案例,爱上Python编程!

Python是一种面向对象的解释型编程语言,源代码与解释器CPython遵守GPL协议,Python语法简洁清晰。 语法简洁清晰,那么我们用少量的Python代码能做哪些有趣的东西?温馨提示:文末必看。 一、...

qq1622479435
06/17
0
0
一文简述多种无监督聚类算法的Python实现

  本文简要介绍了多种无监督学习算法的 Python 实现,包括 K 均值聚类、层次聚类、t-SNE 聚类、DBSCAN 聚类。   无监督学习是一类用于在数据中寻找模式的机器学习技术。无监督学习算法使...

深度学习
05/23
0
0
教程 | 一文简述多种无监督聚类算法的Python实现

  选自towardsdatascience   作者:Vihar Kurama   机器之心编译   参与:Geek AI、路      本文简要介绍了多种无监督学习算法的 Python 实现,包括 K 均值聚类、层次聚类、t-S...

机器之心
05/22
0
0
python中使用递归实现koch曲线绘制

python 中使用递归绘制koch曲线 koch曲线是由瑞典数学家Helge von Koch,在1904年发表的“从初等几何构造的一条没有切线的连续曲线”的论文中提出的。它的描述如下: 1、指定一条线段的长度(...

kochkong
2013/12/16
0
0
手把手教你在多种无监督聚类算法实现Python(附代码)

无监督学习是一类用于在数据中寻找模式的机器学习技术。无监督学习算法使用的输入数据都是没有标注过的,这意味着数据只给出了输入变量(自变量 X)而没有给出相应的输出变量(因变量)。在无...

技术小能手
06/01
0
0
Python VS R,哪个更适合开发者?

21CTO社区导读:Python和R同时出现在20世纪九十年代。它为数据科学家提供了大量的数据模型操作的能力。在发展了30年后,Python与R开始出现不同的爱好者阵营。 90年代出现了互联网,这一事物永...

21CTO
04/28
0
0
Fedora 14下配置Python开发环境

pythone新闻1则 Python十分适合解决很多简单的、有趣的问题,比用C语言要省力的多。(这是实话,几行Python代码你就能制作一个简单的拼写检查程 序。)你会发现这种语言里几乎没有任何复杂或让...

墙头草
2011/03/29
0
1
机器学习:最小二乘法实际应用的一个完整例子

整个过程分七步,为了方便喜欢直接copy代码看结果的同学,每步都放上了完整的代码。 实验数据: 第一步:准备样本数据并绘制散点图 1)代码及其说明 import numpy as npimport scipy as spim...

wangxuwei
07/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CentoOS6.6安装netcat

CentOS下安装netcat 使用zookeeper过程中,需要监控集群状态。在使用四字命令时(echo conf | nc localhost 2181),报出如下错误:-bash: netcat: command not found。 我的系统是CentOS 6....

ghou-靠墙哭
9分钟前
0
0
es6之解构赋值巧用

ES6 允许按照一定模式,从数组、对象等中提取值,对变量进行赋值,这被称为解构赋值。 如何进行解构赋值我这里就不赘述,本篇文章主要是将解构赋值的巧妙使用之处。 1、交互变量的值 常用交互...

秋季长青
15分钟前
0
0
Elasitcsearch High Level Rest Client学习笔记(三)批量api

Bulk Request BulkRequest可以在一起从请求执行批量添加、更新和删除,至少需要添加一个操作 BulkRequest request = new BulkRequest(); //创建BulkRequestrequest.add(new IndexRequest("...

木子SMZ
18分钟前
0
0
mybatis-dynamic sql

OGNL expressions if 判断是否存在值 <select id="findActiveBlogLike" resultType="Blog"> SELECT * FROM BLOG WHERE state = ‘ACTIVE’ <if test="title != null"> AND title like #{tit......

writeademo
25分钟前
0
0
社交系统ThinkSNS+ V1.8.3更新播报

     研发发布版本号:1.8.3   本次版本于2018年7月16日发布   本次发布类型:新增功能、细节调整与优化   社交系统ThinkSNSPlus更新体验:请于官网下载/安装最新版或联系QQ35159...

ThinkSNS账号
29分钟前
0
0
教育思考:选择编程是一场父母和孩子的和解[图]

教育思考:选择编程是一场父母和孩子的和解[图]: 之前有个很热的段子是这样讲的:深夜十点的时候,某小区一女子大声喊叫“什么关系?啊?!到底什么关系?你说!”最后发现原来是一位妈妈陪...

原创小博客
29分钟前
0
0
X64汇编之指令格式解析

最近由于项目组内要做特征码搜索的东西,便于去Hook一些未导出函数,你懂得...于是就闲着学习了一下x86/x64的汇编指令格式。x86的汇编指令格式请参照http://bbs.pediy.com/showthread.php?t...

simpower
32分钟前
0
0
rust 语法概要(只适合不熟悉时快速查阅使用,不适合理解其精髓。未完待续)

注意:本内容只适合快查,不适合理解精髓。精髓请研读 https://kaisery.github.io/trpl-zh-cn/foreword.html 基本数据类型 i8,i16,i32,i64,i128 u8,u16,u32,u64,u128 f32,f64 char bool:true...

捍卫机密
35分钟前
0
0
JS中严格模式和非严格模式

1,使用 严格模式的使用很简单,只有在代码首部加入字符串 "use strict"。必须在首部即首部指其前面没有任何有效js代码除注释,否则无效 2.注意事项 (1)不使用var声明变量严格模式中将不通...

AndyZhouX
36分钟前
0
0
Nginx配置error_page 404 500等自定义的错误页面

Nginx 做web server时, 开发中发现有时候的网站代码有错误,我们需要跳转到一个指定内容的错误页面: 1. 在nginx.conf配置文件上加上一句: fastcgi_intercept_errors on; 2. 服务中加上: er...

MichaelShu
38分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部