DGtal  1.5.beta
DGtal::Preimage2D< Shape > Class Template Reference

Aim: Computes the preimage of the 2D Euclidean shapes crossing a sequence of n straigth segments in O(n), with the algorithm of O'Rourke (1981). More...

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

Public Types

typedef Shape::Point Point
 
typedef Shape::Point Vector
 
typedef std::list< PointContainer
 

Public Member Functions

 Preimage2D (const Point &firstPoint, const Point &secondPoint, const Shape &aShape)
 
 ~Preimage2D ()
 
 Preimage2D (const Preimage2D &other)
 
Preimage2Doperator= (const Preimage2D &other)
 
bool operator== (const Preimage2D &other) const
 
bool operator!= (const Preimage2D &other) const
 
bool isLeftExteriorAtTheFront (const Point &aP, const Point &aQ)
 
bool isLeftExteriorAtTheBack (const Point &aP, const Point &aQ)
 
bool isRightExteriorAtTheFront (const Point &aP, const Point &aQ)
 
bool isRightExteriorAtTheBack (const Point &aP, const Point &aQ)
 
bool canBeAddedAtTheFront (const Point &aP, const Point &aQ)
 
bool canBeAddedAtTheBack (const Point &aP, const Point &aQ)
 
bool addFront (const Point &aP, const Point &aQ)
 
bool addBack (const Point &aP, const Point &aQ)
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 
Point Uf () const
 
Point Ul () const
 
Point Lf () const
 
Point Ll () const
 
void getSeparatingStraightLine (double &alpha, double &beta, double &gamma) const
 
const Shapeshape () const
 
const ContainerpHull () const
 
const ContainerqHull () const
 
std::string className () const
 

Private Types

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 functors::Point2ShapePredicate< Shape, false, true > PHullBackQHullFrontPred
 
typedef functors::Point2ShapePredicate< Shape, true, true > QHullBackPHullFrontPred
 
typedef functors::Point2ShapePredicate< Shape, true, true > PHullFrontQHullBackPred
 
typedef functors::Point2ShapePredicate< Shape, false, true > QHullFrontPHullBackPred
 
typedef functors::Point2ShapePredicate< Shape, true, false > FrontPHullUpdatePred
 
typedef functors::Point2ShapePredicate< Shape, false, false > FrontQHullUpdatePred
 
typedef functors::Point2ShapePredicate< Shape, false, false > BackPHullUpdatePred
 
typedef functors::Point2ShapePredicate< Shape, true, false > BackQHullUpdatePred
 

Private Member Functions

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

Private Attributes

Shape myShape
 
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 n straigth segments in O(n), with the algorithm of O'Rourke (1981).

Note
Joseph O'Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM, Volume 24, Issue 9, September 1981, 574–578.

For all i from 0 to n, 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.

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) the algorithm of O'Rourke will return the right output.

Template Parameters
Shapea model of COrientableHypersurface

You can define your preimage type from a given shape type as follows:

typedef StraightLineFrom2Points<Curve::Point> StraightLine;
StraightLine aStraightLine; //instance of straight line
typedef Preimage2D<StraightLine> Preimage2D;
Preimage2D(const Point &firstPoint, const Point &secondPoint, const Shape &aShape)

Here is another example:

typedef CircleFrom2Points<Curve::Point> Circle;
Circle aCircle( pole ); //instance of circle passing through point 'pole'
typedef Preimage2D<Circle> Preimage2D;

Then, here is the basic usage of this class:

Curve::IncidentPointsRange r = c.getIncidentPointsRange(); //range
Curve::IncidentPointsRange::ConstIterator it (r.begin()); //iterators
//preimage computation
Preimage2D thePreimage(it->first, it->second, aStraightLine);
++it;
while ( (it != itEnd) &&
(thePreimage.addFront(it->first, it->second)) )
{
++it;
}
trace.info() << thePreimage << endl;
//display
Board2D board;
board.setUnit(Board2D::UCentimeter);
board << r << thePreimage;
board.saveEPS( "PreimageExample.eps" );
std::ostream & info()
MyDigitalSurface::ConstIterator ConstIterator
Trace trace
Definition: Common.h:153
See also
examplePreimage.cpp testPreimage.cpp

Definition at line 93 of file Preimage2D.h.

Member Typedef Documentation

◆ BackPHullUpdatePred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,false,false> DGtal::Preimage2D< Shape >::BackPHullUpdatePred
private

Definition at line 130 of file Preimage2D.h.

◆ BackQHullUpdatePred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,true,false> DGtal::Preimage2D< Shape >::BackQHullUpdatePred
private

Definition at line 132 of file Preimage2D.h.

◆ BackwardIterator

template<typename Shape >
typedef std::list<Point>::reverse_iterator DGtal::Preimage2D< Shape >::BackwardIterator
private

