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 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_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.13-cp39-cp39-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 30cb7628db04bd5132bafc9790a3e63db5883eafbd25aeca8ca3f9ecef214ed2 |
|
MD5 | f393da616062b14804e32a8e1973416c |
|
BLAKE2b-256 | ee3649edb2b9dda999302fd1e81a369e9530a434007b6b03ae2c55504a0f0e04 |
Hashes for simplification-0.5.13-cp39-cp39-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ec7e0f738a9b0c3aa403d674385dcc8efe7e7d83fcc0fcac67cb0629a0db58a0 |
|
MD5 | ec380df8e925a5882483a91ee483a4b4 |
|
BLAKE2b-256 | 1ef7ac8b79c81d1acfb7cbe47c2f711af6306b74f4a333bf17181f4c1ebf5921 |
Hashes for simplification-0.5.13-cp39-cp39-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | de5ac04ede41f760ca1288c43a888a1ed274f3e3ee434d9a6ebe2497642a7280 |
|
MD5 | f3075f020aa89a13fc6e860753198e30 |
|
BLAKE2b-256 | a16f9ef1352d2d450a0e4e233bbda7a975025711f3ba50ef0c4f311c5e6405f8 |
Hashes for simplification-0.5.13-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b6fe341806bf258b701a06d63337d36979ac92cc0a935fd4b553c71648ed170b |
|
MD5 | b73a008b16e19e69526be7e4f4a8d693 |
|
BLAKE2b-256 | 4ef3bb7c22188f7ead0930a07ca7cea8d2ae7608f0a8d1c4c0af7fa4a728d552 |
Hashes for simplification-0.5.13-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e9ea2f003d03f9115a067dc59719292dca9cc68bf2ed6e08251c55631c01db75 |
|
MD5 | 3799cd05495d07d2d728c696cd91c9ac |
|
BLAKE2b-256 | a5d35f36a86439a628771825f9642746e2d5bb11546f02f6afc10b409fedd3a0 |
Hashes for simplification-0.5.13-cp38-cp38-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a12f885d5f3fa62cc26b4df7112ef1524fc31f7265c66487cafef4a188b4195f |
|
MD5 | 4dec2553f4fc7621791ab6317c853e92 |
|
BLAKE2b-256 | a77c1bd88b4c5b545e5e5c9293e0768ede6f8ade49fe1a5867fc12835608976a |
Hashes for simplification-0.5.13-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f9a1d07d85cf0e43879af2df4283b39596675c3a58c14115e4e59ba91bcf98a |
|
MD5 | b77049108368e86e497619340fc2e8fd |
|
BLAKE2b-256 | 5af07988f2104d8004ac5990c2fb8f0baa2a29f537c88ac7a24daf68915e5ec6 |
Hashes for simplification-0.5.13-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 583f590fd7dd00d8b28b251bd45c7e27e08a8de806cd7fc58a92ea3322c5283b |
|
MD5 | 5642ef0c0d38f1fab3fb2a5ad44861db |
|
BLAKE2b-256 | 7ed062afbaf769743740c2185049c79744916bd5a9f4e7b7714aef2ba6ec341f |
Hashes for simplification-0.5.13-cp37-cp37m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ff0e42198764fad316c13c420c6447963865655eb7706d40db95de866984267e |
|
MD5 | 454e4068cbb2ed30f0028c7dabb7372d |
|
BLAKE2b-256 | bd53f5b67c457b8d5c9ae98c0225e12485560c5f0ac1962e9687b62258b521a2 |