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 Darwin only)
- Python 3.9 (Linux and macOS Darwin only)
- Python 3.10 (Linux and macOS Darwin only)
Supported Platforms
- Linux (
manylinux1
-compatible) - macOS Darwin
- 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.14-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 35ee71855986dc924e67634245e625c6ba48744b2d5e34e3116d4e3034b16c8e |
|
MD5 | 1f0579ea6e3c34e1e73c304ccef6d9d2 |
|
BLAKE2b-256 | 9c35ab19393236f50f5a353a0ff67038b7c2fccd8e5a193dc02a8b5c089130a3 |
Hashes for simplification-0.5.14-cp310-cp310-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a7c03521893954a0bc062128031d814e0bb3adeca15486ca94c83af7cef0e7e4 |
|
MD5 | 4d3d217ed10b5c0fa764e283ae4b51d4 |
|
BLAKE2b-256 | 185593f2d2c900aeb24e0b41fa5e3e184507663e8ede4d2fce8785e0426ae49d |
Hashes for simplification-0.5.14-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9a0eef415904897eb459430f016ff0a31b540c45fe28f7e362d91c5f57a3a5b3 |
|
MD5 | 10bb9d16ec16cd4deb30d674ea9fcac2 |
|
BLAKE2b-256 | 38afcaebf2d4552b2111144302705f09174cfe3aa1eb72ef5617bae87b15cf05 |
Hashes for simplification-0.5.14-cp39-cp39-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b019feab72bf45b33d85fd1c00daf7bf8ccd2051f4c04f17888708a2877097b1 |
|
MD5 | 41b5077694b6365bf836b380117035bd |
|
BLAKE2b-256 | 8889bf8875642da64766ea425b5379cbff91d9e83a776b8b324f33b1ecd772ee |
Hashes for simplification-0.5.14-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 36cc83bdac297fdcbec55ea0261c90edafe4fe8e010221d4864f783a8341849f |
|
MD5 | 9638178c932783b5247d528823ab8488 |
|
BLAKE2b-256 | 511bf49f2f02ce7c29e0bfb6212fb2d0193b65cdef664ea9b23dcee784afac61 |
Hashes for simplification-0.5.14-cp38-cp38-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9ee66c008c6d1fa5545cef01e49aaa54d1e96b44f0fc805bb2d4f06bc7fed49 |
|
MD5 | 81d860572936e371a3177e6bf9391a58 |
|
BLAKE2b-256 | ccce5ab22d43b95feb48be105729563f7bf0fe4db46b3f6f4def0ae5ca7c61f7 |
Hashes for simplification-0.5.14-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 193e22d8d7625dd1f38719ab66105156bd63a3132cef03cbdaa5130d7c0c0bdf |
|
MD5 | ae49d00b59e03d8d4cbb3f315eeea4f6 |
|
BLAKE2b-256 | ed03354b2f72ddad16ef87c006c1a183daa03936fa5c37c3750f581e8081e807 |
Hashes for simplification-0.5.14-cp37-cp37m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a0eaf1f2f4dd7ac59e3c416468b891d2320afa9954c6fa6dc1c6b04b8103464 |
|
MD5 | 6eb05708b4c1c079bd85e49abf62e812 |
|
BLAKE2b-256 | 794a2ea0251dfbdd8ccae45aeb437968044b591e1f927e2f5e063aca27949146 |