geometry.ramer_douglas_peucker¶

Ramer-Douglas-Peucker polyline simplification algorithm.

Given a sequence of 2-D points and a tolerance epsilon, the algorithm reduces the number of points while preserving the overall shape of the curve.

Time complexity: O(n log n) average, O(n²) worst case Space complexity: O(n)

References:: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Functions¶

`_euclidean_distance`(→ float)	Return the Euclidean distance between two 2-D points.
`_perpendicular_distance`(→ float)	Return the distance from point to the line segment between
`ramer_douglas_peucker`(→ list[tuple[float, float]])	Simplify a polyline using the Ramer-Douglas-Peucker algorithm.

Module Contents¶

geometry.ramer_douglas_peucker._euclidean_distance(point_a: tuple[float, float], point_b: tuple[float, float]) → float¶

Return the Euclidean distance between two 2-D points.

>>> _euclidean_distance((0.0, 0.0), (3.0, 4.0))
5.0
>>> _euclidean_distance((1.0, 1.0), (1.0, 1.0))
0.0

geometry.ramer_douglas_peucker._perpendicular_distance(point: tuple[float, float], line_start: tuple[float, float], line_end: tuple[float, float]) → float¶

Return the distance from point to the line segment between line_start and line_end.

When the perpendicular projection of point onto the infinite line falls within the segment, this equals the perpendicular distance to that line. When the projection falls outside the segment, the distance to the nearest endpoint is returned instead (projection clamped to [0, 1]).

This is the correct distance measure for the Ramer-Douglas-Peucker algorithm: using the infinite-line distance can incorrectly discard points whose projection lies beyond a segment endpoint.

>>> _perpendicular_distance((4.0, 0.0), (0.0, 0.0), (0.0, 3.0))
4.0
>>> # order of line_start and line_end does not affect the result
>>> _perpendicular_distance((4.0, 0.0), (0.0, 3.0), (0.0, 0.0))
4.0
>>> _perpendicular_distance((4.0, 1.0), (0.0, 1.0), (0.0, 4.0))
4.0
>>> _perpendicular_distance((2.0, 1.0), (-2.0, 1.0), (-2.0, 4.0))
4.0
>>> # projection falls outside the segment; distance to nearest endpoint
>>> round(_perpendicular_distance((0.0, 2.0), (1.0, 0.0), (3.0, 0.0)), 6)
2.236068

geometry.ramer_douglas_peucker.ramer_douglas_peucker(pts: list[tuple[float, float]], epsilon: float) → list[tuple[float, float]]¶

Simplify a polyline using the Ramer-Douglas-Peucker algorithm.

Given a sequence of 2-D points and a maximum allowable deviation epsilon (>= 0), returns a simplified list of points such that no discarded point is farther than epsilon from the simplified polyline.

Parameters¶

pts:: Ordered sequence of (x, y) points describing the polyline.
epsilon:: Maximum allowable distance of any discarded point from the simplified polyline. Must be non-negative.

Returns¶

list[tuple[float, float]]: Simplified list of (x, y) points. The first and last points of pts are always preserved.

Raises¶

ValueError: If epsilon is negative.

References¶

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Examples¶

>>> ramer_douglas_peucker([], epsilon=1.0)
[]
>>> ramer_douglas_peucker([(0.0, 0.0)], epsilon=1.0)
[(0.0, 0.0)]
>>> ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.0)], epsilon=1.0)
[(0.0, 0.0), (1.0, 0.0)]
>>> # middle point is within epsilon - it is discarded
>>> ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.1), (2.0, 0.0)], epsilon=0.5)
[(0.0, 0.0), (2.0, 0.0)]
>>> # middle point exceeds epsilon - it is kept
>>> ramer_douglas_peucker([(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)], epsilon=0.5)
[(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)]
>>> ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.5), (2.0, 0.0)], epsilon=-1.0)
Traceback (most recent call last):
    ...
ValueError: epsilon must be non-negative, got -1.0