Root namespace of the polyline simplification library. More...

Namespaces
	math
	Contains functions for calculating statistics and distances between various geometric entities.

	util
	Contains utility functions and classes.

Classes
class	PolylineSimplification
	Provides various simplification algorithms for n-dimensional simple polylines. More...

Functions
template<unsigned DIM, class ForwardIterator >
math::Statistics	compute_positional_error_statistics (ForwardIterator original_first, ForwardIterator original_last, ForwardIterator simplified_first, ForwardIterator simplified_last, bool *valid=0)
	Computes statistics for the positional errors between a polyline and its simplification. More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	compute_positional_errors2 (ForwardIterator original_first, ForwardIterator original_last, ForwardIterator simplified_first, ForwardIterator simplified_last, OutputIterator result, bool *valid=0)
	Computes the squared positional error between a polyline and its simplification. More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_douglas_peucker (ForwardIterator first, ForwardIterator last, typename std::iterator_traits< ForwardIterator >::value_type tol, OutputIterator result)
	Performs Douglas-Peucker polyline simplification (DP). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_douglas_peucker_n (ForwardIterator first, ForwardIterator last, unsigned count, OutputIterator result)
	Performs a variant of Douglas-Peucker polyline simplification (DPn). More...

template<unsigned DIM, class BidirectionalIterator , class OutputIterator >
OutputIterator	simplify_lang (BidirectionalIterator first, BidirectionalIterator last, typename std::iterator_traits< BidirectionalIterator >::value_type tol, unsigned look_ahead, OutputIterator result)
	Performs Lang polyline simplification (LA). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_nth_point (ForwardIterator first, ForwardIterator last, unsigned n, OutputIterator result)
	Performs the nth point routine (NP). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_opheim (ForwardIterator first, ForwardIterator last, typename std::iterator_traits< ForwardIterator >::value_type min_tol, typename std::iterator_traits< ForwardIterator >::value_type max_tol, OutputIterator result)
	Performs Opheim polyline simplification (OP). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_perpendicular_distance (ForwardIterator first, ForwardIterator last, typename std::iterator_traits< ForwardIterator >::value_type tol, OutputIterator result)
	Performs the perpendicular distance routine (PD). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_perpendicular_distance (ForwardIterator first, ForwardIterator last, typename std::iterator_traits< ForwardIterator >::value_type tol, unsigned repeat, OutputIterator result)
	Repeatedly performs the perpendicular distance routine (PD). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_radial_distance (ForwardIterator first, ForwardIterator last, typename std::iterator_traits< ForwardIterator >::value_type tol, OutputIterator result)
	Performs the (radial) distance between points routine (RD). More...

template<unsigned DIM, class ForwardIterator , class OutputIterator >
OutputIterator	simplify_reumann_witkam (ForwardIterator first, ForwardIterator last, typename std::iterator_traits< ForwardIterator >::value_type tol, OutputIterator result)
	Performs Reumann-Witkam polyline simplification (RW). More...

Detailed Description

Root namespace of the polyline simplification library.

\mainpage psimpl - generic n-dimensional polyline simplification

    Author  - Elmar de Koning
    Support - edeko.nosp@m.ning.nosp@m.@gmai.nosp@m.l.co.nosp@m.m
    Website - http://psimpl.sf.net
    Article - http://www.codeproject.com/KB/recipes/PolylineSimplification.aspx
    License - MPL 1.1

<br<blockquote>

\section sec_psimpl psimpl

    'psimpl' is a c++ polyline simplification library that is generic, easy to use, and supports
    the following algorithms:

    Simplification
    + Nth point - A naive algorithm that keeps only each nth point
    + Distance between points - Removes successive points that are clustered together
    + Perpendicular distance - Removes points based on their distance to the line segment defined
      by their left and right neighbors
    + Reumann-Witkam - Shifts a strip along the polyline and removes points that fall outside
    + Opheim - A constrained version of Reumann-Witkam
    + Lang - Similar to the Perpendicular distance routine, but instead of looking only at direct
      neighbors, an entire search region is processed
    + Douglas-Peucker - A classic simplification algorithm that provides an excellent approximation
      of the original line
    + A variation on the Douglas-Peucker algorithm - Slower, but yields better results at lower resolutions

    Errors
    + positional error - Distance of each polyline point to its simplification

    All the algorithms have been implemented in a single standalone C++ header using an STL-style
    interface that operates on input and output iterators. Polylines can be of any dimension, and
    defined using floating point or signed integer data types.

