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.17-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 614d29ca764b105784fd0f20e2b853515d50ec353fc2432c90d113d6f14edc68 |
|
MD5 | 9d00af1a53dde8edf1ba63681243c640 |
|
BLAKE2b-256 | 10a176acd8b62fe46ccea930ec32ecfcd664ae01f41257f61c031a5bb7bd2a82 |
Hashes for simplification-0.5.17-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4177accf6b900726eabb01c7aaf7b657f6ff8b8e7ced0d878d6661b11bc529f3 |
|
MD5 | 34a42287600421208f68a212f0e85a5e |
|
BLAKE2b-256 | 169724fad0543202e83485f70193db415c3a88e6dbd4d3c943016de03626a36b |
Hashes for simplification-0.5.17-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c5f44f73de698a117736f5b5c43cc40828b36df0fe165983f66c4114697a6f12 |
|
MD5 | 5ae9eda2d1ace8dacf56224667bd7b5a |
|
BLAKE2b-256 | ceb46d9d50b48e97cc04b7c71e303694ce41a4d168e3115380b2293e3193df63 |
Hashes for simplification-0.5.17-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d756874d882a963e72d780c95aa2e5a9ed6b6995010e29369a01c4da714fcd74 |
|
MD5 | e9845c726cf9304d79f935228cbec1fa |
|
BLAKE2b-256 | 6dc2d4ff6703f1eb5ecb013a6dea53a6de2968c20be40466232b51ca5ce4485b |
Hashes for simplification-0.5.17-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dacc2fd90cd4bdd40e447c025ce42d75fe6c34c4040bc3842251e693f128b400 |
|
MD5 | 2766d74d7050c36c86dfab41b5b7aed8 |
|
BLAKE2b-256 | 3ba08cd819fc7ff20f7e453558d7890c4002e329084e115206ae56e28e9c3a0e |
Hashes for simplification-0.5.17-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8144f842e0f99fdc252e64fc2617a3dd0481de91be9372888604313121be9983 |
|
MD5 | 36195ec8c448cb1cc135780bce88bd37 |
|
BLAKE2b-256 | 82a8879447dba5cc4de1e18943618bf475239f4d39f7da9d7e6d453e198f61eb |
Hashes for simplification-0.5.17-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5b9484683c86057ef8bd4ced88459ac707db99048b716d192e5f5bf45848a054 |
|
MD5 | bdba3da35bebc6a7d2ebacfac23a0b77 |
|
BLAKE2b-256 | b83646ac248222a0ca6a0c48604013d5f31afce9d2a103b3c8808373fcbd3166 |
Hashes for simplification-0.5.17-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bf46eab7e2fe15e84f2b8aaed877ae41adb244436192b219f531a688193bea74 |
|
MD5 | 222d878a577dd642fda4b6021f5e2b27 |
|
BLAKE2b-256 | aca140aa4b920622bb4309152a6a3ff89db213e3a44abfe7b2400d8a39f1b01c |
Hashes for simplification-0.5.17-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b2d037486f349fe07c3294a39c1a73a0195cd212dfd11f83cfed0bd299b3d833 |
|
MD5 | ac31103f72395f063e76cb07d59dc3cb |
|
BLAKE2b-256 | c5a86273ae3be6552d9befbb84e12c456f0ff6e636c9d71f4c56818d85a69a29 |
Hashes for simplification-0.5.17-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d5d0996743b90bff0a5c2b5bc0a7b61688ef7f9f71505fb9c4cf6df4146f74a8 |
|
MD5 | ecc156454617dba30ee8875349bfc88a |
|
BLAKE2b-256 | 9191ff3f1b09da8514a8f76fffdf299cb125f0c8538365e138acee2fa0d45075 |
Hashes for simplification-0.5.17-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 618080088dd1b5710d32fd01c2230a7ad5f6bfe1136f2f07588b1c934cf52026 |
|
MD5 | 99ced531f002507c26529cef4a89ccfe |
|
BLAKE2b-256 | abe09472fdf71447fd135e2ba014dc4094641364ab53995fb69ff5f636daf2cf |