Data Structures | Public Types | Public Member Functions | Protected Member Functions | Private Types | Private Member Functions | Private Attributes

DGtal::Preimage2D< Shape > Class Template Reference

Aim: Computes the preimage of the 2D Euclidean shapes crossing a sequence of straigth segments in linear-time according to the algorithm of O'Rourke (1981). More...

#include <Preimage2D.h>

Data Structures

struct  selfDrawStyle

Public Types

typedef Shape::Coordinate CoordinateType
typedef DGtal::PointVector
< 2, CoordinateType
Point
typedef DGtal::PointVector
< 2, CoordinateType
Vector

Public Member Functions

 Preimage2D (const Point &firstPoint, const Point &secondPoint)
 ~Preimage2D ()
bool addFront (const Point &aP, const Point &aQ)
void selfDisplay (std::ostream &out) const
bool isValid () const
template<typename Functor >
void selfDraw (LibBoard::Board &board) const
void selfDraw (LibBoard::Board &board) const

Protected Member Functions

 Preimage2D ()

Private Types

typedef std::list< PointContainer
typedef std::list< Point >
::iterator 
ForwardIterator
typedef std::list< Point >
::reverse_iterator 
BackwardIterator
typedef std::list< Point >
::const_iterator 
ConstForwardIterator
typedef std::list< Point >
::const_reverse_iterator 
ConstBackwardIterator
typedef Point2ShapePredicate
< Shape, false, true > 
PHullBackQHullFrontPred
typedef Point2ShapePredicate
< Shape, true, true > 
QHullBackPHullFrontPred
typedef Point2ShapePredicate
< Shape, true, false > 
PHullUpdateForPAddingPred
typedef Point2ShapePredicate
< Shape, false, false > 
QHullUpdateForQAddingPred
typedef Point2ShapePredicate
< Shape, false, false > 
QHullUpdateForPAddingPred
typedef Point2ShapePredicate
< Shape, true, false > 
PHullUpdateForQAddingPred

Private Member Functions

template<typename Iterator , typename Predicate >
void update (const Point &aPoint, Container &aContainer, Iterator &anIterator, const Iterator &anEndIterator)
 Preimage2D (const Preimage2D &other)
Preimage2Doperator= (const Preimage2D &other)

Private Attributes

Container myPHull
Container myQHull

Detailed Description

template<typename Shape>
class DGtal::Preimage2D< Shape >

Aim: Computes the preimage of the 2D Euclidean shapes crossing a sequence of straigth segments in linear-time according to the algorithm of O'Rourke (1981).

Description of template class 'Preimage2D'

The straight segment i is described by its two end points Pi and Qi. The set of shapes considered here are those that can be uniquely defined by two points and that separate the 2D plane into two disjoint parts (e.g. straight lines, circles passing through a given point). Consequently, the points Pi and the points Qi are assumed to lie in either side of the shape. Nb: The user of this class has to decide from its input set of segments and the shape used whether a linear-time algorithm is possible or not. (if yes - e.g. preimage of straight lines crossing a set of vertical segments of increasing x-coordinate - this algorithm will return the right output).

   typedef int Coordinate;
   typedef PointVector<2, Coordinate> Point;
   typedef StraightLine<Coordinate> StraightLine;
   typedef Preimage2D<StraightLine> Preimage2D;
   
   // Set input data segments as two vectors of endpoints.   
   std::vector<Point> P, Q;
   
   Q.push_back(Point(0, 10));
   Q.push_back(Point(1, 11));
   Q.push_back(Point(2, 11));
   Q.push_back(Point(3, 12));
   
   P.push_back(Point(0, 12));
   P.push_back(Point(1, 13));
   P.push_back(Point(2, 13));
   P.push_back(Point(3, 14));
   
   // Initialization 
   int i = 0;
   Preimage2D thePreimage(bInf.at(i), bSup.at(i));
   
   // Incremental computation of the preimage
   while ( (i < n) &&
   (thePreimage.addFront(bInf.at(i), bSup.at(i))) )
   {
     i++;
   }
   std::cout << thePreimage << std::endl;

Member Typedef Documentation