<br<blockquote>

\section sec_changelog changelog

    28-09-2010 - Initial version
    23-10-2010 - Changed license from CPOL to MPL
    26-10-2010 - Clarified input (type) requirements, and changed the behavior of the algorithms
                 under invalid input
    01-12-2010 - Added the nth point, perpendicular distance and Reumann-Witkam routines; moved all
                 functions related to distance calculations to the math namespace
    10-12-2010 - Fixed a bug in the perpendicular distance routine
    27-02-2011 - Added Opheim simplification, and functions for computing positional errors due to
                 simplification; renamed simplify_douglas_peucker_alt to simplify_douglas_peucker_n
    18-06-2011 - Added Lang simplification; fixed divide by zero bug when using integers; fixed a
                 bug where incorrect output iterators were returned under invalid input; fixed a bug
                 in douglas_peucker_n where an incorrect number of points could be returned; fixed a
                 bug in compute_positional_errors2 that required the output and input iterator types
                 to be the same; fixed a bug in compute_positional_error_statistics where invalid
                 statistics could be returned under questionable input; documented input iterator
                 requirements for each algorithm; miscellaneous refactoring of most algorithms.

Function Documentation

◆ compute_positional_error_statistics()

template<unsigned DIM, class ForwardIterator >

math::Statistics psimpl::compute_positional_error_statistics	(	ForwardIterator	original_first,
		ForwardIterator	original_last,
		ForwardIterator	simplified_first,
		ForwardIterator	simplified_last,
		bool *	valid = `0`
	)

Computes statistics for the positional errors between a polyline and its simplification.

This is a convenience function that provides template type deduction for PolylineSimplification::ComputePositionalErrorStatistics.

Parameters

[in]	original_first	the first coordinate of the first polyline point
[in]	original_last	one beyond the last coordinate of the last polyline point
[in]	simplified_first	the first coordinate of the first simplified polyline point
[in]	simplified_last	one beyond the last coordinate of the last simplified polyline point
[out]	valid	[optional] indicates if the computed statistics are valid

Returns: the computed statistics

Definition at line 1878 of file psimpl.h.

◆ compute_positional_errors2()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::compute_positional_errors2	(	ForwardIterator	original_first,
		ForwardIterator	original_last,
		ForwardIterator	simplified_first,
		ForwardIterator	simplified_last,
		OutputIterator	result,
		bool *	valid = `0`
	)

Computes the squared positional error between a polyline and its simplification.

This is a convenience function that provides template type deduction for PolylineSimplification::ComputePositionalErrors2.

Parameters

[in]	original_first	the first coordinate of the first polyline point
[in]	original_last	one beyond the last coordinate of the last polyline point
[in]	simplified_first	the first coordinate of the first simplified polyline point
[in]	simplified_last	one beyond the last coordinate of the last simplified polyline point
[in]	result	destination of the squared positional errors
[out]	valid	[optional] indicates if the computed positional errors are valid

Returns: one beyond the last computed positional error

Definition at line 1852 of file psimpl.h.

◆ simplify_douglas_peucker()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_douglas_peucker	(	ForwardIterator	first,
		ForwardIterator	last,
		typename std::iterator_traits< ForwardIterator >::value_type	tol,
		OutputIterator	result
	)

Performs Douglas-Peucker polyline simplification (DP).

This is a convenience function that provides template type deduction for PolylineSimplification::DouglasPeucker.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	tol	perpendicular (point-to-segment) distance tolerance
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1804 of file psimpl.h.

◆ simplify_douglas_peucker_n()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_douglas_peucker_n	(	ForwardIterator	first,
		ForwardIterator	last,
		unsigned	count,
		OutputIterator	result
	)

Performs a variant of Douglas-Peucker polyline simplification (DPn).

This is a convenience function that provides template type deduction for PolylineSimplification::DouglasPeuckerAlt.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	count	the maximum number of points of the simplified polyline
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1827 of file psimpl.h.

◆ simplify_lang()

template<unsigned DIM, class BidirectionalIterator , class OutputIterator >

OutputIterator psimpl::simplify_lang	(	BidirectionalIterator	first,
		BidirectionalIterator	last,
		typename std::iterator_traits< BidirectionalIterator >::value_type	tol,
		unsigned	look_ahead,
		OutputIterator	result
	)

Performs Lang polyline simplification (LA).

This is a convenience function that provides template type deduction for PolylineSimplification::Lang.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	tol	perpendicular (point-to-segment) distance tolerance
[in]	look_ahead	defines the size of the search region
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1780 of file psimpl.h.

◆ simplify_nth_point()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_nth_point	(	ForwardIterator	first,
		ForwardIterator	last,
		unsigned	n,
		OutputIterator	result
	)

Performs the nth point routine (NP).

This is a convenience function that provides template type deduction for PolylineSimplification::NthPoint.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	n	specifies 'each nth point'
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1637 of file psimpl.h.

◆ simplify_opheim()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_opheim	(	ForwardIterator	first,
		ForwardIterator	last,
		typename std::iterator_traits< ForwardIterator >::value_type	min_tol,
		typename std::iterator_traits< ForwardIterator >::value_type	max_tol,
		OutputIterator	result
	)

Performs Opheim polyline simplification (OP).

This is a convenience function that provides template type deduction for PolylineSimplification::Opheim.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	min_tol	minimum distance tolerance
[in]	max_tol	maximum distance tolerance
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1755 of file psimpl.h.

◆ simplify_perpendicular_distance() [1/2]

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_perpendicular_distance	(	ForwardIterator	first,
		ForwardIterator	last,
		typename std::iterator_traits< ForwardIterator >::value_type	tol,
		OutputIterator	result
	)

Performs the perpendicular distance routine (PD).

This is a convenience function that provides template type deduction for PolylineSimplification::PerpendicularDistance.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	tol	perpendicular (segment-to-point) distance tolerance
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1708 of file psimpl.h.

◆ simplify_perpendicular_distance() [2/2]

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_perpendicular_distance	(	ForwardIterator	first,
		ForwardIterator	last,
		typename std::iterator_traits< ForwardIterator >::value_type	tol,
		unsigned	repeat,
		OutputIterator	result
	)

Repeatedly performs the perpendicular distance routine (PD).

This is a convenience function that provides template type deduction for PolylineSimplification::PerpendicularDistance.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	tol	perpendicular (segment-to-point) distance tolerance
[in]	repeat	the number of times to successively apply the PD routine.
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1684 of file psimpl.h.

◆ simplify_radial_distance()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_radial_distance	(	ForwardIterator	first,
		ForwardIterator	last,
		typename std::iterator_traits< ForwardIterator >::value_type	tol,
		OutputIterator	result
	)

Performs the (radial) distance between points routine (RD).

This is a convenience function that provides template type deduction for PolylineSimplification::RadialDistance.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	tol	radial (point-to-point) distance tolerance
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1660 of file psimpl.h.

◆ simplify_reumann_witkam()

template<unsigned DIM, class ForwardIterator , class OutputIterator >

OutputIterator psimpl::simplify_reumann_witkam	(	ForwardIterator	first,
		ForwardIterator	last,
		typename std::iterator_traits< ForwardIterator >::value_type	tol,
		OutputIterator	result
	)

Performs Reumann-Witkam polyline simplification (RW).

This is a convenience function that provides template type deduction for PolylineSimplification::ReumannWitkam.

Parameters

[in]	first	the first coordinate of the first polyline point
[in]	last	one beyond the last coordinate of the last polyline point
[in]	tol	perpendicular (point-to-line) distance tolerance
[in]	result	destination of the simplified polyline

Returns: one beyond the last coordinate of the simplified polyline

Definition at line 1731 of file psimpl.h.

Namespaces

Classes

Functions

Detailed Description

Function Documentation

◆ compute_positional_error_statistics()

◆ compute_positional_errors2()

◆ simplify_douglas_peucker()

◆ simplify_douglas_peucker_n()

◆ simplify_lang()

◆ simplify_nth_point()

◆ simplify_opheim()

◆ simplify_perpendicular_distance() [1/2]

◆ simplify_perpendicular_distance() [2/2]

◆ simplify_radial_distance()

◆ simplify_reumann_witkam()