### 12 releases

✓ 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

**MIT**and maybe MPL-2.0

145KB

1.5K
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:

, and `simplify_rdp_ffi`

.`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

containing the following fields:`struct`

: a void pointer to a 2D array of double-precision floats:`data``[``[``1.``0``,``2.``0``]``,``[``3.``0``,``4.``0``]``,``[``5.``0``,``6.``0``]``]`

: a`len`

denoting the length of the array (i.e.`size_t`

, above)`3`

- A precision parameter, double_precision

. E.g.`float``1.``0`

The return type is the same

as above, containing the simplified linestring coordinates.`struct`

## Freeing FFI Memory

Callers **must** call

, passing the returned `drop_float_array``(``)`

, in order to free the memory that the shared library has allocated. Failure to do so will result in memory leaks.`struct`

### 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

~1–1.5MB

~23K SLoC