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 2.7
- Python 3.6
- Python 3.7
Supported Platforms
- Linux (
manylinux1
-compatible) - macOS
- 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, 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
Which return the indices of the simplified input LineString.
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.1-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 831142d3ebec84e48e4eee9a492b5047e793e1fc904914e57da0c53c04ba8df2 |
|
MD5 | 1b786a9f9968c3ffe1da68b4958515e7 |
|
BLAKE2b-256 | d9081ac4e6d45dc30326b45f59c6c64411cb774e59f6f828a148fd961d4c76a9 |
Hashes for simplification-0.5.1-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fd8d4083c43cb1fe9478fc0e903c166a28cca777af6b3a59e59e7ea462b63f26 |
|
MD5 | 2ceb3a5bca094d386e14649d692a2b6e |
|
BLAKE2b-256 | e802d0325c1b4b98e6a3d13632c35bae7faba582237faeca1124d447b25e2113 |
Hashes for simplification-0.5.1-cp38-cp38-macosx_10_9_x86_64.macosx_10_9_intel.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ad2cdf6b34a4fd31b90699804590e0a3f47cac44ca7c3bd119607a7e144de9e2 |
|
MD5 | 84b2631f51a922e350083ea6adb0ea8c |
|
BLAKE2b-256 | 0ca22710d51504d63723fc18cba825c71d1016cba6cb1db76c19aac96b94ec59 |
Hashes for simplification-0.5.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | da3bc089ac0993f61847512b0c09a363cccb93751888164f1c008fdedfeb1b21 |
|
MD5 | 5db581a77e7c3458c5364c3d00863a21 |
|
BLAKE2b-256 | d1acb995bc90b33bb9b341b7969e2f821f0d9f264e9a1bd66919683da0612892 |
Hashes for simplification-0.5.1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6bb77d26f40332a6155c87df4e1b9eb8908fd607e8055bbca320dfe95335fbab |
|
MD5 | 475e788dbf64edc0012e0fa4da1247cd |
|
BLAKE2b-256 | b2979e78d670fb2831ea9fa1962549b83322bcc5397b723b24eeaadab8583307 |
Hashes for simplification-0.5.1-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2bdeda3de696b6f4bba3785ca3ac101d3193abfa660dc70a9a5aa19aef9d05a0 |
|
MD5 | dd28bdb0a2b36bcac9b9d62fc6196445 |
|
BLAKE2b-256 | ea68f3952e5e46e03e71e9b889fdeffd4ba59b3bf01e77850f899e0ec2738d53 |
Hashes for simplification-0.5.1-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d7411964dcd81070d136959af1ec230db3f2a35bd6989e7e6e2e9bbd8605476e |
|
MD5 | 53664804aa059295f1ab8c4a3134a02e |
|
BLAKE2b-256 | c1914d4f7e2971d3da459275648deed28692d100afc61b0b446b81ce82dceb2a |
Hashes for simplification-0.5.1-cp37-cp37m-macosx_10_9_x86_64.macosx_10_9_intel.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1f0087ad5bbfd3ecd1fda31a459d335afa97315240e3650975d602867d91b0a4 |
|
MD5 | 7107670d9fb1b071bb83748d587ff96f |
|
BLAKE2b-256 | e0446f769923d4f1b430e38c0e3a9150f57b8c6124e63721013001e128c75cd1 |
Hashes for simplification-0.5.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 99bc314ee766cde4aaba4cb5e4c2d3cd779c9b43902f1d73d977334bd70b49c2 |
|
MD5 | 9b82a576e57c9001db659e8592df21bf |
|
BLAKE2b-256 | 45247410415ff1a5951fc728071873524366970c6298012689fe469f88b34d34 |
Hashes for simplification-0.5.1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b58408a580d53182a45964e448ce97429aa1db57faf78b84d6664bd4f35fcff8 |
|
MD5 | a8c6514838671bde59f656a6166c12cd |
|
BLAKE2b-256 | c3ca60ef36158a90adb8be1b2954bcfe2a8490d244214e74e8bb03fda86e742a |
Hashes for simplification-0.5.1-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f0fbe74e2becf0b4b0bdbae4dd1a8008655c833f9bc1c00d92e89bab033ac1d6 |
|
MD5 | f9dcb4c821cb7fcaf4283103b295dfdd |
|
BLAKE2b-256 | 847fa174c2e069a8626b2f4ba2014ae83e594e7c95bcf694c8dac334af604772 |
Hashes for simplification-0.5.1-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 47267a9468714f159e760a67cedd0feddbc15037b91c71a7fa7edcf7e411490a |
|
MD5 | 3529e7f5e780c5aab2254dea97605f80 |
|
BLAKE2b-256 | 2a22a47ad0a80a82a11ddd02eb3d360f62d1a9c38e59a21ed24cb75caa5010c1 |
Hashes for simplification-0.5.1-cp36-cp36m-macosx_10_9_x86_64.macosx_10_9_intel.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4062f9c762cfb5b35e570dc757abd9a2760e25ed6ad184925ac5e8ed01302ec2 |
|
MD5 | 61a7a9bd850b9631037729cd13db30bc |
|
BLAKE2b-256 | 96235abd3f3b659e040e0a3f46d6649b4c591a8ced4e67c9f1ca884a27a6bb3b |
Hashes for simplification-0.5.1-cp27-cp27mu-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 42a3c802ce098c406304c736790f95ca707d0ddc375bd3dd0eadc618dc8b0e87 |
|
MD5 | 12045c43d726c11071a92fb50d424cfc |
|
BLAKE2b-256 | 3fcc52c73a954f2fc384a2865b3e122cc7102c2879c7465cc8728c32b75d6fdd |
Hashes for simplification-0.5.1-cp27-cp27mu-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 22a50345e3ba016101c5a7da5a5716dd94643933fc6cff78daf59fd9352f688e |
|
MD5 | dea3b457f053dcfc2267582e4b1fe77a |
|
BLAKE2b-256 | e0b37484ad75fd6b84f6e49d93caf52b95f4985453150e596e3ea48f8a722a29 |
Hashes for simplification-0.5.1-cp27-cp27m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57cc61bd50dcb3815466091341858e76b63b9f2ef1e036b2b782e2acefe5bce3 |
|
MD5 | d25b6c071685fdfd340a913ec1e0beaa |
|
BLAKE2b-256 | 95569b182a82ea5769ddd95df6abdaddb450b0c6f997a88e9403fe0cb8026897 |
Hashes for simplification-0.5.1-cp27-cp27m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 53b43ccd13fdbe38d8d8a4c0df2fccad303dc0309f0d157b6095da54a3fdf63d |
|
MD5 | 85e0aaaa5d238e549fa90c0effab0eed |
|
BLAKE2b-256 | d013c1f58840311666b702960c7c7c92a59a05ec1491c74e973eae71bacfb2b6 |
Hashes for simplification-0.5.1-cp27-cp27m-macosx_10_9_x86_64.macosx_10_9_intel.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e32625f891c4ad94d2e138d0341cf91babdd8b2ab4e343610e4e5b742cc19f0 |
|
MD5 | 2486b752e35b30d9b1fdacfc6e0d8893 |
|
BLAKE2b-256 | eab3f242b174e230862abfd03beb0382053b510eb5f71c99821f642aab57924c |