✓ Uses Rust 2018 edition
|new 0.8.3||Mar 29, 2020|
|0.8.0||Mar 25, 2020|
|0.5.0||Jan 7, 2019|
|0.4.0||Aug 25, 2018|
|0.1.5||Aug 8, 2016|
#197 in Algorithms
81 downloads per month
The shared library exposes a(n) FFI:
Some examples are available in this Jupyter notebook.
Simplification, a Python package which uses this shared library, is available from PyPi.
- A C-compatible
structcontaining 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]]
size_tdenoting the length of the array (i.e.
- A precision parameter, double_precision
The 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 / 3.6 implementation can be found at
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.
On an 841-point LineString, RDP runs around 3.5x faster than VW. However, RDP's worst-case time complexity is O(n2) – 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
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