Aim: This class implements the on-line algorithm of Melkman for the computation of the convex hull of a simple polygonal line (without self-intersection) [Melkman, 1987: [85]]. More...

#include <DGtal/geometry/tools/MelkmanConvexHull.h>

Public Types
typedef MelkmanConvexHull< TPoint, TOrientationFunctor >	Self

typedef TPoint	Point

typedef TOrientationFunctor	Functor

typedef PredicateFromOrientationFunctor2< Functor, false, false >	BackwardPredicate

typedef PredicateFromOrientationFunctor2< Functor, true, false >	ForwardPredicate

typedef std::deque< Point >::const_iterator	ConstIterator

Public Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::COrientationFunctor2< Functor >))

	BOOST_STATIC_ASSERT ((boost::is_same< Point, typename Functor::Point >::value))

	MelkmanConvexHull (Alias< Functor > aFunctor)

	MelkmanConvexHull ()

	MelkmanConvexHull (const MelkmanConvexHull &mch)=default

void	add (const Point &aPoint)

ConstIterator	begin () const

ConstIterator	end () const

void	selfDisplay (std::ostream &out) const

bool	isValid () const

Self &	operator= (const Self &mch)

const Point &	operator[] (unsigned int i) const

unsigned int	size () const

void	clear ()

void	reverse ()

Private Attributes
std::deque< Point >	myContainer

BackwardPredicate	myBackwardPredicate

ForwardPredicate	myForwardPredicate

Functor	myDefaultFunctor

Point	myFirstPoint

Detailed Description

template<typename TPoint, typename TOrientationFunctor>
class DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >

Aim: This class implements the on-line algorithm of Melkman for the computation of the convex hull of a simple polygonal line (without self-intersection) [Melkman, 1987: [85]].

This algorithm is based on a deque, which stores the vertices of the convex hull (for convenience, the first and last vertex contained in the deque are the same point). Since we assume that the input points form a simple polygonal line, a new point cannot be located in the cone formed by the first and last edges of the current convex hull. As a consequence, it is enough to update the convex hull by a Graham scan from the front and/or from the back of the deque; it is never required to remove/insert points in the middle of the container. See Convex hull and alpha-shape in the plane for more details.

See also: functions::Hull2D::updateHullWithAdaptedStack

Note that if the input points do not form a simple polygonal line, the behavior is not defined.

Template Parameters

TPoint	a model of point
TOrientationFunctor	a model of COrientationFunctor2 (whose inner type 'Point' match to 'TPoint')

Examples: geometry/tools/exampleConvexHull2D.cpp.

Definition at line 89 of file MelkmanConvexHull.h.

Member Typedef Documentation

◆ BackwardPredicate

template<typename TPoint , typename TOrientationFunctor >

typedef PredicateFromOrientationFunctor2<Functor,false,false> DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::BackwardPredicate

Type of predicate devoted to the backward scan

Definition at line 114 of file MelkmanConvexHull.h.

◆ ConstIterator

template<typename TPoint , typename TOrientationFunctor >

typedef std::deque<Point>::const_iterator DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::ConstIterator

Type of iterator on the convex hull vertices

Definition at line 123 of file MelkmanConvexHull.h.

◆ ForwardPredicate

template<typename TPoint , typename TOrientationFunctor >

typedef PredicateFromOrientationFunctor2<Functor,true,false> DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::ForwardPredicate

Type of predicate devoted to the forward scan

Definition at line 118 of file MelkmanConvexHull.h.

◆ Functor

template<typename TPoint , typename TOrientationFunctor >

typedef TOrientationFunctor DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::Functor

Type of orientation functor

Definition at line 106 of file MelkmanConvexHull.h.

◆ Point

template<typename TPoint , typename TOrientationFunctor >

typedef TPoint DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::Point

Type of point

Definition at line 102 of file MelkmanConvexHull.h.

◆ Self

template<typename TPoint , typename TOrientationFunctor >

typedef MelkmanConvexHull<TPoint, TOrientationFunctor> DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::Self

Self type

Definition at line 97 of file MelkmanConvexHull.h.

Constructor & Destructor Documentation

◆ MelkmanConvexHull() [1/3]

template<typename TPoint , typename TOrientationFunctor >

DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::MelkmanConvexHull ( Alias< Functor > aFunctor )

◆ MelkmanConvexHull() [2/3]

template<typename TPoint , typename TOrientationFunctor >

DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::MelkmanConvexHull ( )

◆ MelkmanConvexHull() [3/3]

template<typename TPoint , typename TOrientationFunctor >

DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::MelkmanConvexHull ( const MelkmanConvexHull< TPoint, TOrientationFunctor > & mch )

default

