reducers

README

go.geo/reducers

This package implements several reducers that simplify a geo.Path object. See the reducers godoc for more information.

Note: all these methods create a new path and do not modify the input path.

Currently implemented:

• Douglas-Peucker
• Visvalingam
• Radial

Performance

These reducers are optimized and performance is comparible to libraries in other languages.

go get github.com/paulmach/go.geo/reducers go test github.com/paulmach/go.geo/reducers -bench .

Douglas-Peucker

Probably the most popular simplification algorithm around. For algorithm details, see wikipedia.

Usage:

originalPath := geo.NewPath()
reducedPath := reducers.DouglasPeucker(originalPath, threshold)

// the index map method can be used to figure out which of the points were kept
reducedPath, indexMap := reducers.DouglasPeuckerIndexMap(originalPath, threshold)

for i, v := range indexMap {
	reducedPath.GetAt(i) == originalPath.GetAt(v)
}

// to chain reducers and combine their index maps use MergeIndexMaps
p1, im1 := reducers.RadialIndexMap(path, meters) 
reducedPath, im2 := reducers.DouglasPeuckerIndexMap(p1, threshold)
indexMap := MergeIndexMaps(im1, im2)

Visvalingam

See Mike Bostock's explanation for algorithm details.

Usage:

originalPath := geo.NewPath()
reducedPath := reducers.DouglasPeucker(originalPath, threshold)

// will remove all whose triangle is smaller than `threshold`
reducedPath := reducers.VisvalingamThreshold(path, threshold)

// will remove points until there are only `toKeep` points left.
reducedPath := reducers.VisvalingamKeep(path, toKeep)

// One can also combine the parameters.
// This will continue to remove points until 
//  - there are no more below the threshold,
//  - or the new path is of length `toKeep`
reducedpath := reducers.Visvalingam(path, threshold, toKeep)

Radial

Radial reduces the path by removing points that are close together. A full algorithm description.

Usage:

originalPath := geo.NewPath()

// this method uses a Euclidean distance measure.
reducedPath := reducers.Radial(path, meters)

// if the points are in the lng/lat space Radial Geo will 
// compute the geo distance between the coordinates.
reducedPath := reducers.RadialGeo(path, meters)

Documentation

Index

• func DouglasPeucker(path *geo.Path, threshold float64) *geo.Path
• func DouglasPeuckerGeoIndexMap(path *geo.Path, meters float64) (reduced *geo.Path, indexMap []int)
• func DouglasPeuckerIndexMap(path *geo.Path, threshold float64) (reduced *geo.Path, indexMap []int)
• func MergeIndexMaps(map1, map2 []int) []int
• func Radial(path *geo.Path, meters float64) *geo.Path
• func RadialGeo(path *geo.Path, meters float64) *geo.Path
• func RadialGeoIndexMap(path *geo.Path, meters float64) (*geo.Path, []int)
• func RadialIndexMap(path *geo.Path, meters float64) (*geo.Path, []int)
• func Visvalingam(path *geo.Path, threshold float64, minPointsToKeep int) *geo.Path
• func VisvalingamKeep(path *geo.Path, toKeep int) *geo.Path
• func VisvalingamThreshold(path *geo.Path, threshold float64) *geo.Path
• type DouglasPeuckerReducer
  • func NewDouglasPeucker(threshold float64) *DouglasPeuckerReducer
  • func (r DouglasPeuckerReducer) GeoReduce(path *geo.Path) *geo.Path
  • func (r DouglasPeuckerReducer) Reduce(path *geo.Path) *geo.Path
• type RadialGeoReducer
  • func NewRadialGeoReducer(meters float64) *RadialGeoReducer
  • func (r RadialGeoReducer) GeoReduce(path *geo.Path) *geo.Path
  • func (r RadialGeoReducer) Reduce(path *geo.Path) *geo.Path
• type RadialReducer
  • func NewRadialReducer(threshold float64) *RadialReducer
  • func (r RadialReducer) GeoReduce(path *geo.Path) *geo.Path
  • func (r RadialReducer) Reduce(path *geo.Path) *geo.Path
• type VisvalingamReducer
  • func NewVisvalingamReducer(threshold float64, minPointsToKeep int) *VisvalingamReducer
  • func (r VisvalingamReducer) GeoReduce(path *geo.Path) *geo.Path
  • func (r VisvalingamReducer) Reduce(path *geo.Path) *geo.Path

Functions

func DouglasPeucker

func DouglasPeucker(path *geo.Path, threshold float64) *geo.Path

DouglasPeucker simplifies the path using the Douglas Peucker method. Returns a new path and DOES NOT modify the original.

func DouglasPeuckerGeoIndexMap

func DouglasPeuckerGeoIndexMap(path *geo.Path, meters float64) (reduced *geo.Path, indexMap []int)

DouglasPeuckerGeoIndexMap is similar to GeoReduce but returns an array that maps each new path index to its original path index. Returns a new path and DOES NOT modify the original.

func DouglasPeuckerIndexMap

func DouglasPeuckerIndexMap(path *geo.Path, threshold float64) (reduced *geo.Path, indexMap []int)

DouglasPeuckerIndexMap is similar to DouglasPeucker but returns an array that maps each new path index to its original path index. Returns a new path and DOES NOT modify the original.

func MergeIndexMaps

func MergeIndexMaps(map1, map2 []int) []int

MergeIndexMaps merges two index maps for use when chaining reducers. For example, to radially reduce and then DP, merge the index maps with this function to get a map from the original to the final path.

func Radial

func Radial(path *geo.Path, meters float64) *geo.Path

