Download as Notebook

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[0] <= 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,:]])
   

Main Program

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()

png