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.12-cp39-cp39-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 72b2eb12631e1a20abbc5919a4af8ea01dbd275d6fee869489a90c2ced241beb |
|
MD5 | 58678bdc00088359fd4a02ace2a76b16 |
|
BLAKE2b-256 | 0457150b3804bbc4b1ee0ec5d7530e299afd34e8026e16ff8ec2b422c1b57068 |
Hashes for simplification-0.5.12-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 | ff09e535cbdc85d69b9a3f0386ec674164ba0f7c4182231e9d47dcc8f515430c |
|
MD5 | 9fbc6027aa5f40d61d79e064a3614025 |
|
BLAKE2b-256 | 0bf486b8d8be387fc2796a2d4f26badfcd1db6315b1c34043401e599a19e8fd1 |
Hashes for simplification-0.5.12-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 054409a80f11b1102cf09283ab3b9baa5113a27bcf6c133bacc5097927bcb146 |
|
MD5 | 513635a249f38c6141848d2f6700150e |
|
BLAKE2b-256 | 0892e50886333267c51beb6f626f577bfdeec1fc8f739033376acc420e0e86c3 |
Hashes for simplification-0.5.12-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4ac340e8d39d2d26c91b277abfce6fe116179ba950847c1a2955b9dc85ebba2e |
|
MD5 | 3f838b5f45729a8daf4b8d6622e09bfe |
|
BLAKE2b-256 | de4b751309f787c74c4e6cd4ffa0cf21979779ef7ad63739f594cb9c05304200 |
Hashes for simplification-0.5.12-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 | 55a7e5266b0c310dba80aa36ca3f420b47cfefceb4f43dd9a91950b315ecb4e1 |
|
MD5 | b1cff096946df44f37f8f1ae02736844 |
|
BLAKE2b-256 | d4546a2e17d7d2ae5decede5ae9127b481ce9aa418652edde46b73fd090e62f2 |
Hashes for simplification-0.5.12-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 59b418eadbb78edf3f57cea6b6bb1cdc98c0dcd93e9385486f0d03a22e31bf87 |
|
MD5 | 8ad39400054bba8eaa2d0516c62e7f0d |
|
BLAKE2b-256 | be0421ef473bd1223d994be34ebacf2475bc7b60e482a21832f963c5820b2f91 |
Hashes for simplification-0.5.12-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16236ce491dd345a8195c055eba2ddef498bdb9da270f83bda7fa4fdb271950c |
|
MD5 | 3196fcb4034a3c5651c9be695333c3e0 |
|
BLAKE2b-256 | 7e7b986e1397bbe6666e952d0e72970faf2b542210b876babc35b3ed22209166 |
Hashes for simplification-0.5.12-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | afde8ead96913ece2370cd893e940b95efae0acbce8a5ef021231f509f7c7e99 |
|
MD5 | 51e133be7964b047fe0c2d6e4f5fb8b5 |
|
BLAKE2b-256 | 3729048b541d77fa139d5632c55615b8a5472f5ae042bbdc568c315c39c7e2dd |
Hashes for simplification-0.5.12-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 | 764b42da51b22e97d35f9ae72fb924d11c326428dfe7427f59dcc04da97dd865 |
|
MD5 | 92e86088498f80e7c6c46a22759823e0 |
|
BLAKE2b-256 | d9dfcd3b75868de4a632fac5d0a7577c6d0f2dae5673eb5994b77e006a6481c9 |