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.7-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 84e37404e88af38f32df142b2e64d7c7246231717744572df28c1a75bfa8bc06 |
|
MD5 | 0744bf63af7fd2ac65096e8d4986f369 |
|
BLAKE2b-256 | 85c90aedb1f13a2ff5d3a78d9c5c9c36272e182530c4f9e1efd6bc480c144c29 |
Hashes for simplification-0.5.7-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 15e32cc92cd64904f3fe2b1d8c53ae3b289440b4cd216816f36e617d8b33b63c |
|
MD5 | 0884c5823281dbc74a50dbca8bca1fc4 |
|
BLAKE2b-256 | 41b06d648bf4a84abfaf53de3b1da4424c3fbcddf1bf1fc09064be59f28aaa2d |
Hashes for simplification-0.5.7-cp38-cp38-macosx_10_14_x86_64.macosx_10_9_intel.macosx_10_9_x86_64.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 24c9e2fef9bfa00e1e84e3a6432c0c0b8f83092afaf42732b764fc0b3fef9c78 |
|
MD5 | 47adc024cbc00c6e5b513d885a721c07 |
|
BLAKE2b-256 | ab6d8b777db454a913947f9fd782c4ee2ae9442a6ddde1bdda9b5d14eaf515d8 |
Hashes for simplification-0.5.7-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 537ae7ef986828f1b36f59eb3bb73abde890af0d670c3d8bb02a453a8050b474 |
|
MD5 | 063707ac1eecec8163ec3bf64b7bc278 |
|
BLAKE2b-256 | ca916e586e89fd08b2c0009f68b6716252e6ed4f85e88cc4eb03c7623df2c654 |
Hashes for simplification-0.5.7-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0927b98f4a8c8a2fa84436704afada97018af7cc3ca532fc79bd0b1ebba79b96 |
|
MD5 | ef78e7cd747ae4b852f6f4f216def886 |
|
BLAKE2b-256 | 027abb8ed7a422ddb54510ca77f7dd855e654c558cd633de0beb7db0b7ee913e |
Hashes for simplification-0.5.7-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dbde1492b6d9f96ce16a0bc7a0ad24f21f33497cf42be6ea0650b8745de172c6 |
|
MD5 | 836cb93c52ca5746caf8accb94831bb0 |
|
BLAKE2b-256 | b0193529ffbba799e86b04636e1a88a6661ba836af580f737b4698dbbe0f2e0e |
Hashes for simplification-0.5.7-cp37-cp37m-macosx_10_14_x86_64.macosx_10_9_intel.macosx_10_9_x86_64.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f69ceeab530ebea049f9d32c208381cbfce54d76d2a0806ac0961eea02130f93 |
|
MD5 | 559c06357bb9f89fcea25354ab1f7937 |
|
BLAKE2b-256 | f678931db0d6c05e556559b8d96a6a527f16f70552503570c50e4dc2d48da650 |
Hashes for simplification-0.5.7-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e2d3c13c73a8e7531b33ed8bd87b71f04ea46e8606e0679e4e9dd136ffa50b35 |
|
MD5 | bdb56d52285075e00a3aeb0c102137ab |
|
BLAKE2b-256 | 5aa52b0c1b0f71a7b9d990d61d4fddca8647ef4e41a3ed3054ab775d0693994e |
Hashes for simplification-0.5.7-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0a8d2590d2dbc016cabcb6a91e63846055ad7540bda81423312479a16bb546a |
|
MD5 | d35239772db0dc639ed39e7b8bfe8428 |
|
BLAKE2b-256 | 47c5e0183d974176dbdc40b6849f4665abbd591a40551dd73bd13071f4b57962 |
Hashes for simplification-0.5.7-cp36-cp36m-macosx_10_14_x86_64.macosx_10_9_intel.macosx_10_9_x86_64.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 255dd4fe36f70c8ccbd5880106096027203373b4d7728c3d586c6bdf90a7008d |
|
MD5 | 8a46a54bf4f727949002cb3d0f3f3a7a |
|
BLAKE2b-256 | 223be7563f66069b4752e54367446a87077cb028c8669ebe019f7f838bb18183 |
Hashes for simplification-0.5.7-cp27-cp27mu-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | acbee23ba01f3cc99f70303aa03c4f013bb1fe7ddeb7f6ba9feeb9c69ea0ba14 |
|
MD5 | 93d47488c60504367a1bf0bb33df5e0a |
|
BLAKE2b-256 | fa185a9090510f6a865acf93149b2c210647053388fc4b45bbf3f3f581bc450b |
Hashes for simplification-0.5.7-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 | c647cad156a722a273bae297207eaa341a6563c5cba8dd0ac20adc761c526db9 |
|
MD5 | eb03948963910c2d02531f8622c31d04 |
|
BLAKE2b-256 | 30274a7f7075d7445aa7f3aff965efd070861c60acf5cab349061942ee57a0cd |