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
- Python 3.8 (Linux and macOS only)
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
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.2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 904a33d1d39f509af1f91961b09367e1e34504caa2ff50672bb7af08b97e2c11 |
|
MD5 | 84e184b36ff3360dd3e80dcedb418f07 |
|
BLAKE2b-256 | 29757b81f734143984340aacfec96e11ce6e3e094d0cdee6c3d239398e373b73 |
Hashes for simplification-0.5.2-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | af908013117cda4cc13f1fac6a233314f6c484e2c2a5182f82d74a4447d8da17 |
|
MD5 | a65784cacda3b9148dcd3902ca4591e2 |
|
BLAKE2b-256 | 3ad568ad5c8e0e3a0e725b0ad9fc9649e63105da0bc62ab9001d6582a030fe34 |
Hashes for simplification-0.5.2-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cdd4ca39ca35c23749a8e85623ed4aff8532a1e594faf584ad590406736cb813 |
|
MD5 | 754c34541f05d5cf19c92cbb344431b8 |
|
BLAKE2b-256 | de28042488083b9d4ec58ebc5b5000fbb5b85eee4ce5cccf82612f45f7ca5a24 |
Hashes for simplification-0.5.2-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 | f36d342b3cd01e9b0895ae15ed77b3f20147b619f52e23b358cd06095e5f8217 |
|
MD5 | afb59dddef7b5df3a317ad99cc562ca1 |
|
BLAKE2b-256 | 8d63fa13df8633fd8238cd30f8e7835147b4b2805466648d2dc08b0e9111519e |
Hashes for simplification-0.5.2-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d20bfb07d08e73e790e799b4faff89b821a784a798abe243ac7eee8e133dfb2c |
|
MD5 | 17f2a9d748a596aee8ad65c65fbb50c5 |
|
BLAKE2b-256 | 8269173acbeb9784ee391c596ea47956bc55b6b4e933d8e56f736caf2a2ad88f |
Hashes for simplification-0.5.2-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6439fe3bb2598ed76fb7046391ea8d41db324f37bbe6fcf913c0aa2257853947 |
|
MD5 | 392a751364fb3d76350ce21ae8839e06 |
|
BLAKE2b-256 | 6af9da789a4a3139cc1e868e681ef56c0c2fa58ca4804aff9a824a4726329fd2 |
Hashes for simplification-0.5.2-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 943286c7a60a1cb576efc2f94656a6f9f69321b17431d797f84b9335e685d5cf |
|
MD5 | 4384a017103e42474ea8736c82ff4895 |
|
BLAKE2b-256 | 96111a2f363b2a9cfec795bb3edf34f5a6b0b910ee6b26a62ff4bc863d8316b9 |
Hashes for simplification-0.5.2-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b5b49a64ddd28d89533a266c55161d736e0555b93cbabd0dfd1196cc5f40d54 |
|
MD5 | 957cb4ad66de1d002f38a035d2b36dbe |
|
BLAKE2b-256 | 17a7b8c46c566b307d24f6db27f926be909df3eea4d15e852940e1fad34edaf2 |
Hashes for simplification-0.5.2-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 | 83ff08d83efc2492b7ee84f4879fcb5efa7a660718439413396e8d3903979fbb |
|
MD5 | 2253ce5e613a2761c50bb7cf70f3954a |
|
BLAKE2b-256 | cccd9be6d2ec0305812685e196afd936e06ababed0624f8ae7dea9d06c352355 |
Hashes for simplification-0.5.2-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7013299f6c55b2e0a4dcd431a5a53f2a8e0e613453ca48b66898697e984b4dc8 |
|
MD5 | 311aebbab50d4a2548eea9a88df97b77 |
|
BLAKE2b-256 | fdf84fbe715612738f03da7434ecfbf0f3a0e31959b96a9e0091b04666bb4be9 |
Hashes for simplification-0.5.2-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e929811ed466f2130b75f793c2cd85eb158ecfd8a53f29aaf71443eefc5ddfc |
|
MD5 | 6262d7353f9088918a00534e688af8b2 |
|
BLAKE2b-256 | 156efddea43615690acfc1cfde12c8ddb0f1fd408bc49617ce0195e2c8f04a43 |
Hashes for simplification-0.5.2-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 975c0e89eb7b5ab1bf9cfe4f2914f917c20b629e5627ae1de169cb12e16b1732 |
|
MD5 | 1886626d186864d67d92861ae864bf58 |
|
BLAKE2b-256 | cc09aafdce582ed4b1a025bf876d2cbb70438a1fc11c6fde95adb00c21ae98d4 |
Hashes for simplification-0.5.2-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 | ea752e17539f729ff000390b661ab8b44d92be3d8628cac337de3e4612b5c26f |
|
MD5 | 8483f7cd97d341f10e9a707200be1dcd |
|
BLAKE2b-256 | 17ae77e27411aec0e1d205b8c3fb4bd0b355881f494f6fe137a70a2d3c668e11 |
Hashes for simplification-0.5.2-cp27-cp27mu-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c6ba946478314a2f334eb19c057f2935704bab7b830c974551d746c0c2018c8d |
|
MD5 | 99583543b63ba758f79a6dd5f194e866 |
|
BLAKE2b-256 | ff1e52fc2d1536d0d6cd0e3108a539e15986644d099388077019cc7cd92f93fa |
Hashes for simplification-0.5.2-cp27-cp27mu-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eabc6bce14d0a9a5b5ccded3e80103f6226a93a8aa974a8a9a719bb47dfb6d30 |
|
MD5 | f46c6dfced6a58d57d0cf42bf06629cd |
|
BLAKE2b-256 | 2019507264c83333e06c513d3a357ab3a5fed3aa682eb5ecf222840af41fe66a |
Hashes for simplification-0.5.2-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 | 175e3d507f89f2598494fdeafc07c33d6e13766f37cfeb782488cd6b4771b9c4 |
|
MD5 | 55fd0f96a2c6f8951f7d9d0b041f8d08 |
|
BLAKE2b-256 | 5d521af3220c4ded9f6526bad125e1882c8511b46d3e7615d5b1e55d4729ee68 |