Default copy constructor.

Parameters

mch	the object to copy.

Member Function Documentation

◆ add()

template<typename TPoint , typename TOrientationFunctor >

void DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::add ( const Point & aPoint )

Consider a new point and possibly update the convex hull.

Parameters

aPoint an extra point

Postcondition: if aPoint lies outside the current convex hull, this hull is then updated with aPoint as a vertex.

◆ begin()

template<typename TPoint , typename TOrientationFunctor >

ConstIterator DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::begin ( ) const

Begin iterator

Returns: either a const iterator pointing past-the-end if the container is empty or a const iterator pointing after the first point otherwise. Rationale: we do not want to iterate over the same point, duplicated at the begin and at the end of the container.

◆ BOOST_CONCEPT_ASSERT()

template<typename TPoint , typename TOrientationFunctor >

DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::BOOST_CONCEPT_ASSERT ( (concepts::COrientationFunctor2< Functor >) )

◆ BOOST_STATIC_ASSERT()

template<typename TPoint , typename TOrientationFunctor >

DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::BOOST_STATIC_ASSERT ( (boost::is_same< Point, typename Functor::Point >::value) )

◆ clear()

template<typename TPoint , typename TOrientationFunctor >

void DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::clear ( )

clear the current content of the convex hull.

◆ end()

template<typename TPoint , typename TOrientationFunctor >

ConstIterator DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::end ( ) const

End iterator

Returns: a const iterator to the end of the container

◆ isValid()

template<typename TPoint , typename TOrientationFunctor >

bool DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::isValid ( ) const

Checks the validity/consistency of the object.

Returns: 'true' if the object is valid, 'false' otherwise.

◆ operator=()

template<typename TPoint , typename TOrientationFunctor >

Self & DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::operator= ( const Self & mch )

Assignement Operator

Parameters

mch	the object to copy.

Returns: a reference on 'this'.

◆ operator[]()

template<typename TPoint , typename TOrientationFunctor >

const Point & DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::operator[] ( unsigned int i ) const

Returns: the i-th point of the convex hull queue.

Parameters

i	the index of the considered point.

◆ reverse()

template<typename TPoint , typename TOrientationFunctor >

void DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::reverse ( )

Reverse the convex hull container allowing to change the order of adding points from the front or from the back in reference to an input contour. Such a reverse is important to avoid wrong convexhull and to allow convex hull extension from two directions.

◆ selfDisplay()

template<typename TPoint , typename TOrientationFunctor >

void DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

◆ size()

template<typename TPoint , typename TOrientationFunctor >

unsigned int DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::size ( ) const

Returns: the nomber of points constituing the convex hull.

Field Documentation

◆ myBackwardPredicate

template<typename TPoint , typename TOrientationFunctor >

BackwardPredicate DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::myBackwardPredicate

private

Predicate devoted to the backward scan

Definition at line 220 of file MelkmanConvexHull.h.

◆ myContainer

template<typename TPoint , typename TOrientationFunctor >

std::deque<Point> DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::myContainer

private

Deque container, which stores the vertices of the convex hull NB: the first and last point is the same.

Definition at line 216 of file MelkmanConvexHull.h.

◆ myDefaultFunctor

template<typename TPoint , typename TOrientationFunctor >

Functor DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::myDefaultFunctor

private

Used to define a default functor to allow default constructor

Definition at line 228 of file MelkmanConvexHull.h.

◆ myFirstPoint

template<typename TPoint , typename TOrientationFunctor >

Point DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::myFirstPoint

private

first point used to reverse the convexhull container.

Definition at line 232 of file MelkmanConvexHull.h.

◆ myForwardPredicate

template<typename TPoint , typename TOrientationFunctor >

ForwardPredicate DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >::myForwardPredicate

private

Predicate devoted to the forward scan

Definition at line 224 of file MelkmanConvexHull.h.

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

MelkmanConvexHull.h

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ BackwardPredicate

◆ ConstIterator

◆ ForwardPredicate

◆ Functor

◆ Point

◆ Self

Constructor & Destructor Documentation

◆ MelkmanConvexHull() [1/3]

◆ MelkmanConvexHull() [2/3]

◆ MelkmanConvexHull() [3/3]

Member Function Documentation

◆ add()

◆ begin()

◆ BOOST_CONCEPT_ASSERT()

◆ BOOST_STATIC_ASSERT()

◆ clear()

◆ end()

◆ isValid()

◆ operator=()

◆ operator[]()

◆ reverse()

◆ selfDisplay()

◆ size()

Field Documentation

◆ myBackwardPredicate

◆ myContainer

◆ myDefaultFunctor

◆ myFirstPoint

◆ myForwardPredicate