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< Point >	Container

Public Member Functions
	Preimage2D (const Point &firstPoint, const Point &secondPoint, const Shape &aShape)
	~Preimage2D ()
	Preimage2D (const Preimage2D &other)
Preimage2D &	operator= (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 Shape &	shape () const
const Container &	pHull () const
const Container &	qHull () 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

Shape

a 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;

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
  Curve::IncidentPointsRange::ConstIterator itEnd (r.end()); 
 
  //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" );

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

firstPoint	the end point of the first straight segment expected to lie in the interior of the separating shapes
secondPoint	the end point of the first straight segment expected to lie in the exterior of the separating shapes
aShape	any 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

other

the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

aP	the end point of the new straight segment expected to lie in the interior of the separating shapes
aQ	the 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

other

the 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

other

the 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

other

the 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.

    {
      return myPHull;
    };

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.

    {
      return myQHull;
    };

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

out	the 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.

    {
      return myShape;
    };

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

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

Template Parameters

Iterator	the type of Iterator (either Container::iterator or Container::reverse_iterator)
Predicate	the 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:

• Preimage2D.h