template<typename Shape >
typedef std::list<Point>::reverse_iterator DGtal::Preimage2D< Shape >::BackwardIterator [private]
template<typename Shape >
typedef std::list<Point>::const_reverse_iterator DGtal::Preimage2D< Shape >::ConstBackwardIterator [private]
template<typename Shape >
typedef std::list<Point>::const_iterator DGtal::Preimage2D< Shape >::ConstForwardIterator [private]
template<typename Shape >
typedef std::list<Point> DGtal::Preimage2D< Shape >::Container [private]
template<typename Shape >
typedef Shape::Coordinate DGtal::Preimage2D< Shape >::CoordinateType
template<typename Shape >
typedef std::list<Point>::iterator DGtal::Preimage2D< Shape >::ForwardIterator [private]
template<typename Shape >
typedef Point2ShapePredicate<Shape,false,true> DGtal::Preimage2D< Shape >::PHullBackQHullFrontPred [private]
template<typename Shape >
typedef Point2ShapePredicate<Shape,true,false> DGtal::Preimage2D< Shape >::PHullUpdateForPAddingPred [private]
template<typename Shape >
typedef Point2ShapePredicate<Shape,true,false> DGtal::Preimage2D< Shape >::PHullUpdateForQAddingPred [private]
template<typename Shape >
typedef DGtal::PointVector<2,CoordinateType> DGtal::Preimage2D< Shape >::Point
template<typename Shape >
typedef Point2ShapePredicate<Shape,true,true> DGtal::Preimage2D< Shape >::QHullBackPHullFrontPred [private]
template<typename Shape >
typedef Point2ShapePredicate<Shape,false,false> DGtal::Preimage2D< Shape >::QHullUpdateForPAddingPred [private]
template<typename Shape >
typedef Point2ShapePredicate<Shape,false,false> DGtal::Preimage2D< Shape >::QHullUpdateForQAddingPred [private]
template<typename Shape >
typedef DGtal::PointVector<2,CoordinateType> DGtal::Preimage2D< Shape >::Vector

Constructor & Destructor Documentation

template<typename Shape >
DGtal::Preimage2D< Shape >::Preimage2D ( const Point firstPoint,
const Point secondPoint 
)

Constructor.

Parameters:
firstPoint,secondPoint,the two end points of the first straight segment
template<typename Shape >
DGtal::Preimage2D< Shape >::~Preimage2D (  ) 

Destructor. Does nothing.

template<typename Shape >
DGtal::Preimage2D< Shape >::Preimage2D (  )  [protected]

Constructor. Forbidden by default (protected to avoid g++ warnings).

template<typename Shape >
DGtal::Preimage2D< Shape >::Preimage2D ( const Preimage2D< Shape > &  other  )  [private]

Copy constructor.

Parameters:
other the object to clone. Forbidden by default.

Member Function Documentation

template<typename Shape >
bool DGtal::Preimage2D< Shape >::addFront ( const Point aP,
const Point aQ 
)

Updates the current preimage with the constraints involved by the two end points of a new segment (adding to the front of the sequence of segments with respect to the scan orientaion e.g. back => seg1 => ... segn => front) Nb: in O(n)

Parameters:
aP,aQ,the two ends of the new straight segment assumed to lie on either side of the shapes.
Returns:
'false' if the updated preimage is empty, 'true' otherwise.
template<typename Shape >
bool DGtal::Preimage2D< Shape >::isValid (  )  const

Checks the validity/consistency of the object.

Returns:
'true' if the object is valid, 'false' otherwise.
template<typename Shape >
Preimage2D& DGtal::Preimage2D< Shape >::operator= ( const Preimage2D< Shape > &  other  )  [private]

Assignment.

Parameters:
other the object to copy.
Returns:
a reference on 'this'. Forbidden by default.
template<typename Shape >
void DGtal::Preimage2D< Shape >::selfDisplay ( std::ostream &  out  )  const

Writes/Displays the object on an output stream.

Parameters:
out the output stream where the object is written.
template<typename Shape >
template<typename Functor >
void DGtal::Preimage2D< Shape >::selfDraw ( LibBoard::Board board  )  const

Draw the preimage

Parameters:
board the output board where the object is drawn.
Template Parameters:
Functor a Functor to specialize the Board style
template<typename Shape >
void DGtal::Preimage2D< Shape >::selfDraw ( LibBoard::Board board  )  const [inline]

Draw the preimage on a LiBoard board

Parameters:
board the output board where the object is drawn.
Template Parameters:
Functor a Functor to specialize the Board style
template<typename Shape >
template<typename Iterator , typename Predicate >
void DGtal::Preimage2D< Shape >::update ( const Point aPoint,
Container aContainer,
Iterator &  anIterator,
const Iterator &  anEndIterator 
) [private]

Updates the current preimage Nb: in O(n)

Parameters:
aPoint a new vertex of the preimage, aContainer the container to be updated, anIterator an iterator to its front (resp. back) anEndIterator an iterator pointing after its back (resp. before its front).

Field Documentation

template<typename Shape >
Container DGtal::Preimage2D< Shape >::myPHull [private]
template<typename Shape >
Container DGtal::Preimage2D< Shape >::myQHull [private]

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