Aleph::DouglasPeuckerSimplification Class Reference

Douglas-Peucker polyline simplification. More...

#include <geom_algorithms.H>

Public Member Functions
Array< Point >	operator() (const Array< Point > &polyline, const Geom_Number &epsilon) const
	Simplify an open polyline.
Array< Point >	operator() (const DynList< Point > &polyline, const Geom_Number &epsilon) const
	Overload accepting DynList.
Polygon	simplify_polygon (const Polygon &poly, const Geom_Number &epsilon) const
	Simplify a closed polygon.

Static Private Member Functions
static void	dp_recurse (const Array< Point > &pts, const size_t first, const size_t last, const Geom_Number &eps2, Array< bool > &keep)

Detailed Description

Douglas-Peucker polyline simplification.

Recursively splits the polyline at the vertex farthest from the line connecting the current endpoints. Vertices closer than epsilon to the connecting line are discarded.

• Open polyline: first and last vertex are always kept.
• Closed polygon: the vertex farthest from vertex 0 is used to split the ring into two open chains, each simplified independently.

Complexity: O(n log n) average, O(n²) worst case.

Definition at line 12421 of file geom_algorithms.H.

Member Function Documentation

dp_recurse()

static void Aleph::DouglasPeuckerSimplification::dp_recurse ( const Array< Point > &  pts, const size_t  first, const size_t  last, const Geom_Number &  eps2, Array< bool > &  keep  )

inlinestaticprivate

Definition at line 12423 of file geom_algorithms.H.

References Aleph::Segment::distance_to(), Aleph::divide_and_conquer_partition_dp(), and dp_recurse().

Referenced by dp_recurse(), and operator()().

operator()() [1/2]

Array< Point > Aleph::DouglasPeuckerSimplification::operator() ( const Array< Point > &  polyline, const Geom_Number &  epsilon  ) const

inline

Simplify an open polyline.

First and last vertices are always kept.

Parameters

polyline	Ordered sequence of vertices.
epsilon	Maximum perpendicular distance tolerance.

Returns

Simplified vertex array (subsequence of polyline).

Definition at line 12463 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), and dp_recurse().

operator()() [2/2]

Array< Point > Aleph::DouglasPeuckerSimplification::operator() ( const DynList< Point > &  polyline, const Geom_Number &  epsilon  ) const

inline

Overload accepting DynList.

Definition at line 12489 of file geom_algorithms.H.

References Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), and Aleph::HTList::Iterator::has_curr().

simplify_polygon()

Polygon Aleph::DouglasPeuckerSimplification::simplify_polygon ( const Polygon &  poly, const Geom_Number &  epsilon  ) const

inline

Simplify a closed polygon.

Splits the polygon ring at the vertex farthest from vertex 0, simplifies each open chain, and merges the results.

Parameters

poly	The closed polygon.
epsilon	Maximum perpendicular distance tolerance.

Returns

A new polygon with fewer vertices.

Definition at line 12510 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), Aleph::Array< T >::append(), Aleph::Polygon::close(), Aleph::divide_and_conquer_partition_dp(), and Aleph::GeomPolygonUtils::extract_vertices().

Referenced by main(), TEST_F(), TEST_F(), and TEST_F().

---

The documentation for this class was generated from the following file:

• geom_algorithms.H