#include <GeometricalDSS.h>

Collaboration diagram for DGtal::GeometricalDSS< TConstIterator >:

Public Types
typedef TConstIterator	ConstIterator
typedef GeometricalDSS < ConstIterator >	Self
typedef GeometricalDSS < ReverseIterator < ConstIterator > >	Reverse
typedef IteratorCirculatorTraits < ConstIterator >::Value	Pair
typedef Pair::first_type	Point
typedef StraightLineFrom2Points< Point >	StraightLine
typedef Preimage2D< StraightLine >	Preimage
typedef CowPtr< Preimage >	PreimagePtr

Public Member Functions
	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< typename Pair::first_type, typename Pair::second_type >::value))
	GeometricalDSS ()
	GeometricalDSS (const Self &other)
Self &	operator= (const Self &other)
	~GeometricalDSS ()
bool	operator== (const Self &other) const
bool	operator!= (const Self &other) const
Self	getSelf () const
Reverse	getReverse () const
bool	isValid () const
ConstIterator	begin () const
ConstIterator	end () const
Point	getUf () const
Point	getUl () const
Point	getLf () const
Point	getLl () const
bool	isClockwiseOriented () const
void	getParameters (double &alpha, double &beta, double &gamma) const
void	projects (double &x, double &y, const double &alpha, const double &beta, const double &gamma) const
void	init (const ConstIterator &anIt)
bool	extendForward ()
bool	isExtendableForward ()
bool	isConcave ()
bool	isConvex ()
bool	extendBackward ()
bool	isExtendableBackward ()
bool	isOppositeEndConcave ()
bool	isOppositeEndConvex ()
void	selfDisplay (std::ostream &out) const
std::string	className () const

Private Attributes
ConstIterator	myBegin
ConstIterator	myEnd
PreimagePtr	myPreimagePtr
bool	myFlagIsInit
bool	myFlagIsCW

Detailed Description

template<typename TConstIterator>
class DGtal::GeometricalDSS< TConstIterator >

Aim: On-line recognition of a digital straight segment (DSS) defined as a sequence of connected grid edges such that there is at least one straight line that separates the centers of the two incident pixels of each grid edge.

Note:: On either side, the pixels centers are included. The class of segments considered here is thus larger than the one considered in ArithmeticalDSS (the equivalence would be true if the pixels centers were included on one side but excluded on the other side)

The algorithm computes and maintains the preimage of the whole set of separating straight lines in linear time using Preimage2D and 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.

This class is a model of the concept CBidirectionalSegmentComputer.

It should be used with the Curve object (defined in StdDefs.h) and its IncidentPointsRange as follows:

  Curve::IncidentPointsRange r = c.getIncidentPointsRange(); 
  Curve::IncidentPointsRange::ConstIterator itEnd (r.end()); 
  GeometricalDSS<Curve::IncidentPointsRange::ConstIterator> s; 
  //extension
  s.init( r.begin() );
  while ( ( s.end() != itEnd )
        &&( s.extendForward() ) ) {}

Template Parameters:

TConstIterator ConstIterator type on STL pairs of 2D points

See also:: testGeometricalDSS.cpp exampleGeometricalDSS.cpp Preimage2D ArithmeticalDSS

Definition at line 92 of file GeometricalDSS.h.

Member Typedef Documentation

template<typename TConstIterator>

typedef TConstIterator DGtal::GeometricalDSS< TConstIterator >::ConstIterator

Definition at line 98 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef IteratorCirculatorTraits<ConstIterator>::Value DGtal::GeometricalDSS< TConstIterator >::Pair

Definition at line 103 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef Pair::first_type DGtal::GeometricalDSS< TConstIterator >::Point

Definition at line 104 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef Preimage2D<StraightLine> DGtal::GeometricalDSS< TConstIterator >::Preimage

Definition at line 113 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef CowPtr<Preimage> DGtal::GeometricalDSS< TConstIterator >::PreimagePtr

