A little while ago I was working on a project that dealt with the simplification of rail tracks logged by GPS for the Algorithm Engineering Group of Technische Universität Darmstadt using data provided by Deutsche Bahn.

Because the data contained too many coordinates, something had to be done in order to reduce the number of points the rail tracks were representy by. The Ramer-Douglas-Peucker algorithm Ramer (1972) and Douglas and Peucker (1973), an algorithm used for reducing the number of points in a curve, came in quite handy for this task.

Visualization

In the graph below you can see the algorithm in action. Move and release the slider in order to see the results of the RDP algorithm applied to the problem at hand.

ε =
Original # of points:
Simplified # of points:


Python Implementation

I've created a Python implementation of the RDP algorithm, which can be installed via pip:

pip install rdp

And be used like this:

from rdp import rdp

res = rdp([[1, 1], [1, 1.1], [2, 2]], epsilon=0.5)
print(res)
## [[1.0, 1.0], [2.0, 2.0]]

Behind the scenes, this implementation uses numpy and hence supports passing a numpy array as well.

As far as the Point-Line-Distance in 2-Dimensional space is concerned, linear algebra comes to the rescue. The implementation uses a custom distance function: If the line is specified by two points \(\textbf{x}_1 = (x_1, y_1)\) and \(\textbf{x}_2 = (x_2, y_2)\), then the distance from the point \(\textbf{x}_0 = (x_0, y_0)\) is given by

\(d = \frac{|\text{det}(\textbf{x}_2 - \textbf{x}_1 \textbf{x}_1 - \textbf{x}_0)|}{|\textbf{x}_2 - \textbf{x}_1|}\)

where \(\text{det}(A)\) denotes a determinant. The derivation of this formula can be found on Wolfram MathWorld. This can be translated into python as follows:

import numpy as np

def pldist(x0, x1, x2):
    if x1[0] == x2[0]:
        return np.abs(x0[0] - x1[0])

    return np.divide(np.linalg.norm(np.linalg.det([x2 - x1, x1 - x0])),
                     np.linalg.norm(x2 - x1))

Bibliography

David H Douglas and Thomas K Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10(2):112–122, 1973.

Urs Ramer. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing, 1(3):244–256, 1972.


Comments

comments powered by Disqus