python道格拉斯算法的实现

废话不多说直接开干
需要用到模块

pip install -i https://pypi.tuna.tsinghua.edu.cn/simple math #对浮点数的数学运算函数
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple shapely #提供几何形状的操作和分析，如交集、并集、差集等
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple matplotlib #可视化模块

项目需要优化运动轨迹路线用到道格拉斯算法相对来说很实用建议用到GPS定位同行可以试试看

运行代码

# -*- coding:utf-8 -*-
"""
道格拉斯算法的实现
程序需要安装shapely模块
"""
import math
from shapely import wkt, geometry
import matplotlib.pyplot as pltclass Point:"""点类"""x = 0.0y = 0.0index = 0  # 点在线上的索引def __init__(self, x, y, index):self.x = xself.y = yself.index = indexclass Douglas:"""道格拉斯算法类"""points = []D = 1  # 容差def readPoint(self):"""生成点要素"""g = wkt.loads("LINESTRING(1 4,2 3,4 2,6 6,7 7,8 6,9 5,10 10)")coords = g.coordsfor i in range(len(coords)):self.points.append(Point(coords[i][0], coords[i][1], i))def compress(self, p1, p2):"""具体的抽稀算法"""swichvalue = False# 一般式直线方程系数 A*x+B*y+C=0,利用点斜式,分母可以省略约区# A=(p1.y-p2.y)/math.sqrt(math.pow(p1.y-p2.y,2)+math.pow(p1.x-p2.x,2))A = (p1.y - p2.y)# B=(p2.x-p1.x)/math.sqrt(math.pow(p1.y-p2.y,2)+math.pow(p1.x-p2.x,2))B = (p2.x - p1.x)# C=(p1.x*p2.y-p2.x*p1.y)/math.sqrt(math.pow(p1.y-p2.y,2)+math.pow(p1.x-p2.x,2))C = (p1.x * p2.y - p2.x * p1.y)m = self.points.index(p1)n = self.points.index(p2)distance = []middle = Noneif (n == m + 1):return# 计算中间点到直线的距离for i in range(m + 1, n):d = abs(A * self.points[i].x + B * self.points[i].y + C) / math.sqrt(math.pow(A, 2) + math.pow(B, 2))distance.append(d)dmax = max(distance)if dmax > self.D:swichvalue = Trueelse:swichvalue = Falseif (not swichvalue):for i in range(m + 1, n):del self.points[i]else:for i in range(m + 1, n):if (abs(A * self.points[i].x + B * self.points[i].y + C) / math.sqrt(math.pow(A, 2) + math.pow(B, 2)) == dmax):middle = self.points[i]self.compress(p1, middle)self.compress(middle, p2)def printPoint(self):"""打印数据点"""for p in self.points:print( "%d,%f,%f" % (p.index, p.x, p.y))def main():"""测试"""d = Douglas()d.readPoint()# d.printPoint()# 结果图形的绘制，抽稀之前绘制fig = plt.figure()a1 = fig.add_subplot(121)dx = []dy = []for i in range(len(d.points)):dx.append(d.points[i].x)dy.append(d.points[i].y)a1.plot(dx, dy, color='g', linestyle='-', marker='+')d.compress(d.points[0], d.points[len(d.points) - 1]) #稀释后轨迹# 抽稀之后绘制dx1 = []dy1 = []a2 = fig.add_subplot(122)for p in d.points:print(p.x,p.y)dx1.append(p.x)dy1.append(p.y)a2.plot(dx1, dy1, color='r', linestyle='-', marker='+')plt.show()if __name__ == '__main__':main()