Definition at line 114 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef GeometricalDSS<ReverseIterator<ConstIterator> > DGtal::GeometricalDSS< TConstIterator >::Reverse

Definition at line 100 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef GeometricalDSS<ConstIterator> DGtal::GeometricalDSS< TConstIterator >::Self

Definition at line 99 of file GeometricalDSS.h.

template<typename TConstIterator>

typedef StraightLineFrom2Points<Point> DGtal::GeometricalDSS< TConstIterator >::StraightLine

Definition at line 112 of file GeometricalDSS.h.

Constructor & Destructor Documentation

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::GeometricalDSS ( )

inline

Constructor.

Definition at line 43 of file GeometricalDSS.ih.

References DGtal::false.

:myBegin(), myEnd(), myPreimagePtr(), myFlagIsInit(false), myFlagIsCW(true)
{
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::GeometricalDSS ( const Self & other )

inline

Copy constructor.

Parameters:

other the object to clone.

Definition at line 50 of file GeometricalDSS.ih.

:myBegin(other.myBegin), myEnd(other.myEnd), myPreimagePtr(other.myPreimagePtr), 
myFlagIsInit(other.myFlagIsInit), myFlagIsCW(other.myFlagIsCW)
{
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::~GeometricalDSS ( )

inline

Destructor.

Definition at line 74 of file GeometricalDSS.ih.

{

}

Member Function Documentation

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::ConstIterator DGtal::GeometricalDSS< TConstIterator >::begin ( ) const

inline

Returns:: segment begin iterator.

Definition at line 160 of file GeometricalDSS.ih.

Referenced by DGtal::Display2DFactory::draw().

{
  return myBegin;
}

template<typename TConstIterator>

DGtal::GeometricalDSS< TConstIterator >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< typename Pair::first_type, typename Pair::second_type >::value) )

template<typename TConstIterator >

std::string DGtal::GeometricalDSS< TConstIterator >::className ( ) const

inline

Default drawing style object.

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

Definition at line 517 of file GeometricalDSS.ih.

{
  return "GeometricalDSS";
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::ConstIterator DGtal::GeometricalDSS< TConstIterator >::end ( ) const

inline

Returns:: segment end iterator.

Definition at line 168 of file GeometricalDSS.ih.

Referenced by DGtal::Display2DFactory::draw().

{
  return myEnd;
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::extendBackward ( )

inline

Backward extension of the segment.

Returns:: 'true' if the segment is extended and 'false' otherwise.

Definition at line 448 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  ConstIterator it( myBegin ); 
  --it; 
  Pair aPair( *it ); 
  bool isOK = false; 
  
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isOK = myPreimagePtr->addBack( aPair.first, aPair.second ); 
    else
      isOK = myPreimagePtr->addFront( aPair.first, aPair.second ); 
    
  } else
  { //not initialized yet
    if ( myPreimagePtr->addBack( aPair.first, aPair.second ) )
    {
      myFlagIsCW = true;
      isOK = true; 
    }
    else if ( myPreimagePtr->addFront( aPair.first, aPair.second ) )
    {
      myFlagIsCW = false;
      isOK = true; 
    }
    myFlagIsInit = true; 
  }
  
  if (isOK) 
  {
    myBegin = it; 
    return true; 
  } else return false; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::extendForward ( )

inline

Forward extension of the segment.

Returns:: 'true' if the segment is extended and 'false' otherwise.

Definition at line 379 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  Pair aPair( *myEnd ); 
  bool isOK = false; 
  
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isOK = myPreimagePtr->addFront( aPair.first, aPair.second ); 
    else
      isOK = myPreimagePtr->addBack( aPair.first, aPair.second ); 
    
  } else
  { //not initialized yet
    if ( myPreimagePtr->addFront( aPair.first, aPair.second ) )
    {
      myFlagIsCW = true;
      isOK = true; 
    }
    else if ( myPreimagePtr->addBack( aPair.first, aPair.second ) )
    {
      myFlagIsCW = false;
      isOK = true; 
    }
    myFlagIsInit = true; 
  }
  
  if (isOK) 
  {
    ++myEnd; 
    return true; 
  } else return false; 
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Point DGtal::GeometricalDSS< TConstIterator >::getLf ( ) const