Definition at line 110 of file Preimage2D.h.

◆ ConstBackwardIterator

template<typename Shape >
typedef std::list<Point>::const_reverse_iterator DGtal::Preimage2D< Shape >::ConstBackwardIterator
private

Definition at line 112 of file Preimage2D.h.

◆ ConstForwardIterator

template<typename Shape >
typedef std::list<Point>::const_iterator DGtal::Preimage2D< Shape >::ConstForwardIterator
private

Definition at line 111 of file Preimage2D.h.

◆ Container

template<typename Shape >
typedef std::list<Point> DGtal::Preimage2D< Shape >::Container

Definition at line 103 of file Preimage2D.h.

◆ ForwardIterator

template<typename Shape >
typedef std::list<Point>::iterator DGtal::Preimage2D< Shape >::ForwardIterator
private

Definition at line 109 of file Preimage2D.h.

◆ FrontPHullUpdatePred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,true,false> DGtal::Preimage2D< Shape >::FrontPHullUpdatePred
private

Definition at line 126 of file Preimage2D.h.

◆ FrontQHullUpdatePred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,false,false> DGtal::Preimage2D< Shape >::FrontQHullUpdatePred
private

Definition at line 128 of file Preimage2D.h.

◆ PHullBackQHullFrontPred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,false,true> DGtal::Preimage2D< Shape >::PHullBackQHullFrontPred
private

Definition at line 117 of file Preimage2D.h.

◆ PHullFrontQHullBackPred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,true,true> DGtal::Preimage2D< Shape >::PHullFrontQHullBackPred
private

Definition at line 121 of file Preimage2D.h.

◆ Point

template<typename Shape >
typedef Shape::Point DGtal::Preimage2D< Shape >::Point

Definition at line 100 of file Preimage2D.h.

◆ QHullBackPHullFrontPred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,true,true> DGtal::Preimage2D< Shape >::QHullBackPHullFrontPred
private

Definition at line 119 of file Preimage2D.h.

◆ QHullFrontPHullBackPred

template<typename Shape >
typedef functors::Point2ShapePredicate<Shape,false,true> DGtal::Preimage2D< Shape >::QHullFrontPHullBackPred
private

Definition at line 123 of file Preimage2D.h.

◆ Vector

template<typename Shape >
typedef Shape::Point DGtal::Preimage2D< Shape >::Vector

Definition at line 101 of file Preimage2D.h.

Constructor & Destructor Documentation

◆ Preimage2D() [1/2]

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

Constructor.

Parameters
firstPointthe end point of the first straight segment expected to lie in the interior of the separating shapes
secondPointthe end point of the first straight segment expected to lie in the exterior of the separating shapes
aShapeany shape

◆ ~Preimage2D()

template<typename Shape >
DGtal::Preimage2D< Shape >::~Preimage2D ( )

Destructor. Does nothing.

◆ Preimage2D() [2/2]

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

Copy constructor.

Parameters
otherthe object to clone.

Member Function Documentation

◆ addBack()

template<typename Shape >
bool DGtal::Preimage2D< Shape >::addBack ( 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 back with respect to a clockwise-oriented scan)

Nb: in O(n)

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'false' if the updated preimage is empty, 'true' otherwise.

Referenced by main().

◆ addFront()

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 with respect to a clockwise-oriented scan)

Nb: in O(n)

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'false' if the updated preimage is empty, 'true' otherwise.

Referenced by main().

◆ canBeAddedAtTheBack()

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

Decide whether a new constraint can be added at the back (with respect to a clockwise-oriented scan) without making the preimage empty or not

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'false' if the new constraint make the preimage empty 'true' otherwise.

◆ canBeAddedAtTheFront()

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

Decide whether a new constraint can be added at the front (with respect to a clockwise-oriented scan) without making the preimage empty or not

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'false' if the new constraint make the preimage empty 'true' otherwise.

◆ className()

template<typename Shape >
std::string DGtal::Preimage2D< Shape >::className ( ) const

Default drawing style object.

Returns
the dyn. alloc. default style for this object.
the style name used for drawing this object.

◆ getSeparatingStraightLine()

template<typename Shape >
void DGtal::Preimage2D< Shape >::getSeparatingStraightLine ( double &  alpha,
double &  beta,
double &  gamma 
) const

Get the parameters of one separating straight line

Parameters
alpha(returned) y-component of the normal
beta(returned) x-component of the normal
gamma(returned) intercept

◆ isLeftExteriorAtTheBack()

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

Decide whether a new constraint that is added at the back (with respect to a clockwise-oriented scan) makes the preimage empty because of point aQ or not

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'true' if the new constraint makes the preimage empty because of point aQ and 'false' otherwise.

