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: simplify_rdp_ffi, and simplify_visvalingam_ffi.
Some examples are available in this Jupyter notebook.
Simplification, a Python package which uses this shared library, is available from PyPi.

Arguments

• A C-compatible struct containing the following fields:
  • data: a void pointer to a 2D array of double-precision floats: [[1.0, 2.0], [3.0, 4.0], [5.0, 6.0]]
  • len: a size_t denoting the length of the array (i.e. 3, above)
• A precision parameter, double_precision float. E.g. 1.0

The return type is the same struct as above, containing the simplified linestring coordinates.

Freeing FFI Memory

Callers must call drop_float_array(), passing the returned struct, in order to free the memory that the shared library has allocated. Failure to do so will result in memory leaks.

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