inline

Returns:: first lower leaning point.

Definition at line 194 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  return myPreimagePtr->getLf();
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Point DGtal::GeometricalDSS< TConstIterator >::getLl ( ) const

inline

Returns:: last lower leaning point.

Definition at line 203 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  return myPreimagePtr->getLl();
}

template<typename TConstIterator >

void DGtal::GeometricalDSS< TConstIterator >::getParameters	(	double &	alpha,
		double &	beta,
		double &	gamma
	)		const

inline

Get the parameters of one separating straight line

Parameters:

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

Definition at line 221 of file GeometricalDSS.ih.

Referenced by DGtal::Display2DFactory::draw().

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  myPreimagePtr->getSeparatingStraightLine(alpha, beta, gamma);
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Reverse DGtal::GeometricalDSS< TConstIterator >::getReverse ( ) const

inline

Returns:: a default-constructed instance of Reverse.

Definition at line 123 of file GeometricalDSS.ih.

{
  return Reverse(); 
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Self DGtal::GeometricalDSS< TConstIterator >::getSelf ( ) const

inline

Returns:: a default-constructed instance of Self

Definition at line 132 of file GeometricalDSS.ih.

{
  return Self(); 
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Point DGtal::GeometricalDSS< TConstIterator >::getUf ( ) const

inline

Returns:: first upper leaning point.

Definition at line 176 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  return myPreimagePtr->getUf();
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Point DGtal::GeometricalDSS< TConstIterator >::getUl ( ) const

inline

Returns:: last upper leaning point.

Definition at line 185 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  return myPreimagePtr->getUl();
}

template<typename TConstIterator >

void DGtal::GeometricalDSS< TConstIterator >::init ( const ConstIterator & anIt )

inline

Segment initialization

Parameters:

anIt	any iterator

Definition at line 246 of file GeometricalDSS.ih.

{
  myBegin = anIt; 
  myEnd = anIt; 
  ++myEnd; 
  Pair aPair( *anIt); 
  myPreimagePtr = PreimagePtr( new Preimage( aPair.first, aPair.second, StraightLine() ) );
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isClockwiseOriented ( ) const

inline

Returns:: 'true' if CW, 'false' if CCW

Definition at line 212 of file GeometricalDSS.ih.

{
  return myFlagIsCW;
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isConcave ( )

inline

Decide whether the extension of the segment would result in a concave part or not.

Returns:: 'true' if the extension of the segment results in a concave part and 'false' otherwise.

NB: a true returned value implies that isExtendableForward() returns 'false'

Definition at line 258 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  Pair aPair( *myEnd ); 
  bool isExterior = false; 
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isExterior = myPreimagePtr->isLeftExteriorAtTheFront( aPair.first, aPair.second ); 
    else
      isExterior = myPreimagePtr->isRightExteriorAtTheBack( aPair.first, aPair.second ); 
    
  }
  return isExterior; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isConvex ( )

inline

Decide whether the extension of the segment would result in a convex part or not.

Returns:: 'true' if the extension of the segment results in a convex part and 'false' otherwise.

NB: a true returned value implies that isExtendableForward() returns 'false'

Definition at line 280 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  Pair aPair( *myEnd ); 
  bool isExterior = false; 
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isExterior = myPreimagePtr->isRightExteriorAtTheFront( aPair.first, aPair.second ); 
    else
      isExterior = myPreimagePtr->isLeftExteriorAtTheBack( aPair.first, aPair.second ); 
    
  }
  return isExterior; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isExtendableBackward ( )

inline

Backward extension test.

Returns:: 'true' if the segment can be extended and 'false' otherwise.

Definition at line 418 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  ConstIterator it( myBegin ); 
  --it; 
  Pair aPair( *it ); 
  bool isOK = false; 
  
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isOK = myPreimagePtr->canBeAddedAtTheBack( aPair.first, aPair.second ); 
    else
      isOK = myPreimagePtr->canBeAddedAtTheFront( aPair.first, aPair.second ); 
    
  } else
  { //not initialized yet
    if ( myPreimagePtr->canBeAddedAtTheBack( aPair.first, aPair.second ) )
      isOK = true; 
    else if ( myPreimagePtr->canBeAddedAtTheFront( aPair.first, aPair.second ) )
      isOK = true; 
  }
  
  return isOK; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isExtendableForward ( )