Radial peforms a radial distance polyline simplification using a standard euclidean distance. Returns a new path and DOES NOT modify the original.

func RadialGeo

func RadialGeo(path *geo.Path, meters float64) *geo.Path

RadialGeo peforms a radial distance polyline simplification using the GeoDistance. ie. the path points must be lng/lat points otherwise the behavior of this function is undefined. Returns a new path and DOES NOT modify the original.

func RadialGeoIndexMap

func RadialGeoIndexMap(path *geo.Path, meters float64) (*geo.Path, []int)

RadialGeoIndexMap is similar to RadialGeo but returns an array that maps each new path index to its original path index. Returns a new path and DOES NOT modify the original.

func RadialIndexMap

func RadialIndexMap(path *geo.Path, meters float64) (*geo.Path, []int)

RadialIndexMap is similar to Radial but returns an array that maps each new path index to its original path index. Returns a new path and DOES NOT modify the original.

func Visvalingam

func Visvalingam(path *geo.Path, threshold float64, minPointsToKeep int) *geo.Path

Visvalingam computes the Visvalingam-Whyatt on the polyline. Returns a new path and DOES NOT modify the original.

Threshold is the max triangle area to keep around, ie. remove all triangles below this threshold. minPointsToKeep is the minimum number of points in the line.

To just use the threshold, set minPointsToKeep to zero To just use minPointsToKeep, set the threshold to something big like math.MaxFloat64

http://bost.ocks.org/mike/simplify/

func VisvalingamKeep

func VisvalingamKeep(path *geo.Path, toKeep int) *geo.Path

VisvalingamKeep runs the Visvalingam-Whyatt algorithm removing triangles of minimum area until we're down to `toKeep` number of points. Returns a new path and DOES NOT modify the original.

func VisvalingamThreshold

func VisvalingamThreshold(path *geo.Path, threshold float64) *geo.Path

VisvalingamThreshold runs the Visvalingam-Whyatt algorithm removing triangles whose area is below the threshold. This function is here to simplify the interface. Returns a new path and DOES NOT modify the original.

Types

type DouglasPeuckerReducer

type DouglasPeuckerReducer struct {
	Threshold float64
}

A DouglasPeuckerReducer wraps the DouglasPeucker function to fulfill the geo.Reducer and geo.GeoReducer interfaces.

func NewDouglasPeucker

func NewDouglasPeucker(threshold float64) *DouglasPeuckerReducer

NewDouglasPeucker creates a new DouglasPeuckerReducer.

func (DouglasPeuckerReducer) GeoReduce

func (r DouglasPeuckerReducer) GeoReduce(path *geo.Path) *geo.Path

GeoReduce runs the DouglasPeucker on a lng/lat path. The threshold is expected to be in meters.

func (DouglasPeuckerReducer) Reduce

func (r DouglasPeuckerReducer) Reduce(path *geo.Path) *geo.Path

Reduce runs the DouglasPeucker using the threshold of the DouglasPeuckerReducer.

type RadialGeoReducer

type RadialGeoReducer struct {
	Threshold float64 // meters
}

A RadialGeoReducer wraps the RadialGeo function to fulfill the geo.Reducer and geo.GeoReducer interfaces.

func NewRadialGeoReducer

func NewRadialGeoReducer(meters float64) *RadialGeoReducer

NewRadialGeoReducer creates a new RadialGeoReducer. This reducer should be used with EPSG:4326 (lng/lat) paths.

func (RadialGeoReducer) GeoReduce

func (r RadialGeoReducer) GeoReduce(path *geo.Path) *geo.Path

GeoReduce runs the RadialGeo reduction. The path should be in lng/lat (EPSG:4326). The threshold is expected to be in meters.

func (RadialGeoReducer) Reduce

func (r RadialGeoReducer) Reduce(path *geo.Path) *geo.Path

Reduce runs the RadialGeo reduction using the threshold of the RadialGeoReducer. The threshold is expected to be in meters.

type RadialReducer

type RadialReducer struct {
	Threshold float64 // euclidean distance
}

A RadialReducer wraps the Radial function to fulfill the geo.Reducer and geo.GeoReducer interfaces.

func NewRadialReducer

func NewRadialReducer(threshold float64) *RadialReducer

NewRadialReducer creates a new RadialReducer.

func (RadialReducer) GeoReduce

func (r RadialReducer) GeoReduce(path *geo.Path) *geo.Path

GeoReduce runs the RadialGeo reduction. The path should be in lng/lat (EPSG:4326). The threshold is expected to be in meters.

func (RadialReducer) Reduce

func (r RadialReducer) Reduce(path *geo.Path) *geo.Path

Reduce runs the Radial reduction using the threshold of the RadialReducer.

type VisvalingamReducer

type VisvalingamReducer struct {
	Threshold float64
	ToKeep    int
}

A VisvalingamReducer wraps the Visvalingam function to fulfill the geo.Reducer and geo.GeoReducer interfaces.

func NewVisvalingamReducer

func NewVisvalingamReducer(threshold float64, minPointsToKeep int) *VisvalingamReducer

NewVisvalingamReducer creates a new VisvalingamReducer.

func (VisvalingamReducer) GeoReduce

func (r VisvalingamReducer) GeoReduce(path *geo.Path) *geo.Path

GeoReduce runs the Visvalingam reduction on a lng/lat path. The threshold is expected to be in meters squared.

func (VisvalingamReducer) Reduce

func (r VisvalingamReducer) Reduce(path *geo.Path) *geo.Path

Reduce runs the Visvalingam reduction using the values of the Visvalingam.