All Projects → urschrei → Simplification

urschrei / Simplification

Licence: mit
Very fast LineString simplification using RDP or Visvalingam-Whyatt and a Rust binary

Programming Languages

python
139335 projects - #7 most used programming language

Projects that are alternatives of or similar to Simplification

rdp
A library providing FFI access to fast Ramer–Douglas–Peucker and Visvalingam-Whyatt line simplification algorithms
Stars: ✭ 20 (-74.36%)
Mutual labels:  geo, geospatial, computational-geometry, rdp
Geopython
Notebooks and libraries for spatial/geo Python explorations
Stars: ✭ 268 (+243.59%)
Mutual labels:  geospatial, geo, computational-geometry
fgpv-vpgf
RAMP2 FGP Visualiser / Visualisateur pour la PGF PCAR2 - The Reusable Accessible Mapping Platform (RAMP), also known as the Federal Geospatial Platform Visualiser (FGPV), is a Javascript based web mapping platform that provides a reusable, responsive and WCAG 2.1 "AA" compliant common viewer platform for the Government of Canada. This is an unsu…
Stars: ✭ 34 (-56.41%)
Mutual labels:  geo, geospatial
GeoJSON.jl
Utilities for working with GeoJSON data in Julia
Stars: ✭ 46 (-41.03%)
Mutual labels:  geo, geospatial
Election Geodata
Precinct shapes (and vote results) for US elections past, present, and future
Stars: ✭ 289 (+270.51%)
Mutual labels:  geospatial, geo
turf-go
A Go language port of Turf.js
Stars: ✭ 41 (-47.44%)
Mutual labels:  geo, geospatial
tile38
Real-time Geospatial and Geofencing
Stars: ✭ 8,117 (+10306.41%)
Mutual labels:  geo, geospatial
QGeoView
QGeoView is a Qt / C ++ widget for visualizing geographic data.
Stars: ✭ 33 (-57.69%)
Mutual labels:  geo, geospatial
rgis
Performant, cross-platform (web, desktop) GIS app written in Rust
Stars: ✭ 79 (+1.28%)
Mutual labels:  geo, geospatial
Mapsui
Mapsui is a .NET Map component for WPF, Xamarin.Forms, Xamarin.Android, Xamarin.iOS and UWP
Stars: ✭ 447 (+473.08%)
Mutual labels:  geospatial, geo
Orb
Types and utilities for working with 2d geometry in Golang
Stars: ✭ 378 (+384.62%)
Mutual labels:  geospatial, geo
Go Geom
Package geom implements efficient geometry types for geospatial applications.
Stars: ✭ 456 (+484.62%)
Mutual labels:  geospatial, geo
pyturf
A modular geospatial engine written in python
Stars: ✭ 15 (-80.77%)
Mutual labels:  geo, geospatial
georaster-layer-for-leaflet
Display GeoTIFFs and soon other types of raster on your Leaflet Map
Stars: ✭ 168 (+115.38%)
Mutual labels:  geo, geospatial
Geo On Fire
A library to create high performance geolocation queries for Firebase. Checkout the demos: https://run.plnkr.co/plunks/AYaN8ABEDcMntgbJyLVW/ and https://run.plnkr.co/plunks/xJgstAvXYcp0w7MbOOjm/
Stars: ✭ 54 (-30.77%)
Mutual labels:  geospatial, geo
GMT.jl
Generic Mapping Tools Library Wrapper for Julia
Stars: ✭ 148 (+89.74%)
Mutual labels:  geo, geospatial
Shapefile.jl
Parsing .shp files in Julia
Stars: ✭ 40 (-48.72%)
Mutual labels:  geospatial, geo
Atlas
🌎 Atlas is a set of APIs for looking up information about locations
Stars: ✭ 21 (-73.08%)
Mutual labels:  geo, geospatial
Solaris
CosmiQ Works Geospatial Machine Learning Analysis Toolkit
Stars: ✭ 290 (+271.79%)
Mutual labels:  geospatial, geo
Proj4.jl
Julia wrapper for the PROJ cartographic projections library
Stars: ✭ 23 (-70.51%)
Mutual labels:  geospatial, geo

Build Status Build status Coverage Status

Simplification

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

Line

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

MIT

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].