inline

Forward extension test.

Returns:: 'true' if the segment can be extended and 'false' otherwise.

Definition at line 351 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  Pair aPair( *myEnd ); 
  bool isOK = false; 
  
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isOK = myPreimagePtr->canBeAddedAtTheFront( aPair.first, aPair.second ); 
    else
      isOK = myPreimagePtr->canBeAddedAtTheBack( aPair.first, aPair.second ); 
    
  } else
  { //not initialized yet
    if ( myPreimagePtr->canBeAddedAtTheFront( aPair.first, aPair.second ) )
      isOK = true; 
    else if ( myPreimagePtr->canBeAddedAtTheBack( aPair.first, aPair.second ) )
      isOK = true; 
  }
  
  return isOK; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isOppositeEndConcave ( )

inline

Decide whether the extension of the segment would result in a concave part or not.

Returns:: 'true' if the extension of the segment results in a concave part and 'false' otherwise.

NB: a true returned value implies that isExtendableBackward() returns 'false'

Definition at line 302 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  ConstIterator it( myBegin ); 
  --it; 
  Pair aPair( *it ); 
  bool isExterior = false; 
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isExterior = myPreimagePtr->isRightExteriorAtTheBack( aPair.first, aPair.second ); 
    else
      isExterior = myPreimagePtr->isLeftExteriorAtTheFront( aPair.first, aPair.second ); 
    
  }
  return isExterior; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isOppositeEndConvex ( )

inline

Decide whether the extension of the segment would result in a convex part or not.

Returns:: 'true' if the extension of the segment results in a convex part and 'false' otherwise.

NB: a true returned value implies that isExtendableBackward() returns 'false'

Definition at line 326 of file GeometricalDSS.ih.

