### 14 unstable releases (6 breaking)

0.12.0 | Dec 1, 2021 |
---|---|

0.11.20 | Nov 25, 2021 |

0.8.3 | Mar 29, 2020 |

0.5.0 | Jan 7, 2019 |

0.1.5 | Aug 8, 2016 |

#**958** in Algorithms

**MIT**license

140KB

1K
SLoC

# RDP

A Rust implementation of the Ramer–Douglas-Peucker and Visvalingam-Whyatt line simplification algorithms.

**The algorithms underlying this crate have now migrated to rust-geo as the **

`Simplify`and

`SimplifyVW`traits.

# FFI

The shared library exposes a(n) FFI: https://docs.rs/rdp/latest/rdp/#functions.

Some examples are available in this Jupyter notebook.

**Simplification**, a Python package which uses this shared library, is available from PyPi.

### Example Implementation

A Python 2.7 / 3.5 / 3.6 implementation can be found at `ffi .py`

Run

`cargo`` build`` --`release

, then `python ffi``.`py

to test. It's also importable, exposing `simplify_linestring``(``)`

– call it with a coordinate list and a precision parameter. Allocated memory is dropped on exit.# Performance & Complexity

On an 841-point LineString, RDP runs around 3.5x faster than VW. However, RDP's worst-case time complexity is O(*n*^{2}) – This implementation doesn't use the Convex Hull Speedup, see Hershberger & Snoeyink, 1992 – whereas the VW implementation uses a min-heap, and thus has worst-case time-complexity of O(*n* log(*n*)), which may make it a better choice for larger LineStrings under certain conditions; RDP has an *average* time complexity of O(*n* log(*n*)), but LineStrings such as the one seen here will slow it down significantly.
You can verify these times for yourself by running

.`cargo`` bench`

# License

# References

**Douglas, D.H.**, **Peucker, T.K.**, 1973. *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, 112–122. DOI

**Ramer, U.**, 1972. *An iterative procedure for the polygonal approximation of plane curves*. Computer Graphics and Image Processing 1, 244–256. DOI

**Visvalingam, M.**, **Whyatt, J.D.**, 1993. *Line generalisation by repeated elimination of points*. The Cartographic Journal 30, 46–51. DOI

#### Dependencies

~3MB

~62K SLoC