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²) – 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

MIT

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