{
  ASSERT( myPreimagePtr.get() != 0 ); 
  ConstIterator it( myBegin ); 
  --it; 
  Pair aPair( *it ); 
  bool isExterior = false; 
  if (myFlagIsInit)
  { //initialized
    
    if (myFlagIsCW) 
      isExterior = myPreimagePtr->isLeftExteriorAtTheBack( aPair.first, aPair.second ); 
    else
      isExterior = myPreimagePtr->isRightExteriorAtTheFront( aPair.first, aPair.second ); 
    
  }
  return isExterior; 
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::isValid ( ) const

inline

Checks the validity/consistency of the object.

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

Definition at line 145 of file GeometricalDSS.ih.

References DGtal::GeometricalDSS< TConstIterator >::isValid().

Referenced by DGtal::GeometricalDSS< TConstIterator >::isValid(), and DGtal::GeometricalDSS< TConstIterator >::operator==().

{
  if ( myPreimagePtr.get() != 0 )
  {
    return myPreimagePtr->isValid(); 
  }
  else 
  {
    return false;
  }
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::operator!= ( const Self & other ) const

inline

Difference operator

Parameters:

other the object to compare with.

Returns:: 'true' if not equal, 'false' otherwise.

Definition at line 115 of file GeometricalDSS.ih.

{
  return !(*this == other); 
}

template<typename TConstIterator >

DGtal::GeometricalDSS< TConstIterator >::Self & DGtal::GeometricalDSS< TConstIterator >::operator= ( const Self & other )

inline

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'.

Definition at line 59 of file GeometricalDSS.ih.

References DGtal::GeometricalDSS< TConstIterator >::myBegin, DGtal::GeometricalDSS< TConstIterator >::myEnd, DGtal::GeometricalDSS< TConstIterator >::myFlagIsCW, DGtal::GeometricalDSS< TConstIterator >::myFlagIsInit, and DGtal::GeometricalDSS< TConstIterator >::myPreimagePtr.

{
  if ( this != &other )
  {
    myBegin = other.myBegin;
    myEnd = other.myEnd;
    myPreimagePtr = other.myPreimagePtr;
    myFlagIsInit = other.myFlagIsInit; 
    myFlagIsCW = other.myFlagIsCW; 
  }
  return *this;
}

template<typename TConstIterator >

bool DGtal::GeometricalDSS< TConstIterator >::operator== ( const Self & other ) const

inline

Equality operator

Parameters:

other the object to compare with.

Returns:: 'true' if equal, 'false' otherwise

Definition at line 81 of file GeometricalDSS.ih.

References DGtal::GeometricalDSS< TConstIterator >::isValid(), DGtal::GeometricalDSS< TConstIterator >::myBegin, DGtal::GeometricalDSS< TConstIterator >::myEnd, and DGtal::GeometricalDSS< TConstIterator >::myPreimagePtr.

{
  if (isValid()&&other.isValid())
  {
    Pair firstPair( *myBegin );
    Pair oFirstPair( *(other.myBegin) ); 
    if ( (firstPair.first == oFirstPair.first)
       &&(firstPair.second == oFirstPair.second) )
    {
      ConstIterator it (myEnd); 
      --it;
      Pair lastPair( *it );  
      ConstIterator oIt (other.myEnd); 
      --oIt;
      Pair oLastPair( *oIt ); 
     
      if ( (lastPair.first == oLastPair.first)
         &&(lastPair.second == oLastPair.second) )
      {
        return ( *myPreimagePtr == *(other.myPreimagePtr) ); 
      }
      else return false; 
    } 
    else return false; 
  }
  else 
  {
    return ( (!isValid()) && (!other.isValid()) );
  }
}

template<typename TConstIterator >

void DGtal::GeometricalDSS< TConstIterator >::projects	(	double &	x,
		double &	y,
		const double &	alpha,
		const double &	beta,
		const double &	gamma
	)		const

inline

Projects the point ( x , y ) onto the straight line of parameters ( alpha , beta , gamma )

Parameters:

x	(returned) x-coordinate of the point
y	(returned) y-coordinate of the point
alpha	x-component of the direction vector
beta	y-component of the direction vector
gamma	intercept

Definition at line 230 of file GeometricalDSS.ih.

Referenced by DGtal::Display2DFactory::draw().

{
  ASSERT( (alpha!=0)||(beta!=0) );
  double d2 = ( alpha * alpha + beta * beta );
  double s = beta*x - alpha*y; 
  x = (beta*s - alpha*gamma)/d2;
  y = -(alpha*s + beta*gamma)/d2;
}

template<typename TConstIterator >

void DGtal::GeometricalDSS< TConstIterator >::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the object on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 492 of file GeometricalDSS.ih.

{
  out << std::endl;
  out << "[GeometricalDSS]" << std::endl;
  if (isValid())
  {
    Pair firstPair( *myBegin ); 
    out << "\t From " << firstPair.first << firstPair.second << std::endl; 
    ConstIterator it (myEnd); 
    --it;
    Pair lastPair( *it );  
    out << "\t To " << lastPair.first << lastPair.second << std::endl; 
    ASSERT( myPreimagePtr.get() != 0 ); 
    out << (*myPreimagePtr); 
  }
  else
  {
    out << "\t not valid" << std::endl; 
  }
  out << "[end of GeometricalDSS]" << std::endl;
}