Fast linestring simplification using RDP or Visvalingam-Whyatt and a Rust binary
Project description
Simplification
Simplify a LineString using the Ramer–Douglas–Peucker or Visvalingam-Whyatt algorithms
Installation
pip install simplification
Please use a recent (>= 8.1.2) version of pip
.
Supported Python Versions
- Python 3.7
- Python 3.8
- Python 3.8 (Linux and macOS Darwin only)
- Python 3.9 (Linux and macOS Darwin only)
- Python 3.10 (Linux and macOS Darwin only)
Supported Platforms
- Linux (
manylinux1
-compatible) - macOS Darwin
- Windows 32-bit / 64-bit
Usage
import numpy as np
from 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
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.
But I only want the simplified Indices
simplification
now has:
cutil.simplify_coords_idx
cutil.simplify_coords_vw_idx
The 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]
But I need to ensure that the resulting geometries are valid
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.
But I Want to Simplify Polylines
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]
How it Works
FFI and a Rust binary
Is It Fast
I should think so.
What does that mean
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.
Disclaimer
All benchmarks are subjective, and pathological input will greatly increase processing time. Error-checking is non-existent at this point.
License
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for simplification-0.5.15-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 978323c3c41a4d225b9d9c55e2198381e9cee5c12d4309e96bfa39fe9b2ef975 |
|
MD5 | 636db1f37bef64cc35c1eba03678d435 |
|
BLAKE2b-256 | 38706554a1c45483ebeb34004d902f49a3ce885401a4c9846a37aeb9b33586f0 |
Hashes for simplification-0.5.15-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 78e6b9abe708f3f77236b966618987149efa406f168db7c931a4d6a8983a307b |
|
MD5 | 01c35102c9a85f3ca68972ef93743b1a |
|
BLAKE2b-256 | bb47df53557db7b4a747c9f7a90aaacbd822eee7c1031d4db78916832cff7caa |
Hashes for simplification-0.5.15-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9e6110c06af3c81b8d780455faead37642d75de3f8dcaee35ce5f81521055de |
|
MD5 | b1dfd277e57d2ba2d2ebafc974bcffe0 |
|
BLAKE2b-256 | 2dcee4e0068f77ea8d85f649a6cc36d8a2953d884076609c31f5a641bae81f89 |
Hashes for simplification-0.5.15-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 43050cc37393f96679412a7a54044078a5fae04eb496284e57fd01c4e776c806 |
|
MD5 | 40f38454ca66c26ded2582a8c9cb7430 |
|
BLAKE2b-256 | b6015b59b310cdffd63d7aa3a830f92b1771256036c358b7f57dbc098865550e |
Hashes for simplification-0.5.15-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e5348763ca0e58b8829eaac63c58df0abfa8d2e6761cf976a2a64d43aab75375 |
|
MD5 | c67261d7daf8eff834ec063087f88b0b |
|
BLAKE2b-256 | dac4a907466ba3965b40653e8e3c709c5bed6fee0bdd5c4fdd1c483a25940595 |
Hashes for simplification-0.5.15-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b1fb3cbd962a09f1138e8f5ef75255f6a088c616c20095b98e699f76b3aa770 |
|
MD5 | b92ba7b6c655bc7699b65762c47294ea |
|
BLAKE2b-256 | c5e913cee3c485216dabc7481fa0f126f999b0ccbff245ae3a2cae242049e38e |
Hashes for simplification-0.5.15-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4fd4cf6ff7f32a340d19082fc74d459d332d8fb4c609a182a89c696d121dc955 |
|
MD5 | b85b68582c4294ff8c438d779717d1d4 |
|
BLAKE2b-256 | c75a4761aaef63947c1981d16b883754f171439dac1511a688d7e99a9ca84f57 |
Hashes for simplification-0.5.15-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79825a73165d1b32184693e48e03072cc9f66d3805df0229e1dbcd6db04b890c |
|
MD5 | 171a0e69f01745a23997e3dad5f7b74b |
|
BLAKE2b-256 | feb3b9a056c33f736bcd1ef9bd2a9b5f70f5f2fe1c15321a23699dfc0f0d529e |
Hashes for simplification-0.5.15-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e4123abad91cfde522d909dfa8f72b48e59ca7b52156c9dbcfecc5d3fa7c82df |
|
MD5 | a25f337d118782c7a74ef9546e51c569 |
|
BLAKE2b-256 | 93e4a9666273695157a4529ee818a2a934207dab8f92c7df7c77a63bcf876be6 |
Hashes for simplification-0.5.15-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a55abdcd8ebcb525741acd75ec43b9e01de76c5aae8184602c0cfad052f3fd59 |
|
MD5 | 2f903aa7c33461358bcc137ae435952f |
|
BLAKE2b-256 | 0c6d556bff1f4c1515139060346d442592046852a2ee9fdff2aa4df19efbc748 |
Hashes for simplification-0.5.15-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a7bde404059d3155a2702c86e6551311725e37a4572adc099ab6ab6f1fbf4f28 |
|
MD5 | cb03a11ab4ebc2071ef969b7433c75f8 |
|
BLAKE2b-256 | 41f7a7579a689478f247f4cfefc82e2153f3490578ea72ff613606a048996edf |