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, 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.10-cp39-cp39-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 17df9f4ffa6c3e797050b83d9a03ff4607c21a23e011c0f17d4e213bd544a3ad |
|
MD5 | 01438accc98e9978c53c9d1624f2949c |
|
BLAKE2b-256 | 1c86948d05f78f8a400aaa9058fe6998c85393222edb95147c66310f365fc812 |
Hashes for simplification-0.5.10-cp39-cp39-macosx_10_14_x86_64.macosx_10_9_intel.macosx_10_9_x86_64.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 070a6862d8c938e21204635582130998799b7dbf5b00ab80f6626ec36df64944 |
|
MD5 | 0b8c0ad3b5478f2e4daac5fdd3350ebe |
|
BLAKE2b-256 | 0abf9ecc27abd09ff41025d1852e33514f1c0c83f96ce4113e6223190b0c5d45 |
Hashes for simplification-0.5.10-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8d9309e185af9ad68143ac812e6449382e96a26eb4391a21255906c46e283f46 |
|
MD5 | aa5828766381869e5b5db75f612ffdd5 |
|
BLAKE2b-256 | 8caf4f26b191e010e92fe756681199d59e28f5e812508a3f6d90fa182ab76d88 |
Hashes for simplification-0.5.10-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | befbd82a6554dc8c44a37e0afcbbe38bff01817ff3845ec6d21b6d8e45c8b334 |
|
MD5 | 8ab57faca6d55fde38f670e7d3247910 |
|
BLAKE2b-256 | 58c0cda5cfa94aea91f2f8ca8dddc9551880f2b14cee90b5dcaca315f0a06616 |
Hashes for simplification-0.5.10-cp38-cp38-macosx_10_14_x86_64.macosx_10_9_intel.macosx_10_9_x86_64.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8248e922c4314f20199c156b482edef85104abbb405ead082097072cb11a3314 |
|
MD5 | f804b6985724f1eefbc77b59f38d8e70 |
|
BLAKE2b-256 | 8f1bf201cc2a8de24fc007c3f101067e94e4928e23cd653acdb8479e8d9e7391 |
Hashes for simplification-0.5.10-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 561b8705a4657b688d15bbf441d74f2028a9a195b28dae680d6d533d07780a19 |
|
MD5 | 5b70c9130e77e1ee29734de50cfd7a36 |
|
BLAKE2b-256 | 1c4410785a0364ecedbe3aefc591871c010c35c880b696f70b59a9a0dad5182d |
Hashes for simplification-0.5.10-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6acefb53d495953b4b0b7b8059b01e9d2b68130170b6c650f37c3812f5df0dde |
|
MD5 | 47bf694e8bfdb794112594960e709b87 |
|
BLAKE2b-256 | 8211ee6f4c3497a379389069c36306b79fbca2fe24c5ae1fff84d47c11d5000d |
Hashes for simplification-0.5.10-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6474501e0193f1e1649f99bc7d041a733432188fbb948909b3c209f8d1b10528 |
|
MD5 | 3171a3b1fae4572fcd9d4c22eca5d2b5 |
|
BLAKE2b-256 | 2f6c0140395fecf67b3695a3f667e4fba3f0718530fbe6b3f31c4d0070aeb5d0 |
Hashes for simplification-0.5.10-cp37-cp37m-macosx_10_14_x86_64.macosx_10_9_intel.macosx_10_9_x86_64.macosx_10_10_intel.macosx_10_10_x86_64.macosx_10_11_intel.macosx_10_11_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 290229331ecae9e4e7a17c1a4ea4482a25a2891945a69c6954be3cb9ffb2c32d |
|
MD5 | 5cefec75585086e8f0246ac093958dec |
|
BLAKE2b-256 | 9059166eee614e81d247fab9f4648c38a5a78b0c3c8cc1ecc431a1741257f72f |