Visvalingam-Whyatt polyline simplification. More...

#include <geom_algorithms.H>

Classes
struct	VWEntry
	Entry in the priority queue for vertex removal. More...

Public Member Functions
Array< Point >	operator() (const Array< Point > &polyline, const Geom_Number &area_threshold) const
	Simplify an open polyline.

Array< Point >	operator() (const DynList< Point > &polyline, const Geom_Number &area_threshold) const
	Overload accepting DynList.

Static Public Member Functions
static Polygon	simplify_polygon (const Polygon &poly, const Geom_Number &area_threshold)
	Simplify a closed polygon.

Static Private Member Functions
static Geom_Number	effective_area (const Point &a, const Point &b, const Point &c)

static Array< Point >	simplify_open_array (const Array< Point > &polyline, const Geom_Number &area_threshold)

Detailed Description

Visvalingam-Whyatt polyline simplification.

Iteratively removes the vertex that forms the smallest effective area triangle with its two neighbors. Uses a min-heap for O(n log n) complexity.

Open polyline: first and last vertex are never removed.
Closed polygon: all vertices are candidates; cyclic neighbor links.

Definition at line 12575 of file geom_algorithms.H.

Member Function Documentation

◆ effective_area()

static Geom_Number Aleph::VisvalingamWhyattSimplification::effective_area	(	const Point &	a,
		const Point &	b,
		const Point &	c
	)

inlinestaticprivate

Definition at line 12592 of file geom_algorithms.H.

References Aleph::area_of_parallelogram(), and Aleph::divide_and_conquer_partition_dp().

Referenced by simplify_open_array(), and simplify_polygon().

◆ operator()() [1/2]

Array< Point > Aleph::VisvalingamWhyattSimplification::operator()	(	const Array< Point > &	polyline,
		const Geom_Number &	area_threshold
	)		const

inline

Simplify an open polyline.

First and last vertices are always kept.

Parameters

polyline	Ordered sequence of vertices.
area_threshold	Minimum effective area to keep a vertex.

Returns: Simplified vertex array (subsequence of polyline).

Definition at line 12687 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and simplify_open_array().

◆ operator()() [2/2]

Array< Point > Aleph::VisvalingamWhyattSimplification::operator()	(	const DynList< Point > &	polyline,
		const Geom_Number &	area_threshold
	)		const

inline

Overload accepting DynList.

Definition at line 12695 of file geom_algorithms.H.

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

◆ simplify_open_array()

static Array< Point > Aleph::VisvalingamWhyattSimplification::simplify_open_array	(	const Array< Point > &	polyline,
		const Geom_Number &	area_threshold
	)

inlinestaticprivate

Definition at line 12600 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), effective_area(), Aleph::DynBinHeap< T, Compare >::get(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), Aleph::next(), and Aleph::DynBinHeap< T, Compare >::put().

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

◆ simplify_polygon()

static Polygon Aleph::VisvalingamWhyattSimplification::simplify_polygon	(	const Polygon &	poly,
		const Geom_Number &	area_threshold
	)

inlinestatic

Simplify a closed polygon.

All vertices are candidates (cyclic neighbor links).

Parameters

poly	The closed polygon.
area_threshold	Minimum effective area to keep a vertex.

Returns: A new polygon with fewer vertices.

Definition at line 12715 of file geom_algorithms.H.

References Aleph::Polygon::add_vertex(), Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), effective_area(), Aleph::GeomPolygonUtils::extract_vertices(), Aleph::DynBinHeap< T, Compare >::get(), Aleph::GenBinHeap< NodeType, Key, Compare >::is_empty(), Aleph::next(), Aleph::DynBinHeap< T, Compare >::put(), and Aleph::Array< T >::size().

Referenced by TEST_F().

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

geom_algorithms.H

Classes

Public Member Functions

Static Public Member Functions