Point Line Distance und Douglas Peucker
This notebook presents a simplistic implementation of Douglas Peucker’s line simplification algorithm. This algorithm is largely based on the concept of a point line distance, which is easy to implemented in Euclidean geometry. In the sequel, the function dist provides the Euclidean distance between two vectors and the function pld calculates the distance of the third parameter to the line segment given by the first two parameters.
import numpy as np; # Distanz def dist(u,v): return np.sqrt(np.sum(np.square(np.array(u)-np.array(v)))) # Point Line Distance for Segment u->v mit p def pld(u,v,p): u = np.array(u) v = np.array(v) p = np.array(p) l = dist(u,v) # length of segment if (abs(l) < 1E-12): # line is very short return np.sqrt(dist(p,v)) t = np.dot((v-u),(p-u)) / (l*l) if t < 0: # use startpoint if projection is before return np.sqrt(dist(p,u)) if t > 1: return np.sqrt(dist(p,v)) # use endpoint if projection is after proj = u + t*(v-u) return dist(p, proj) print("Dist: %f"%dist ([1,1],[2,2])) print("Distance: %f " % (pld([1,1],[3,3],[2,2.1])))
Dist: 1.414214 Distance: 0.070711
Douglas Peucker Simplification
The Douglas Peucker Line Simplification is a recursive process in which the given linestring is first approximated by a single line from start to end point. Then, the point of the trajectory with the largest point-line distance to this approximation line is calculated. If this is larger than a given threshold, this point is used to split the trajectory into two pieces each of which are then further processed independently. The final simplification is the concatenation of all line segments generated in this process for which the error is small enough such that they are not further subdivided
The following implementation uses a recurive approach. Note that this recursion can and should be resolved into a loop in order not to avoid stack overflows. A decent implementation is available in libtrajcomp https://www.github.com/mwernerds/trajcomp
from matplotlib import pyplot as plt; import matplotlib.lines as lines def douglas_peucker(traj, eps): if traj.shape <= 2: # no way to simplify return traj distances = [pld(traj[0,:],traj[-1,:],x) for x in traj] pos = np.argmax(distances) if distances[pos] > eps: return np.vstack([ douglas_peucker(traj[:(pos+1)], eps), traj[pos,:], douglas_peucker(traj[(pos+1):], eps) ]) else: return np.vstack([traj[0,:],traj[-1,:]])
The following code snippet first creates a trajectory, then runs Douglas Peucker to find a simplification. The remainder of the code just presents a figure with both lines (red for the original, blue for the simplification).
traj = np.array([[1,1],[2,5],[3,3.05],[4,3.1],[5,3]]) simp = douglas_peucker(traj,5) fig = plt.figure() l1 = lines.Line2D(traj[:,0],traj[:,1],color="r", transform=fig.transFigure, figure=fig) l2 = lines.Line2D(simp[:,0],simp[:,1],color="b", transform=fig.transFigure, figure=fig) fig.lines.extend([l1,l2]) plt.show()