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 and macOS Darwin only)
- 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 (
manylinux
-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.16-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2f7b6e65e2861ca33c6ca53797903f959e7b8986999fc659ea46d91dbdf64844 |
|
MD5 | 663ca1130e6e4352f71664c7701bdd17 |
|
BLAKE2b-256 | 9dceb9ecdac16551c0fb78bcfb4137f0e5566ecf87619072aa5dab5dc7e4c7b9 |
Hashes for simplification-0.5.16-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f7a82b3089586c47d434845a64d5b0be2ef03d11fcc49a5aac076f95cdaae23e |
|
MD5 | b013f385ca6e6a6ab98e2db2f7916585 |
|
BLAKE2b-256 | 02f162bbf801b49f3291b82b023bd51bc67d250bc2cc091dcaed76ce9d6bbcb0 |
Hashes for simplification-0.5.16-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cb227b081436667563a0fc440f84bc3c4015e8b2ec6f9829e85c963127c0bea6 |
|
MD5 | 4ee1ba22e9bca505ced4cec3abdc9b55 |
|
BLAKE2b-256 | 930d01f83c46fd3e2f3de15e24adf88d71cc6865a43bdb14d2e17dc7ba9b69ca |
Hashes for simplification-0.5.16-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 30ea81e24694889d2b3344d919765cd922c55851f6b433bb62e03df674ac1a23 |
|
MD5 | 859ce0337d28a08d9f37a9103b6b8e0a |
|
BLAKE2b-256 | 9ad239f063cacf89a0f88fda01a79af7e131023d53f929fe54c736795a2f39fe |
Hashes for simplification-0.5.16-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1a993611aef21dc2680634f8f562414d9a72c77e70a6c9cb3c1016d466418817 |
|
MD5 | 1951afef966fa7d2431d72f4d2807127 |
|
BLAKE2b-256 | 2369993d9f9541d20a688d005e7a9cc87982c55d6eef0ef2e42059f05ef3bc05 |
Hashes for simplification-0.5.16-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 37602026f081a59e5abc1687a2548ed08c4d9bbc96feef90efd393728eebfb0e |
|
MD5 | fa58b29f43814b34c8f1ed9899467d06 |
|
BLAKE2b-256 | e4943cff650993f28f7bb6c21d5d442ae0dc083a102ac7f54ac82718ce9528b9 |
Hashes for simplification-0.5.16-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6670eca16c5e8bb23584d5d792372a11042ecd067e962af864a8b6238488efb8 |
|
MD5 | b8b2e74e94400a612ecadf66b5c0a87f |
|
BLAKE2b-256 | c0577067f2241fec5183ec45aaec695cbc947a258a387a20cbe12f90688c1173 |
Hashes for simplification-0.5.16-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5a694ed5c7582690a50effc200df9cf286b5ef2f934c4f9c846b9e194a7ba818 |
|
MD5 | e5cf71185fd52b45162d8be8a8781c24 |
|
BLAKE2b-256 | 7a5b6c908385e6ad7c1e373a9e4d3991f49daeeb2c0207a146da633f8b7bf40f |
Hashes for simplification-0.5.16-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49f0db7c1fbc8534ab3525a584a958dbb331c56e6a19a5b9f8059198be6bae12 |
|
MD5 | ead77c77698cbb2c36a9adefdf3d8bb8 |
|
BLAKE2b-256 | 585bb7996541b9c5a40e8f57931c3bde734fc8b91531fa45060956bdd0549a9f |
Hashes for simplification-0.5.16-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_12_x86_64.manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d411f767263050e57cbec5fe5184bd6bfd3acde4697d9fd16ce0db083a85e539 |
|
MD5 | c8897c6a1eb6aa3dc4ff141c0937cbe5 |
|
BLAKE2b-256 | be9701b8cba03e63b8bd24f647021eeaedc651771ad32680ac8330570132db96 |
Hashes for simplification-0.5.16-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6946626afc7d1b620ad7a66ec0901e80ecc65821851897bf563001117437513a |
|
MD5 | aa40ef1eacdd03edaa273c81afc99dbd |
|
BLAKE2b-256 | 071a971cdf70dd6976ab11ae67366ec47bf8db81509229fbbbcdfc187d3de4d9 |