Data

Tools

Indexes

Applications

Experiments

Open Source Science

simplification

Very fast Python line simplification using either the RDP or Visvalingam-Whyatt algorithm implemented in Rust

https://github.com/urschrei/simplification

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ✓
    DOI references
    Found 3 DOI reference(s) in README
  • ✓
    Academic publication links
    Links to: zenodo.org
  • ○
    Committers with academic emails
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (13.9%) to scientific vocabulary

Keywords

computational-geometry geo geospatial linestring polyline rdp simplification visvalingam-whyatt

Keywords from Contributors

cryptocurrencies graph-generation mesh network-simulation hacking optim interactive pde projection sequences
Last synced: 6 months ago · JSON representation ·

Repository

Very fast Python line simplification using either the RDP or Visvalingam-Whyatt algorithm implemented in Rust

Basic Info
  • Host: GitHub
  • Owner: urschrei
  • License: other
  • Language: Python
  • Default Branch: master
  • Homepage:
  • Size: 3.68 MB
Statistics
  • Stars: 188
  • Watchers: 6
  • Forks: 17
  • Open Issues: 4
  • Releases: 65
Topics
computational-geometry geo geospatial linestring polyline rdp simplification visvalingam-whyatt
Created over 9 years ago · Last pushed 6 months ago
Metadata Files
Readme License Citation

README.md

Build Status Coverage Status Downloads DOI Anaconda-Server Badge

Simplification

Simplify a LineString using the Ramer–Douglas–Peucker or Visvalingam-Whyatt algorithms

Line

Installation

uv add simplification OR
pip install simplification OR
conda install conda-forge::simplification

Installing for local development

  1. Ensure you have a copy of librdp from https://github.com/urschrei/rdp/releases, and it's in the src/simplification subdir
  2. run pip install -e .[test] --use-pep517
  3. run pytest .

Supported Python Versions

Simplification supports all currently supported Python versions.

Supported Platforms

  • Linux (manylinux-compatible) x86_64 and aarch64
  • macOS Darwin x86_64 and arm64
  • Windows 64-bit

Usage

