Python实现曲线点抽稀算法的示例
发布时间：2020-12-17 08:01:17 所属栏目：Python 来源：网络整理
导读：本文介绍了Python实现曲线点抽稀算法的示例，分享给大家，具体如下： 目录 何为抽稀 道格拉斯-普克(Douglas-Peuker)算法 垂距限值法 最后 正文 何为抽稀 在处理矢量化数据时，记录中往往会有很多重复数据，对进一步数据处理带来诸多不便。多余的数据一方面浪
|
本文介绍了Python实现曲线点抽稀算法的示例，分享给大家，具体如下： 目录
正文 何为抽稀 在处理矢量化数据时，记录中往往会有很多重复数据，对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间，另一方面造成所要表达的图形不光滑或不符合标准。因此要通过某种规则，在保证矢量曲线形状不变的情况下， 最大限度地减少数据点个数，这个过程称为抽稀。 通俗的讲就是对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度保持原有形状。比较常用的两种抽稀算法是：道格拉斯-普克(Douglas-Peuker)算法和垂距限值法。 道格拉斯-普克(Douglas-Peuker)算法 Douglas-Peuker算法(DP算法)过程如下: 1、连接曲线首尾两点A、B； 下面是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； 下面是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,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,])
print len(diluting)
print(diluting)
最后 其实DP算法和垂距限值法原理一样，DP算法是从整体上考虑一条完整的曲线，实现时较垂距限值法复杂，但垂距限值法可能会在某些情况下导致局部最优。另外在实际使用中发现采用点到另外两点所在直线距离的方法来判断偏离，在曲线弧度比较大的情况下比较准确。如果在曲线弧度比较小，弯��程度不明显时，这种方法抽稀效果不是很理想，建议使用三点所围成的三角形面积作为判断标准。下面是抽稀效果:
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程小技巧。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
