Skip to content

polykin.math¤

simplify_polyline ¤

simplify_polyline(
    points: FloatMatrix, tol: float
) -> FloatMatrix

Simplify an N-dimensional polyline using the Ramer-Douglas-Peucker algorithm.

The Ramer-Douglas-Peucker algorithm is considered the best global polyline simplification algorithm. This particular implementation is based on the recursive version of the method.

References

  • Ramer, Urs. "An iterative procedure for the polygonal approximation of plane curves." Computer graphics and image processing 1.3 (1972): 244-256.
  • Douglas, David H., 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 (1973): 112-122.
PARAMETER DESCRIPTION
points

Matrix of point coordinates.

TYPE: FloatMatrix

tol

Point-to-edge distance tolerance. Points closer than tol are removed.

TYPE: float

RETURNS DESCRIPTION
FloatMatrix

Simplified polyline.

Examples:

Simplify a 2D polyline.

>>> from polykin.math import simplify_polyline
>>> p = np.array([[0.0, 0.0],
...               [1.0, 0.1],
...               [2.0, -0.1],
...               [3.0, 5.0],
...               [4.0, 6.0],
...               [5.0, 7.0],
...               [6.0, 8.1],
...               [7.0, 9.0],
...               [8.0, 9.0],
...               [9.0, 9.0]])
>>> simplify_polyline(p, tol=1.0)
array([[ 0. ,  0. ],
       [ 2. , -0.1],
       [ 3. ,  5. ],
       [ 7. ,  9. ],
       [ 9. ,  9. ]])
Source code in src/polykin/math/filters.py 
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
def simplify_polyline(points: FloatMatrix,
                      tol: float
                      ) -> FloatMatrix:
    r"""Simplify an N-dimensional polyline using the Ramer-Douglas-Peucker
    algorithm.

    The Ramer-Douglas-Peucker algorithm is considered the best global polyline
    simplification algorithm. This particular implementation is based on the
    recursive version of the method. 

    **References**

    * Ramer, Urs. "An iterative procedure for the polygonal approximation of
    plane curves." Computer graphics and image processing 1.3 (1972): 244-256.
    * Douglas, David H., 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 (1973): 112-122.

    Parameters
    ----------
    points : FloatMatrix
        Matrix of point coordinates.
    tol : float
        Point-to-edge distance tolerance. Points closer than `tol` are removed.

    Returns
    -------
    FloatMatrix
        Simplified polyline.

    Examples
    --------
    Simplify a 2D polyline.
    >>> from polykin.math import simplify_polyline
    >>> p = np.array([[0.0, 0.0],
    ...               [1.0, 0.1],
    ...               [2.0, -0.1],
    ...               [3.0, 5.0],
    ...               [4.0, 6.0],
    ...               [5.0, 7.0],
    ...               [6.0, 8.1],
    ...               [7.0, 9.0],
    ...               [8.0, 9.0],
    ...               [9.0, 9.0]])
    >>> simplify_polyline(p, tol=1.0)
    array([[ 0. ,  0. ],
           [ 2. , -0.1],
           [ 3. ,  5. ],
           [ 7. ,  9. ],
           [ 9. ,  9. ]])
    """

    nvert, ndims = points.shape

    if ndims < 2:
        raise ValueError("Polyline must have at least 2 dimensions.")

    if nvert < 2:
        raise ValueError("Polyline must have at least 2 points.")
    elif nvert == 2:
        return points
    else:
        idx = _ramer_douglas_peucker(points, 0, nvert - 1, tol)
        return points[idx, :]