本文介绍了Python:具有点数而不是epsilon的Ramer-Douglas-Peucker(RDP)算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想针对,目的是不使用epsilon,而是选择我想保留在最后的点数:
I would like to modify this following python script for RDP algorithm with the purpose of not using epsilon but to choose the number of points I want to keep at the final :
class DPAlgorithm():
def distance(self, a, b):
return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
def point_line_distance(self, point, start, end):
if (start == end):
return self.distance(point, start)
else:
n = abs(
(end[0] - start[0]) * (start[1] - point[1]) - (start[0] - point[0]) * (end[1] - start[1])
)
d = sqrt(
(end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2
)
return n / d
def rdp(self, points, epsilon):
"""
Reduces a series of points to a simplified version that loses detail, but
maintains the general shape of the series.
"""
dmax = 0.0
index = 0
i=1
for i in range(1, len(points) - 1):
d = self.point_line_distance(points[i], points[0], points[-1])
if d > dmax :
index = i
dmax = d
if dmax >= epsilon :
results = self.rdp(points[:index+1], epsilon)[:-1] + self.rdp(points[index:], epsilon)
else:
results = [points[0], points[-1]]
return results
我本着这种精神发现了一个Java脚本:
I found a Java script in that spirit : https://gist.github.com/msbarry/9152218
有人知道Python 3.X的版本吗?
Does anyone know a version for Python 3.X ?
谢谢
Momow
ThanksMomow
推荐答案
从上面的链接中将JS代码移植到Python [2.7]:
Ported JS code from the link above to Python [2.7]:
# -*- coding: utf-8 -*-
import math
import time
def timenow():
return int(time.time() * 1000)
def sqr(x):
return x*x
def distSquared(p1, p2):
return sqr(p1[0] - p2[0]) + sqr(p1[1] - p2[1])
class Line(object):
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
self.lengthSquared = distSquared(self.p1, self.p2)
def getRatio(self, point):
segmentLength = self.lengthSquared
if segmentLength == 0:
return distSquared(point, p1);
return ((point[0] - self.p1[0]) * (self.p2[0] - self.p1[0]) + \
(point[1] - self.p1[1]) * (self.p2[1] - self.p1[1])) / segmentLength
def distanceToSquared(self, point):
t = self.getRatio(point)
if t < 0:
return distSquared(point, self.p1)
if t > 1:
return distSquared(point, self.p2)
return distSquared(point, [
self.p1[0] + t * (self.p2[0] - self.p1[0]),
self.p1[1] + t * (self.p2[1] - self.p1[1])
])
def distanceTo(self, point):
return math.sqrt(self.distanceToSquared(point))
def simplifyDouglasPeucker(points, pointsToKeep):
weights = []
length = len(points)
def douglasPeucker(start, end):
if (end > start + 1):
line = Line(points[start], points[end])
maxDist = -1
maxDistIndex = 0
for i in range(start + 1, end):
dist = line.distanceToSquared(points[i])
if dist > maxDist:
maxDist = dist
maxDistIndex = i
weights.insert(maxDistIndex, maxDist)
douglasPeucker(start, maxDistIndex)
douglasPeucker(maxDistIndex, end)
douglasPeucker(0, length - 1)
weights.insert(0, float("inf"))
weights.append(float("inf"))
weightsDescending = weights
weightsDescending = sorted(weightsDescending, reverse=True)
maxTolerance = weightsDescending[pointsToKeep - 1]
result = [
point for i, point in enumerate(points) if weights[i] >= maxTolerance
]
return result
这篇关于Python:具有点数而不是epsilon的Ramer-Douglas-Peucker(RDP)算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!