RDP

Rust实现Ramer–Douglas–Peucker和Visvalingam-Whyatt线简化算法。

此crate中使用的算法现在已迁移到rust-geo，作为Simplify和SimplifyVW特性。

FFI

共享库公开了一个FFI：https://docs.rs/rdp/latest/rdp/#functions。
一些示例可以在这个Jupyter笔记本中找到。
简化，这是一个使用此共享库的Python包，可在PyPi上找到。

示例实现

Python 2.7 / 3.5 / 3.6实现可在此处找到：ffi.py
运行cargo build --release，然后python ffi.py进行测试。它也可以导入，暴露了simplify_linestring() – 使用坐标列表和精度参数调用它。退出时释放分配的内存。

性能 & 复杂度

在841个点的LineString上，RDP的运行速度比VW快约3.5倍。然而，RDP的最坏情况时间复杂度为O(n^2)——这个实现没有使用凸包加速，参见Hershberger & Snoeyink，1992年的论文——《算法：减少数字化线条或其漫画所需点的数量》——VW的实现使用最小堆，因此最坏情况时间复杂度为O(n log(n))，在特定条件下可能更适合较大的LineString；RDP的平均时间复杂度为O(n log(n))，但像这里看到的LineString（见此处）会显著减慢其速度。您可以通过运行cargo bench来验证这些时间。

许可证

MIT

参考文献

Douglas, D.H.，Peucker, T.K.，1973. 《算法：减少数字化线条或其漫画所需点的数量》. Cartographica: The International Journal for Geographic Information and Geovisualization 10, 112–122. DOI

Ramer, U.，1972. 《迭代过程用于平面曲线的多边形近似》. Computer Graphics and Image Processing 1, 244–256. DOI

Visvalingam, M.，Whyatt, J.D.，1993. 《通过重复消除点进行线条泛化》. The Cartographic Journal 30, 46–51. DOI