◆ isLeftExteriorAtTheFront()

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

Decide whether a new constraint that is added at the front (with respect to a clockwise-oriented scan) makes the preimage empty because of point aP or not

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'true' if the new constraint makes the preimage empty because of point aP and 'false' otherwise.

◆ isRightExteriorAtTheBack()

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

Decide whether a new constraint that is added at the front (with respect to a clockwise-oriented scan) makes the preimage empty because of point aP or not

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'true' if the new constraint makes the preimage empty because of point aP and 'false' otherwise.

◆ isRightExteriorAtTheFront()

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

Decide whether a new constraint that is added at the front (with respect to a clockwise-oriented scan) makes the preimage empty because of point aQ or not

Parameters
aPthe end point of the new straight segment expected to lie in the interior of the separating shapes
aQthe end point of the new straight segment expected to lie in the exterior of the separating shapes
Returns
'true' if the new constraint makes the preimage empty because of point aQ and 'false' otherwise.

◆ isValid()

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.

◆ Lf()

template<typename Shape >
Point DGtal::Preimage2D< Shape >::Lf ( ) const
Returns
first lower leaning point.

◆ Ll()

template<typename Shape >
Point DGtal::Preimage2D< Shape >::Ll ( ) const
Returns
last lower leaning point.

◆ operator!=()

template<typename Shape >
bool DGtal::Preimage2D< Shape >::operator!= ( const Preimage2D< Shape > &  other) const

Difference operator

Parameters
otherthe object to compare with.
Returns
'true' if not equal, 'false' otherwise.

◆ operator=()

template<typename Shape >
Preimage2D& DGtal::Preimage2D< Shape >::operator= ( const Preimage2D< Shape > &  other)

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'.

◆ operator==()

template<typename Shape >
bool DGtal::Preimage2D< Shape >::operator== ( const Preimage2D< Shape > &  other) const

Equality operator

Parameters
otherthe object to compare with.
Returns
'true' if the points of myPHull match to those of other.myPHull and if the points of myQHull match to those of other.myQHull, 'false' otherwise.

NB: linear in the size of myPHull and myQHull

◆ pHull()

template<typename Shape >
const Container& DGtal::Preimage2D< Shape >::pHull ( ) const
inline
Returns
the lower part of the preimage.

Definition at line 348 of file Preimage2D.h.

349  {
350  return myPHull;
351  };
Container myPHull
Definition: Preimage2D.h:388

References DGtal::Preimage2D< Shape >::myPHull.

◆ qHull()

template<typename Shape >
const Container& DGtal::Preimage2D< Shape >::qHull ( ) const
inline
Returns
the upper part of the preimage.

Definition at line 356 of file Preimage2D.h.

357  {
358  return myQHull;
359  };
Container myQHull
Definition: Preimage2D.h:393

References DGtal::Preimage2D< Shape >::myQHull.

◆ selfDisplay()

template<typename Shape >
void DGtal::Preimage2D< Shape >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

◆ shape()

template<typename Shape >
const Shape& DGtal::Preimage2D< Shape >::shape ( ) const
inline
Returns
the shape used to separate the input points.

Definition at line 340 of file Preimage2D.h.

341  {
342  return myShape;
343  };

References DGtal::Preimage2D< Shape >::myShape.

◆ Uf()

template<typename Shape >
Point DGtal::Preimage2D< Shape >::Uf ( ) const
Returns
first upper leaning point.

◆ Ul()

template<typename Shape >
Point DGtal::Preimage2D< Shape >::Ul ( ) const
Returns
last upper leaning point.

◆ update()

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
aPointa new vertex of the preimage,
aContainerthe STL-like container to be updated,
anIteratoran iterator to its front (resp. back)
anEndIteratoran iterator pointing after its back (resp. before its front).
Template Parameters
Iteratorthe type of Iterator (either Container::iterator or Container::reverse_iterator)
Predicatethe type of Predicate

Field Documentation

◆ myPHull

template<typename Shape >
Container DGtal::Preimage2D< Shape >::myPHull
private

Lower part of the preimage (whose vertices are Pi points)

Definition at line 388 of file Preimage2D.h.

Referenced by DGtal::Preimage2D< Shape >::pHull().

◆ myQHull

template<typename Shape >
Container DGtal::Preimage2D< Shape >::myQHull
private

Upper part of the preimage. (whose vertices are Qi points)

Definition at line 393 of file Preimage2D.h.

Referenced by DGtal::Preimage2D< Shape >::qHull().

◆ myShape

template<typename Shape >
Shape DGtal::Preimage2D< Shape >::myShape
private

Shape used to separate the input points

Definition at line 381 of file Preimage2D.h.

Referenced by DGtal::Preimage2D< Shape >::shape().


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