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 (Linux x86_64 and macOS x86_64 + aarch64 only)
- Python 3.8 (Linux x86_64 and macOS x86_64 + aarch64 only)
- Python 3.9 (Linux x86_64 and macOS x86_64 + aarch64 only)
- Python 3.10 (Linux x86_64 and macOS x86_64 + aarch64 only)
Supported Platforms
- Linux (
manylinux
-compatible) x86_64 - macOS Darwin x86_64 and aarch64
- 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.19-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 59566116cadc1a2a1ea2dabf5f3eb9c197e8a6200088fc7bc4ba2517134c3401 |
|
MD5 | 857d7cb07c348a1e3f316f928b261fe6 |
|
BLAKE2b-256 | 83d5f751a125ffd8eda335e6d1190982a4e2ffb193655fa40e6111770196ca4e |
Hashes for simplification-0.5.19-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e5d8ff1db6e2a5141029fc5e504f4ad2a2a083483719b90b8cf1d33357d4d4ac |
|
MD5 | 8c98d3f5cb238364ae203a5ddda93fdc |
|
BLAKE2b-256 | b574f0835216859b67f0461679882f7e306a12af5b8551535c75a872a44c7897 |
Hashes for simplification-0.5.19-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6041bb06df2428726db4ba36b8339443a3f27209edcf74e06d9cdff9c3480c28 |
|
MD5 | ee57bc387da0b74f877313737df0919e |
|
BLAKE2b-256 | bed3b1d6084a9a5ca9e45d4267c2ddba0b4641bd5fe9999d23c0e4ca08c59a74 |
Hashes for simplification-0.5.19-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d21f87e04721f89a99d8e7a165d2da5f3a17a1fb72d5ff3e5ee941086c6f754b |
|
MD5 | 7b3e2ac41ca15782d50300beccff46b1 |
|
BLAKE2b-256 | 3201586076e1066dc87ae557557302fb724990d809c3f5392e3bfe5325616a34 |
Hashes for simplification-0.5.19-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79eaf9a4ee9fcc76f27119d69b5c1931f13f6baf5214c98b40b13375581ab4c9 |
|
MD5 | 43d66caddd36b357ad08a2ceb25804f8 |
|
BLAKE2b-256 | eb05220a285de0b5bf59b6b88de2e064916f0b78dcacd0f347e67b5b2d91ed46 |
Hashes for simplification-0.5.19-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 51be9da8c5496ca207157e2e0f2255318681c72656b970ff79205aed51bb96f7 |
|
MD5 | d8ed6d2e4779ae35e8df2a0276b2fcf3 |
|
BLAKE2b-256 | 787b02ac09b6a74182591fc6d2a6ae517c1c53e4255d6c9f6765840226b48f5f |
Hashes for simplification-0.5.19-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9ec114ef3abfd689f086cf601454e99f434644e7a7b788a11aeb6be5c4bf9cc8 |
|
MD5 | 62ad9d2a723ce69c53cea334f7c0504d |
|
BLAKE2b-256 | 52663e702a7094ad910b16d9983f60b9eabe125205d2278be3e7a586172a1303 |
Hashes for simplification-0.5.19-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 86a455451caad7a729c123475af7b800cd7de0b1a1ce6073bf11a4f7038217e3 |
|
MD5 | f5e73ab0c535fea07c764b42d51bd2ab |
|
BLAKE2b-256 | f6408b0fefca9120a3b1c4579721cd0638cb2675b8331ca95a2c1f9685c4ea7c |
Hashes for simplification-0.5.19-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 24312fc74bbd96f6159016a23ebc07e19fc77f73faf146fe262730c38738bb1b |
|
MD5 | 6840d0882e90c77ce86f6cf3ba88ef5d |
|
BLAKE2b-256 | a8c26592c4fedf6bdb31eb989294f8ab233bb70296cc0258dc8acd2f1e2aee81 |
Hashes for simplification-0.5.19-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ae06bcf8b85d143df2554409c0faec86e36d5abecff404516300c4cb3c07eff |
|
MD5 | 82a69bbafbf7904ce77ec4cb38dc627e |
|
BLAKE2b-256 | 7ed219b2c4d1b812aa50201938f37350a031672f940ed0e5ec406ce5820fd312 |
Hashes for simplification-0.5.19-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 81d5b7c2ed12475798424d75da26b770b1e87721784107889b4695c8d8a1f548 |
|
MD5 | 26a06afeb46b579a5a2c96bf6b80ef4c |
|
BLAKE2b-256 | 9ad3327440bc50b970033b91fab21302daecc6b2b4713665032804dd2b6691dd |