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_vw, 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 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.4.4-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 03687ccbe7d633e279f5926a9bf4b39f4fc75648479e8f42090a682c6eb41460 |
|
MD5 | b414b32007827077d4771f0caaa44521 |
|
BLAKE2b-256 | 8c2992b448ebce21abbc7f632e143439b9e9636d52d04ab1cc68f11f86cb5dd8 |
Hashes for simplification-0.4.4-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a98c822ef4dd153d2793a177273ca649df3f89704dd47a6b1400397828ed8b28 |
|
MD5 | 5977146deed279a1e9885e79d7ab15e8 |
|
BLAKE2b-256 | 10aeeaaf5a344d22a289259477e0ea77db3d9bbacec89d1684bdc47b979de641 |
Hashes for simplification-0.4.4-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 | bb741fec1991c474b3d5373c542bc4053c6cd885e1ecd0b0d136bb3e7f4fad20 |
|
MD5 | 51d7c04bb6d06ac68a9650da80975d3c |
|
BLAKE2b-256 | 69da7e061c22bed5eba5c2d0df595d050eb1c44b01baaa3ce49aadd02c2dcf02 |
Hashes for simplification-0.4.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a2d755dcfb76faa7268b8c6629efc417d60cd23037c9c11d38b1a22537d01f5 |
|
MD5 | 50dfe18b2a8eae86193dfb2bffeb9614 |
|
BLAKE2b-256 | d4133a812a2958e2e141e318e487366f01d4c488aa2b0748acaacf15fbda2905 |
Hashes for simplification-0.4.4-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5a75f13a3bdcef816486786a0409aeb8463635a41d9bc89dba7429c9a66038c |
|
MD5 | 5d01a038f8fb70d87208fa10bc730c82 |
|
BLAKE2b-256 | e2f7f1467dbf14266b3b0f82d8d91c20d540413602bf069508f0f7b7ee2d0126 |
Hashes for simplification-0.4.4-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1e383178aa5d88e7e4b7312376c1ecfb5c7677aa4b291d58fff05eafa3654b1f |
|
MD5 | 500cddc4260b4492442d89aa8a745e09 |
|
BLAKE2b-256 | 2993c82941eb6f8fcb152625c42c335263e66d41bfd45e6940a92ecdebcb8909 |
Hashes for simplification-0.4.4-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 77a94168c298ee4b5ca5c307ad192d16f3da251c547073f941af8aaeb5934be3 |
|
MD5 | 81a4a66c4cf2779fa7c59a9eb10d08c0 |
|
BLAKE2b-256 | 77135fc97e5ce7512c7b071cbb14f9023e15f381cc97fa2b4ed856d8dd0e3de7 |
Hashes for simplification-0.4.4-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 | c9ed3f6921680170e57f6f31cd01fd2da49fb20fed346efaaa4e5332a1c4fcc9 |
|
MD5 | 5d3e8905eb17ad4540cfcd345c8e7769 |
|
BLAKE2b-256 | f57432c4520677208c052aaeb2bfec93b8570fba3c2ab6e152865beb5b9b55d0 |
Hashes for simplification-0.4.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f078d1c5c31aab393ffa2557071f2adae3797c7fa1b45c6e6ed88a2cfd901fa |
|
MD5 | f7b50199a3aa409e106c35c00f8354d0 |
|
BLAKE2b-256 | 890c2320cf2b1a3ca2b256e33fd1b309bd7fb06430ca3fe65d35070735fd94f5 |
Hashes for simplification-0.4.4-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 48c5426785c1bbf7cd8a63efa8b48479ff7ee1be3c488318d24bf481008910a9 |
|
MD5 | 0f445f95e04a457c44059feb2e482cee |
|
BLAKE2b-256 | 0c2eddf328e8285eb8eabe8d85be661c1c8e704e19be742f7f50aa616ccf152e |
Hashes for simplification-0.4.4-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 306e6b25b9f448cf69e12076391cce083ac1926fd6e6d3e6f4ee560c32050173 |
|
MD5 | 3b232685cb83f57964ec5970126961b0 |
|
BLAKE2b-256 | 404679c5f70dce457416b1128a4c6b6bd9098592063d5040ba2b9fbeda32dbc7 |
Hashes for simplification-0.4.4-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 08b84174c35573bd129128a166af8271bed09a62f149a701cbe47db2c6399a76 |
|
MD5 | 76be767929a13e6d9a58679cf2ff5b79 |
|
BLAKE2b-256 | e9f7a1e62b88e4823b082ee9d501e3b4a00f11e95bfd6fdd2f126727e9c834e6 |
Hashes for simplification-0.4.4-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 | 7f529c0bbcc0e66abf728f9595f805527aa38937171bb738ce7b8dcad28b5b58 |
|
MD5 | 5f6e71615625e957d52e197e60516321 |
|
BLAKE2b-256 | ee7a66aed441f40c90be94438953b820c9309c9b99dbff1636e6e706d86c51a4 |
Hashes for simplification-0.4.4-cp27-cp27mu-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 838f2ae8e7ee131406d51ab7c7875c03fc2c5ed26ebfe96a21366545507e1b61 |
|
MD5 | 46ed6d7814babafdf8d7bd8510edf507 |
|
BLAKE2b-256 | e9c7d25f1715c30336606f98b5e4b0c3cddce47e8dc994d3a2b9cba661239e62 |
Hashes for simplification-0.4.4-cp27-cp27mu-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1f2b4ea192aa15d4401fadefec03fd576dea793c2359b6d2c84aca9221dc995d |
|
MD5 | 12b2a3337cb9584f83d4429f8496ce65 |
|
BLAKE2b-256 | e6431f9344f1932907ff2a0d79f809c2fb23d4da75c06a6bc6376cfc30591f5f |
Hashes for simplification-0.4.4-cp27-cp27m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b4949a7a47bb21d9ab631e8ecfbacb01b957f494b9e387e8e8e3f808959b4ef |
|
MD5 | 60da361c2fd970a47556e5232505536c |
|
BLAKE2b-256 | d93d871e37be25f5ff4a0a59f83235d760f98330839e4b207c2521772bb4a76f |
Hashes for simplification-0.4.4-cp27-cp27m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e36d5b5c912cb11fb4a9228ec5ed793b6f45bdba532e5f8383a4fae4635cfca8 |
|
MD5 | e9f8672a414c5b3277603a8e604809ac |
|
BLAKE2b-256 | f2699faf0511a16567ddd021f239db277f00c4f9d71dc0dd70440a07f0cadd34 |
Hashes for simplification-0.4.4-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 | ad2f3eb420fb9c8211748399ce72e35f5ae0d1fe10e148b3d2a41df1ea48df45 |
|
MD5 | 6b665748ed17c9a05a0c950bd832d164 |
|
BLAKE2b-256 | 5c99ed3bc92a7c36daabbdfef54a10f84d642d36f098e66abc0cf03c33657637 |