在处理矢量化数据时，记录中往往话苄很多反复数据，对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间，另一方面造成所要表达的图形不但滑或不相符标准。是以要经由过程某种规矩，在包管矢量曲线外形不变的情况下， 最大年夜限度地削减数据点个数，这个过程称为抽稀。

【51CTO晃荡】8.26 带你与清华大年夜学、搜狗、京东大年夜咖们一路商量基于算法的IT运维实践

何为抽稀

通俗的讲就是对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且可以或许在必定程度保持原有外形。比较常用的两种抽稀算法是：道格拉斯-普克(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)) 	
			
 1/7    1 2 3 4 5 6 下一页 尾页
	
			

　　推荐阅读
　　功能抢眼！腾讯杀手级新品智能手环S8发布：对飙小米
            【51CTO晃荡】8.26 带你与清华大年夜学、搜狗、京东大年夜咖们一路商量基于算法的IT运维实践

            拥有微信和 QQ 两大年夜霸王级应用，腾讯推出基于社交应用的硬件，的确合偶合理，当然了这看>>>详细阅读


本文标题：两种曲线点抽稀算法-Python实现 附代码
地址：http://www.17bianji.com/lsqh/36842.html
 1/2    1