【51CTO活动】8.26 带你与清华大学、搜狗、京东大咖们一同讨论基于算法的IT运维实际
何为抽稀
在处置矢量化数据时，记载中往往会有很多反双数据，对进一步数据处置带来诸多不便。多余的数据一方面糜费了较多的存储空间，另一方面形成所要表达的图形不润滑或不契合标准。因此要经过某种规则，在保证矢量曲线外形不变的状况下， 最大限制地减少数据点个数，这个进程称为抽稀。
深刻的讲就是对曲线停止采样简化，即在曲线上取有限个点，将其变为折线，并且可以在一定水平保持原有外形。比较常用的两种抽稀算法是：道格拉斯-普克(Douglas-Peuker)算法和垂距限值法。
道格拉斯-普克(Douglas-Peuker)算法
Douglas-Peuker算法(DP算法)进程如下:
衔接曲线首尾两点A、B;
依次计算曲线上一切点到A、B两点所在曲线的距离;
计算最大距离D，假设D小于阈值threshold,则去掉曲线上出A、B外的一切点;假设D大于阈值threshold,则把曲线以最大距离联系成两段;
对一切曲线分段重复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
(责任编辑：admin)