Copyright	(C) Frank Staals
License	see the LICENSE file
Maintainer	Frank Staals
Safe Haskell	None
Language	Haskell2010

Algorithms.Geometry.PolyLineSimplification.DouglasPeucker

Contents

Internal functions

Description

Synopsis

douglasPeucker :: (Ord r, Fractional r, Arity d) => r -> PolyLine d p r -> PolyLine d p r
merge :: PolyLine d p r -> PolyLine d p r -> PolyLine d p r
split :: Int -> PolyLine d p r -> (PolyLine d p r, PolyLine d p r)
maxDist :: (Ord r, Fractional r, Arity d) => LSeq n (Point d r :+ p) -> LineSegment d p r -> (Int, r)

Documentation

douglasPeucker :: (Ord r, Fractional r, Arity d) => r -> PolyLine d p r -> PolyLine d p r Source #

Line simplification with the well-known Douglas Peucker alogrithm. Given a distance value eps adn a polyline pl, constructs a simplification of pl (i.e. with vertices from pl) s.t. all other vertices are within dist eps to the original polyline.

Running time: \( O(n^2) \) worst case, \( O(n log n) \) expected.

Internal functions

merge :: PolyLine d p r -> PolyLine d p r -> PolyLine d p r Source #

Concatenate the two polylines, dropping their shared vertex

split :: Int -> PolyLine d p r -> (PolyLine d p r, PolyLine d p r) Source #

Split the polyline at the given vertex. Both polylines contain this vertex

maxDist :: (Ord r, Fractional r, Arity d) => LSeq n (Point d r :+ p) -> LineSegment d p r -> (Int, r) Source #

Given a sequence of points, find the index of the point that has the Furthest distance to the LineSegment. The result is the index of the point and this distance.