```python from simplification.cutil import ( simplifycoords, simplifycoordsidx, simplifycoordsvw, simplifycoordsvwidx, simplifycoordsvwp, )

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

import numpy as np coordsvw = np.array([ [5.0, 2.0], [3.0, 8.0], [6.0, 20.0], [7.0, 25.0], [10.0, 10.0] ]) simplifiedvw = simplifycoordsvw(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.

``` python

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 = (decodepolyline(line, 5) for line in polylines) simplified = [simplifycoords(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

Blue Oak Model Licence 1.0.0

Citing Simplification

If Simplification has been significant in your research, and you would like to acknowledge the project in your academic publication, we suggest citing it as follows (example in APA style, 7th edition):

Hügel, S. (2021). Simplification (Version X.Y.Z) [Computer software]. https://doi.org/10.5281/zenodo.5774852

In Bibtex format:

@software{Hugel_Simplification_2021,
author = {Hügel, Stephan},
doi = {10.5281/zenodo.5774852},
license = {MIT},
month = {12},
title = {{Simplification}},
url = {https://github.com/urschrei/simplification},
version = {X.Y.Z},
year = {2021}
}

Owner

  • Name: Stephan Hügel
  • Login: urschrei
  • Kind: user
  • Location: Dublin
  • Company: Trinity College Dublin

Marie Curie research fellow at TCD: smart cities and climate change. Prev: @casa-ucl. I also work on high-performance computational geometry libraries @georust

Citation (CITATION.cff) 

cff-version: 1.1.0
message: "If you use this software, please cite it using these metadata."
abstract: "Simplification: a Python library for line simplification using the Ramer-Douglas-Peucker or Visvaligam-Whyatt algorithms"
authors:
  -
    family-names: "Hügel"
    given-names: Stephan
    orcid: "https://orcid.org/0000-0003-4379-2450"
title: "Simplification"
date-released: 2021-12-12
doi: "10.5281/zenodo.5774852"
keywords:
  - geo
  - gis
  - ramer-douglas-peucker
  - visvalingam-whyatt
license: BlueOak-1.0.0
repository-code: "https://github.com/urschrei/simplification"
version: "0.5.21"

GitHub Events

Total
  • Release event: 1
  • Watch event: 17
  • Delete event: 14
  • Issue comment event: 1
  • Push event: 12
  • Pull request event: 31
  • Create event: 15
Last Year
  • Release event: 1
  • Watch event: 17
  • Delete event: 14
  • Issue comment event: 1
  • Push event: 12
  • Pull request event: 31
  • Create event: 15

Committers

Last synced: 9 months ago

All Time
  • Total Commits: 466
  • Total Committers: 7
  • Avg Commits per committer: 66.571
  • Development Distribution Score (DDS): 0.161
Past Year
  • Commits: 43
  • Committers: 3
  • Avg Commits per committer: 14.333
  • Development Distribution Score (DDS): 0.419
Top Committers
Name Email Commits
Stephan Hügel s****l@t****e 391
dependabot[bot] 4****] 66
Ivan Zaikin i****n@i****m 5
dependabot-preview[bot] 2****] 1
Taher Chegini t****i@g****m 1
Alexandr Artemyev m****t@g****m 1
Dongsin Kim d****m@g****m 1
Committer Domains (Top 20 + Academic)
invitae.com: 1 tcd.ie: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time
  • Total issues: 28
  • Total pull requests: 112
  • Average time to close issues: 4 months
  • Average time to close pull requests: 3 days
  • Total issue authors: 24
  • Total pull request authors: 7
  • Average comments per issue: 3.79
  • Average comments per pull request: 0.2
  • Merged pull requests: 100
  • Bot issues: 0
  • Bot pull requests: 106
Past Year
  • Issues: 1
  • Pull requests: 41
  • Average time to close issues: about 1 month
  • Average time to close pull requests: about 8 hours
  • Issue authors: 1
  • Pull request authors: 1
  • Average comments per issue: 0.0
  • Average comments per pull request: 0.0
  • Merged pull requests: 36
  • Bot issues: 0
  • Bot pull requests: 41
View more stats
Top Authors
Issue Authors
  • theroggy (3)
  • versae (2)
  • cheginit (2)
  • Pitirus (1)
  • wagenrace (1)
  • Sovetnikov (1)
  • nka77 (1)
  • odel4y (1)
  • Jens-81 (1)
  • christophfink (1)
  • utapyngo (1)
  • xdmiodz (1)
  • sivashankar28 (1)
  • soichih (1)
  • warrenbocphet (1)
Pull Request Authors
  • dependabot[bot] (105)
  • cheginit (2)
  • urschrei (1)
  • Mogost (1)
  • dongsin-kim (1)
  • utapyngo (1)
  • dependabot-preview[bot] (1)
Top Labels
Issue Labels
Pull Request Labels
dependencies (106) github_actions (105)

Packages

  • Total packages: 1
  • Total downloads:
    • pypi 43,815 last-month
  • Total docker downloads: 43
  • Total dependent packages: 12
  • Total dependent repositories: 47
  • Total versions: 46
  • Total maintainers: 1
pypi.org: simplification

Fast linestring simplification using RDP or Visvalingam-Whyatt and a Rust binary

  • Documentation: https://simplification.readthedocs.io/
  • License: # Blue Oak Model License Version 1.0.0 ## Purpose This license gives everyone as much permission to work with this software as possible, while protecting contributors from liability. ## Acceptance In order to receive this license, you must agree to its rules. The rules of this license are both obligations under that agreement and conditions to your license. You must not do anything with this software that triggers a rule that you cannot or will not follow. ## Copyright Each contributor licenses you to do everything with this software that would otherwise infringe that contributor's copyright in it. ## Notices You must ensure that everyone who gets a copy of any part of this software from you, with or without changes, also gets the text of this license or a link to <https://blueoakcouncil.org/license/1.0.0>. ## Excuse If anyone notifies you in writing that you have not complied with [Notices](#notices), you can keep your license by taking all practical steps to comply within 30 days after the notice. If you do not do so, your license ends immediately. ## Patent Each contributor licenses you to do everything with this software that would otherwise infringe any patent claims they can license or become able to license. ## Reliability No contributor can revoke this license. ## No Liability ***As far as the law allows, this software comes as is, without any warranty or condition, and no contributor will be liable to anyone for any damages related to this software or this license, under any kind of legal claim.***
  • Latest release: 0.7.13
    published over 1 year ago
  • Versions: 46
  • Dependent Packages: 12
  • Dependent Repositories: 47
  • Downloads: 43,815 Last month
  • Docker Downloads: 43
Rankings
Dependent packages count: 0.9%
Downloads: 1.7%
Dependent repos count: 2.1%
Average: 3.9%
Docker downloads count: 4.1%
Stargazers count: 5.8%
Forks count: 8.5%
Maintainers (1)
urschrei
Last synced: 6 months ago

Dependencies

.github/workflows/wheels.yml actions
  • actions/checkout v3 composite
  • actions/download-artifact v3 composite
  • actions/upload-artifact v3 composite
  • ncipollo/release-action v1 composite
  • oprypin/find-latest-tag v1 composite
  • pypa/cibuildwheel v2.11.4 composite
  • robinraju/release-downloader v1.7 composite
pyproject.toml pypi
setup.py pypi