Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Python implementation of Ramer-Douglas-Peucker (RDP) algorithm; ported from JavaScript code at https://gist.github.com/msbarry/9152218; uses desired number of points instead of using a threshold.
# -*- 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.