A Rust implementation of the Ramer–Douglas-Peucker line simplification algorithm.
The shared library exposes a FFI: simplify_linestring_ffi.
Some examples are available in this Jupyter notebook.
(There will be a package on PyPI soon.)
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)float. E.g. 1.0The return type is the same struct as above, containing the simplified linestring coordinates.
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.
A Python 2.7/3.5 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.
Douglas, David H, and Thomas K Peucker. 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 (2): 112–122. DOI
Ramer, Urs. 1972. “An Iterative Procedure for the Polygonal Approximation of Plane Curves.” Computer Graphics and Image Processing 1 (3): 244–256. DOI
This implementation doesn't use the Convex Hull speedup (Hershberger & Snoeyink, 1992). Its worst-case complexity is thus O(n2)