DGtal  1.5.beta
Public Types | Public Member Functions | Private Attributes
DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor > Class Template Reference

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: [90]]. More...

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

Inheritance diagram for DGtal::MelkmanConvexHull< TPoint, TOrientationFunctor >:
[legend]

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
 
size_t 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: [90]].

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
TPointa model of point
TOrientationFunctora 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
mchthe 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
aPointan 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
mchthe 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
ithe 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
outthe output stream where the object is written.

◆ size()

template<typename TPoint , typename TOrientationFunctor >
size_t 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: