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.18-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2efc2d37df13528db3af9269a65c7909b15b122d015bc058c9a3253135a4203b |
|
MD5 | 379ca1dd088aa092782cfbf48ebd459e |
|
BLAKE2b-256 | f540306f57b35eea1dd86231ef6eb180dc8163dce4c10bbeeed9f77fa4a2b990 |
Hashes for simplification-0.5.18-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 98c1a1f809ec176825a68ceba5547dbc4afc679b31f37999c4505622a0bcfff5 |
|
MD5 | bff6b4090277e57db2125a70f9a9bda5 |
|
BLAKE2b-256 | 9b5497f5612621ca7197523a53df324216bc0614b31f13ccb9d4082192ca6cc3 |
Hashes for simplification-0.5.18-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d1adf85c1a3cdf66d82b6f0bd66ec77075c6578336b57efbd6eb273cda8649c8 |
|
MD5 | 03076e7331b768a8f1a3c197c2e612f5 |
|
BLAKE2b-256 | e2295d565e2d1322a4b76ce0c98adf3e7caea5d02f22aab473caf5958461fef5 |
Hashes for simplification-0.5.18-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e2447f493b2171d3a76c7dcb7f89a62ffca6b20bea6212e0d3510aba2f9c110 |
|
MD5 | e24091b20f323e561b4864e44980a73f |
|
BLAKE2b-256 | e86d142e103a597056dca4bc40ed46ceb69a26b28f308088c27633762a64276a |
Hashes for simplification-0.5.18-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 97a64dfcefea4798b9da33e6a56fd28e2978baf03220cddff94f89268c804df1 |
|
MD5 | 791db8a6558e7b9a6969ccc6e10f3046 |
|
BLAKE2b-256 | 10c960eba023c4282bacd348f88ec701ed9e89515287f7de25b7a2ce19e87857 |
Hashes for simplification-0.5.18-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 63915d5b0d61ccbe613033f495a6c51e334b323baa4dfd802055fb6bf0a7027f |
|
MD5 | 359d6b218228f97680e8a9feff3bd107 |
|
BLAKE2b-256 | 053e839fb5ca8477934b38575645735181b5c9d9e79f5fa8477cbce31bfd2817 |
Hashes for simplification-0.5.18-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4e0319deb03f73f61c2533a347ae6f6cde22ad178253303650ca22b30d82e228 |
|
MD5 | 1a1420e89a3510ca9de1df03d44fd6d8 |
|
BLAKE2b-256 | 227170d42a6d409d2e21b4154fe3b48d05e7671f1c8e4c49c78940125b5e2b29 |
Hashes for simplification-0.5.18-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3a1a8da47907bfa694d72461b9d82c8cefc0ef530661aad04935cd3a0c6869d |
|
MD5 | 9e2682f513f530d68828ed6f92ff595c |
|
BLAKE2b-256 | 243a94479494cacd73feed003f5a84cd5ecc847d460716af644a398338ff43e7 |
Hashes for simplification-0.5.18-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4d8a3d6c0a260fc79a49eaf5a8f42aa7119eee317e074c314919f666925c5b7 |
|
MD5 | 9a6e0e6d5c13110253e8e85fce918462 |
|
BLAKE2b-256 | 25a5fdb7960cf184170bd790c521730b90633cd94677b893310ea430d66ee260 |
Hashes for simplification-0.5.18-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e7b156ec18a4bdfd36901617d2a9e1243e6f9ed77be98022ade2a7c425f7bccb |
|
MD5 | 325876a3eac77f44134c83c9dd3d4694 |
|
BLAKE2b-256 | 498a2ec34e0cd8ff4d15f62b7e2fdb8e6f87f62f75fb586f8c63cbbec8a44f25 |
Hashes for simplification-0.5.18-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ca8bbfd2d24f2f14139704c722dc19ee406ab5c2bf007d46ba203394d00db9d7 |
|
MD5 | 748bb3e65f720a8590f1e9b5b5ccb877 |
|
BLAKE2b-256 | 9f16d6a974a1d6dbb86d238bb1acd495966222bbbe3606dd141df5f7788db22f |