geometry.ramer_douglas_peucker
==============================

.. py:module:: geometry.ramer_douglas_peucker

.. autoapi-nested-parse::

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

.. autoapisummary::

   geometry.ramer_douglas_peucker._euclidean_distance
   geometry.ramer_douglas_peucker._perpendicular_distance
   geometry.ramer_douglas_peucker.ramer_douglas_peucker


Module Contents
---------------

.. py:function:: _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


.. py:function:: _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


.. py:function:: 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