Fast linestring simplification using RDP or Visvalingam-Whyatt and a Rust binary
Simplify a LineString using the Ramer–Douglas–Peucker or Visvalingam-Whyatt algorithms
uv add simplification OR
pip install simplification OR
conda install conda-forge::simplification
librdp from https://github.com/urschrei/rdp/releases, and it's in the src/simplification subdirpip install -e .[test] --use-pep517pytest .Simplification supports all currently supported Python versions.
manylinux-compatible) x86_64 and aarch64from simplification.cutil import (
simplify_coords,
simplify_coords_idx,
simplify_coords_vw,
simplify_coords_vw_idx,
simplify_coords_vwp,
)
# Using Ramer–Douglas–Peucker
coords = [
[0.0, 0.0],
[5.0, 4.0],
[11.0, 5.5],
[17.3, 3.2],
[27.8, 0.1]
]
# For RDP, Try an epsilon of 1.0 to start with. Other sensible values include 0.01, 0.001
simplified = simplify_coords(coords, 1.0)
# simplified is [[0.0, 0.0], [5.0, 4.0], [11.0, 5.5], [27.8, 0.1]]
# Using Visvalingam-Whyatt
# You can also pass numpy arrays, in which case you'll get numpy arrays back
import numpy as np
coords_vw = np.array([
[5.0, 2.0],
[3.0, 8.0],
[6.0, 20.0],
[7.0, 25.0],
[10.0, 10.0]
])
simplified_vw = simplify_coords_vw(coords_vw, 30.0)
# simplified_vw is [[5.0, 2.0], [7.0, 25.0], [10.0, 10.0]]
Passing empty and/or 1-element lists will return them unaltered.
simplification now has:
cutil.simplify_coords_idxcutil.simplify_coords_vw_idxThe values returned by these functions are the retained indices. In order to use them as e.g. a masked array in Numpy, something like the following will work:
import numpy as np
from simplification.cutil import simplify_coords_idx
# assume an array of coordinates: orig
simplified = simplify_coords_idx(orig, 1.0)
# build new geometry using only retained coordinates
orig_simplified = orig[simplified]
You can use the topology-preserving variant of VW for this: simplify_coords_vwp. It's slower, but has a far greater likelihood of producing a valid geometry.
No problem; Decode them to LineStrings first.
# pip install pypolyline before you do this
from pypolyline.cutil import decode_polyline
# an iterable of Google-encoded Polylines, so precision is 5. For OSRM &c., it's 6
decoded = (decode_polyline(line, 5) for line in polylines)
simplified = [simplify_coords(line, 1.0) for line in decoded]
FFI and a Rust binary
I should think so.
Using numpy arrays for input and output, the library can be reasonably expected to process around 2500 1000-point LineStrings per second on a Core i7 or equivalent, for a 98%+ reduction in size.
A larger LineString, containing 200k+ points can be reduced to around 3k points (98.5%+) in around 50ms using RDP.
This is based on a test harness available here.
All benchmarks are subjective, and pathological input will greatly increase processing time. Error-checking is non-existent at this point.
SimplificationIf Simplification has been significant in your research, and you would like to acknowledge the project in your academic publication, we suggest citing it as follows (example in APA style, 7th edition):
Hügel, S. (2021). Simplification (Version X.Y.Z) [Computer software]. https://doi.org/10.5281/zenodo.5774852
In Bibtex format:
@software{Hugel_Simplification_2021,
author = {Hügel, Stephan},
doi = {10.5281/zenodo.5774852},
license = {MIT},
month = {12},
title = {{Simplification}},
url = {https://github.com/urschrei/simplification},
version = {X.Y.Z},
year = {2021}
}
Version 1.0.0
This license gives everyone as much permission to work with this software as possible, while protecting contributors from liability.
In order to receive this license, you must agree to its rules. The rules of this license are both obligations under that agreement and conditions to your license. You must not do anything with this software that triggers a rule that you cannot or will not follow.
Each contributor licenses you to do everything with this software that would otherwise infringe that contributor's copyright in it.
You must ensure that everyone who gets a copy of any part of this software from you, with or without changes, also gets the text of this license or a link to https://blueoakcouncil.org/license/1.0.0.
If anyone notifies you in writing that you have not complied with Notices, you can keep your license by taking all practical steps to comply within 30 days after the notice. If you do not do so, your license ends immediately.
Each contributor licenses you to do everything with this software that would otherwise infringe any patent claims they can license or become able to license.
No contributor can revoke this license.
As far as the law allows, this software comes as is, without any warranty or condition, and no contributor will be liable to anyone for any damages related to this software or this license, under any kind of legal claim.
FAQs
Fast linestring simplification using RDP or Visvalingam-Whyatt and a Rust binary
We found that simplification demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Research
The Socket Research Team breaks down a malicious wrapper package that uses obfuscation to harvest credentials and exfiltrate sensitive data.
Research
Security News
Attackers used a malicious npm package typosquatting a popular ESLint plugin to steal sensitive data, execute commands, and exploit developer systems.
Security News
The Ultralytics' PyPI Package was compromised four times in one weekend through GitHub Actions cache poisoning and failure to rotate previously compromised API tokens.