Metadata-Version: 2.1
Name: simplification
Version: 0.5.2
Summary: Fast linestring simplification using RDP or Visvalingam-Whyatt and a Rust binary
Home-page: https://github.com/urschrei/simplification
Author: Stephan Hügel
Author-email: urschrei@gmail.com
License: MIT License
Download-URL: https://github.com/urschrei/simplification/tarball/v0.5.2
Keywords: Geo,Polyline,Linestring,Ramer-Douglas-Peucker,Douglas-Peucker,Visvalingam-Whyatt
Platform: UNKNOWN
Classifier: Programming Language :: Python
Classifier: Programming Language :: Python :: 2.7
Classifier: Programming Language :: Python :: 3.6
Classifier: Programming Language :: Python :: 3.7
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Education
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Topic :: Scientific/Engineering :: GIS
Description-Content-Type: text/markdown
Requires-Dist: numpy (>=1.11.0)

[![Build Status](https://travis-ci.org/urschrei/simplification.svg?branch=master)](https://travis-ci.org/urschrei/simplification) [![Build status](https://ci.appveyor.com/api/projects/status/0n7d5iwb3uqhsos6/branch/master?svg=true)](https://ci.appveyor.com/project/urschrei/simplification/branch/master) [![Coverage Status](https://coveralls.io/repos/github/urschrei/simplification/badge.svg?branch=master)](https://coveralls.io/github/urschrei/simplification?branch=master)

# Simplification
Simplify a LineString using the [Ramerâ€“Douglasâ€“Peucker](https://en.wikipedia.org/wiki/Ramerâ€“Douglasâ€“Peucker_algorithm) or [Visvalingam-Whyatt](https://bost.ocks.org/mike/simplify/) algorithms

![Line](https://cdn.rawgit.com/urschrei/rdp/6c84264fd9cdc0b8fdf974fc98e51fea4834ed05/rdp.svg)  

## Installation
`pip install simplification`  
Please use a recent (>= 8.1.2) version of `pip`.

### Supported Python Versions
- Python 2.7
- Python 3.6
- Python 3.7
- Python 3.8 (Linux and macOS only)

### Supported Platforms
- Linux (`manylinux1`-compatible)
- macOS
- Windows 32-bit / 64-bit

## Usage
```python
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](https://docs.scipy.org/doc/numpy/reference/maskedarray.generic.html#what-is-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](https://github.com/urschrei/pypolyline) 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 = (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](https://github.com/urschrei/rdp)

## 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](benchmark_runner.py).
#### Disclaimer
All benchmarks are subjective, and pathological input will greatly increase processing time. Error-checking is non-existent at this point.

## License
[MIT](license.txt)


