#include <FP.h>

Collaboration diagram for DGtal::FP< TIterator, TInteger, connectivity >:

Public Types
typedef DGtal::PointVector < 2, TInteger >	Point
typedef DGtal::PointVector < 2, TInteger >	Vector
typedef DGtal::PointVector < 2, double >	RealPoint
typedef DGtal::PointVector < 2, double >	RealVector
typedef DGtal::ArithmeticalDSS < TIterator, TInteger, connectivity >	DSSComputer
typedef DGtal::ArithmeticalDSS < DGtal::Circulator< TIterator > , TInteger, connectivity >	DSSComputerInLoop
typedef std::list< Point >	Polygon

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CInteger< TInteger >))
	FP (const TIterator &itb, const TIterator &ite) throw ( InputException )
	FP (const TIterator &itb, const TIterator &ite, const bool &isClosed) throw ( InputException )
	~FP ()
const Polygon &	polygon () const
bool	flagIsClosed () const
bool	isValid () const
Polygon::size_type	size () const
template<typename OutputIterator >
OutputIterator	copyFP (OutputIterator result) const
template<typename OutputIterator >
OutputIterator	copyMLP (OutputIterator result) const
void	selfDisplay (std::ostream &out) const
std::string	className () const

Private Member Functions
template<typename DSS , typename Adapter >
bool	initConvexityConcavity (DSS &aDSS, Adapter *&anAdapter, const typename DSS::ConstIterator &i)
template<typename DSS , typename Adapter >
void	mainAlgorithm (DSS &currentDSS, Adapter *adapter, bool isConvex, typename DSS::ConstIterator i, const typename DSS::ConstIterator &end) throw ( InputException )
RealPoint	getRealPoint (const Point &a, const Point &b, const Point &c) const
bool	quadrant (const Vector &v, const int &q) const
	FP (const FP &other)
FP &	operator= (const FP &other)

Private Attributes
Polygon	myPolygon
bool	myFlagIsClosed

Detailed Description

template<typename TIterator, typename TInteger, int connectivity>
class DGtal::FP< TIterator, TInteger, connectivity >

Aim: Computes the faithful polygon (FP) of a range of 4/8-connected 2D Points.

The FP has several interesting properties:

its vertices are points of the underlying digital curve, thus with integer coordinates,
it respects the convex and concave parts of the underlying digital curve,
it is reversible,
it is unique for digital curves that are not digital straight segments,
it is closed to the minimum length polygon (MLP) (and converges toward the MLP as the resolution tends to the infinity) for closed digital curves.

It is computed in the course of the maximal digital straight segments computation, because in convex parts (resp. concave parts), the first and last upper (resp. lower) leaning points of segments that are maximal at the front or at the back are also vertices of the FP.

See also:: ArithmeticalDSS Adapter Adapter4ConvexPart Adapter4ConcavePart

Note:: T. ROUSSILLON and I. SIVIGNON, Faithful polygonal representation of the convex and concave parts of a digital curve, Pattern Recognition, Volume 44, Issues 10-11, October-November 2011, Pages 2693-2700.

Usage:

//r is a range of 4-connected 2D points

FP<ConstIterator, Integer, 4> theFP( r .begin(), r.end() );

Once the FP is computed, copyFP() is a way of geting its vertices. In the same way, copyMLP() is a way of getting the vertices of the MLP.

Template Parameters:

'TIterator'	type ConstIterator on 2D points,
'TInteger'	type of scalars used for the DSS parameters (satisfying CInteger)
'connectivity'	an integer equal to 4 for standard (4-connected) DSS or 8 for naive (8-connected) DSS. (Any other integers act as 8).

See also:: testFP.cpp

Definition at line 222 of file FP.h.

Member Typedef Documentation

template<typename TIterator, typename TInteger, int connectivity>

typedef DGtal::ArithmeticalDSS<TIterator,TInteger,connectivity> DGtal::FP< TIterator, TInteger, connectivity >::DSSComputer

Definition at line 237 of file FP.h.

template<typename TIterator, typename TInteger, int connectivity>

typedef DGtal::ArithmeticalDSS<DGtal::Circulator<TIterator>,TInteger,connectivity> DGtal::FP< TIterator, TInteger, connectivity >::DSSComputerInLoop

Definition at line 238 of file FP.h.

template<typename TIterator, typename TInteger, int connectivity>

typedef DGtal::PointVector<2,TInteger> DGtal::FP< TIterator, TInteger, connectivity >::Point

Definition at line 231 of file FP.h.

template<typename TIterator, typename TInteger, int connectivity>

typedef std::list<Point> DGtal::FP< TIterator, TInteger, connectivity >::Polygon

Definition at line 240 of file FP.h.

template<typename TIterator, typename TInteger, int connectivity>

typedef DGtal::PointVector<2, double> DGtal::FP< TIterator, TInteger, connectivity >::RealPoint

Definition at line 234 of file FP.h.

template<typename TIterator, typename TInteger, int connectivity>

typedef DGtal::PointVector<2, double> DGtal::FP< TIterator, TInteger, connectivity >::RealVector

Definition at line 235 of file FP.h.

template<typename TIterator, typename TInteger, int connectivity>

typedef DGtal::PointVector<2,TInteger> DGtal::FP< TIterator, TInteger, connectivity >::Vector

Definition at line 232 of file FP.h.

Constructor & Destructor Documentation

template<typename TIterator , typename TInteger , int connectivity>

DGtal::FP< TIterator, TInteger, connectivity >::FP	(	const TIterator &	itb,
		const TIterator &	ite
	)		throw ( InputException )

inline

Constructor.

Parameters:

itb	begin iterator
ite	end iterator

Definition at line 152 of file FP.ih.

{
  FP(itb, ite, false);
}

template<typename TIterator , typename TInteger , int connectivity>

DGtal::FP< TIterator, TInteger, connectivity >::FP	(	const TIterator &	itb,
		const TIterator &	ite,
		const bool &	isClosed
	)		throw ( InputException )

inline

Constructor.

Parameters:

itb	begin iterator
ite	end iterator
isClosed	'true' if the range has to be considered as circular, 'false' otherwise.

Definition at line 161 of file FP.ih.

References DGtal::ArithmeticalDSS< TIterator, TInteger, connectivity >::extendBackward(), DGtal::ArithmeticalDSS< TIterator, TInteger, connectivity >::extendForward(), DGtal::ArithmeticalDSS< TIterator, TInteger, connectivity >::getLf(), and DGtal::ArithmeticalDSS< TIterator, TInteger, connectivity >::getUf().

  : myFlagIsClosed( isClosed ) 
{
  TIterator i = itb;
  if (i != ite) 
    {
      if (myFlagIsClosed) 
        { 
          //first maximal DSS
          Circulator<TIterator> citb(i,itb,ite);
          //DSSComputerInLoop firstMS(citb);
          DSSComputerInLoop *firstMS=new DSSComputerInLoop(citb); //init
          ASSERT(firstMS);
        
          //backward extension
          Circulator<TIterator> back( citb );
          do {
            --back; 
          } while (firstMS->extendBackward(back));
          //forward extension
          Circulator<TIterator> front( citb );
          do {
            ++front; 
          } while (firstMS->extendForward(front));
          //local convexity
          bool isConvexAtFront; 
          Adapter<DSSComputerInLoop>* adapterAtFront;   
        
          isConvexAtFront = initConvexityConcavity<DSSComputerInLoop,Adapter<DSSComputerInLoop> >
            (*firstMS,adapterAtFront,front);
        
          bool isConvexAtBack; 
          Adapter<DSSComputerInLoop>* adapterAtBack;  
        
          isConvexAtBack = initConvexityConcavity<DSSComputerInLoop,Adapter<DSSComputerInLoop> >
            (*firstMS,adapterAtBack,back);
        
          ASSERT(adapterAtFront);
          ASSERT(adapterAtBack);
        
        
          //first point 
          if (adapterAtFront->firstLeaningPoint() == adapterAtFront->lastLeaningPoint()) {
            myPolygon.push_back(adapterAtFront->lastLeaningPoint());
          }
        
          //set end iterator
          typename DSSComputerInLoop::Point leaningPoint; 
          if ( ( (isConvexAtFront)&&(isConvexAtBack) ) 
               || ( (!isConvexAtFront)&&(!isConvexAtBack) ) ) {
            leaningPoint = adapterAtFront->lastLeaningPoint();
          } else {
            leaningPoint = adapterAtBack->firstLeaningPoint(); 
          }
          do {
            ++back;
          } while (*back != leaningPoint);
          ++back;
        
          //call main algo
          mainAlgorithm<DSSComputerInLoop,Adapter<DSSComputerInLoop> >
            (*firstMS,adapterAtFront,isConvexAtFront,front,back);
        
          ASSERT(adapterAtFront);
          ASSERT(adapterAtBack);
        
          //delete (adapterAtFront);
          //delete (adapterAtBack);
          delete (firstMS);
          //remove the last point
          myPolygon.pop_back();
        
        } 
      else 
        { 
          //list of successive upper (U) and lower (L)
          // leaning points. 
          std::list<Point> vTmpU, vTmpL;
          vTmpU.push_back(*i);
          vTmpL.push_back(*i);
          //longest DSS
          DSSComputer *longestDSS= new DSSComputer(i); //longest DSS
          
          ASSERT(longestDSS);
          ++i; //move forward
          while ( (i != ite)&&(longestDSS->extendForward(i)) ) 
            {
              //store the first upper leaning point
              if (longestDSS->getUf() != vTmpU.back()) {
                vTmpU.push_back(longestDSS->getUf());
              }
              //store the first lower leaning point
              if (longestDSS->getLf() != vTmpL.back()) {
                vTmpL.push_back(longestDSS->getLf());
              }
              ++i; //move forward
            }
        
          bool isConvex; //TRUE if longestDSS begins a convex part, FALSE otherwise
          Adapter<DSSComputer>* adapter; //adapter for the current DSS
        
          if (i != ite) 
            {
              isConvex = initConvexityConcavity<DSSComputer,Adapter<DSSComputer> >
                (*longestDSS,adapter,i);
            
              ASSERT(adapter);
            
              if (isConvex) myPolygon = vTmpU;
              else myPolygon = vTmpL;
            
              //call main algo
              mainAlgorithm<DSSComputer,Adapter<DSSComputer> >
                (*longestDSS,adapter,isConvex,i,ite);
            
              ASSERT(adapter);
              //delete (adapter);
              delete (longestDSS);
            } 
          else 
            {
              //the part is assumed to be convex
              //if it is straight
              myPolygon = vTmpU;
              isConvex = true;
              adapter = new Adapter4ConvexPart<DSSComputer>(*longestDSS);
              ASSERT(adapter);
            }
        
        }//end closed/open test
    
    } //end itb == ite test
  
}

template<typename TIterator , typename TInteger , int connectivity>

DGtal::FP< TIterator, TInteger, connectivity >::~FP ( )

inline

Destructor.

Definition at line 306 of file FP.ih.

{

}

template<typename TIterator, typename TInteger, int connectivity>

DGtal::FP< TIterator, TInteger, connectivity >::FP ( const FP< TIterator, TInteger, connectivity > & other )

private

Copy constructor.

Parameters:

other the object to clone. Forbidden by default.

Member Function Documentation

template<typename TIterator, typename TInteger, int connectivity>

DGtal::FP< TIterator, TInteger, connectivity >::BOOST_CONCEPT_ASSERT ( (CInteger< TInteger >) )

template<typename TIterator , typename TInteger , int connectivity>

std::string DGtal::FP< TIterator, TInteger, connectivity >::className ( ) const

inline

Default drawing style object.

Parameters:

mode	the drawing mode.

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

Definition at line 466 of file FP.ih.

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

{
  return "FP";
} 

template<typename TIterator , typename TInteger , int connectivity>

template<typename OutputIterator >

OutputIterator DGtal::FP< TIterator, TInteger, connectivity >::copyFP ( OutputIterator result ) const

inline

Returns:: the vertices of the FP NB: O(n)

Definition at line 334 of file FP.ih.

Referenced by DGtal::FPLengthEstimator< TConstIterator >::init().

                                                                            {
  typename Polygon::const_iterator i = myPolygon.begin();
  while ( i != myPolygon.end() ) {
    *result++ = *i++;
  }
  return result;
}

template<typename TIterator , typename TInteger , int connectivity>

template<typename OutputIterator >

OutputIterator DGtal::FP< TIterator, TInteger, connectivity >::copyMLP ( OutputIterator result ) const

inline

Returns:: the vertices of the MLP NB: O(n)

Definition at line 346 of file FP.ih.

Referenced by DGtal::MLPLengthEstimator< TConstIterator >::init().

                                                                             {
  unsigned int n = (unsigned int) myPolygon.size();
  if (n < 3) { //special case < 3 points
    typename Polygon::const_iterator i = myPolygon.begin();
    for ( ; i!= myPolygon.end() ; ++i) {
      *result++ = RealPoint( *i );
    }
  } else {    //standard case
    typename Polygon::const_iterator i, j, k;
    i = myPolygon.begin();
    j = i; ++j; 
    k = j; ++k; 
    if (myFlagIsClosed) { 
      //first point
      *result++ = getRealPoint(myPolygon.back(),*i,*j);
      //middle points
      while ( k != myPolygon.end() ) {
        *result++ = getRealPoint(*i,*j,*k);
        ++i; ++j; ++k; 
      }
      //last point
      *result++ = getRealPoint(*i,*j,myPolygon.front());
    } else { 
      //first point
      *result++ = RealPoint( myPolygon.front() );
      //middle points
      while ( k != myPolygon.end() ) {
        *result++ = getRealPoint(*i,*j,*k);
        ++i; ++j; ++k; 
      }
      //last point
      *result++ = RealPoint( myPolygon.back() );
    }
  }
  return result;
}

template<typename TIterator, typename TInteger, int connectivity>

bool DGtal::FP< TIterator, TInteger, connectivity >::flagIsClosed ( ) const

inline

Returns:: true if the list has to be consider as circular.

Definition at line 282 of file FP.h.

References DGtal::FP< TIterator, TInteger, connectivity >::myFlagIsClosed.

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

    {
      return myFlagIsClosed;
    };

template<typename TIterator , typename TInteger , int connectivity>

DGtal::PointVector< 2, double > DGtal::FP< TIterator, TInteger, connectivity >::getRealPoint	(	const Point &	a,
		const Point &	b,
		const Point &	c
	)		const

inlineprivate

Gets a MLP vertex from three consecutive vertices of the FP.

Parameters:

a	previous vertex of the FP
b	current vertex of the FP
c	next vertex of the FP

Returns:: vertex of the MLP, which is the tranlated of b by (+- 0.5, +- 0.5)

Definition at line 397 of file FP.ih.

                                                                   {
  RealVector shift;
  Vector e1 = b - a; //previous edge
  Vector e2 = c - b; //next edge
  if ( (e1[0]*e2[1]-e1[1]*e2[0]) <= 0 ) {
    //convex turn
    if ( (quadrant(e1,1))&&(quadrant(e2,1)) ) {
      shift = RealVector(0.5,-0.5);
    } else if ( (quadrant(e1,2))&&(quadrant(e2,2)) ) {
      shift = RealVector(-0.5,-0.5);
    } else if ( (quadrant(e1,3))&&(quadrant(e2,3)) ) {
      shift = RealVector(-0.5,0.5);
    } else if ( (quadrant(e1,4))&&(quadrant(e2,4)) ) {
      shift = RealVector(0.5,0.5);
    } else {
      ASSERT(false && "DGtal::FP<TIterator,TInteger,connectivity>::getRealPoint: not valid polygon" );
    }
  } else {
    //concave turn
    if ( (quadrant(e1,1))&&(quadrant(e2,1)) ) {
      shift = RealVector(-0.5,0.5);
    } else if ( (quadrant(e1,2))&&(quadrant(e2,2)) ) {
      shift = RealVector(0.5,0.5);
    } else if ( (quadrant(e1,3))&&(quadrant(e2,3)) ) {
      shift = RealVector(0.5,-0.5);
    } else if ( (quadrant(e1,4))&&(quadrant(e2,4)) ) {
      shift = RealVector(-0.5,-0.5);
    } else {
      ASSERT(false && "DGtal::FP<TIterator,TInteger,connectivity>::getRealPoint: not valid polygon" );
    }
  } 
  return ( RealPoint(b) + shift );
}

template<typename TIterator , typename TInteger , int connectivity>

template<typename DSS , typename Adapter >

bool DGtal::FP< TIterator, TInteger, connectivity >::initConvexityConcavity	(	DSS &	aDSS,
		Adapter *&	anAdapter,
		const typename DSS::ConstIterator &	i
	)

inlineprivate

A DSS adapter is chosen according to the local convexity/concavity

Parameters:

aDSS	a DSS lying on the range to process
anAdapter	an Adapter to aDSS for convex part when 'true' is returned, for concave part otherwise
i	an iterator pointing after the front of aDSS

Returns:: 'true' if aDSS begins a convex part, 'false' otherwise

Definition at line 47 of file FP.ih.

                                                               {
  bool flag; 
  if ( aDSS.getRemainder(i) < (aDSS.getMu()) ) {      //concave part
    flag = false;
    anAdapter = new Adapter4ConcavePart<DSS>(aDSS);
  } else {                                            //convex part
    flag = true;
    anAdapter = new Adapter4ConvexPart<DSS>(aDSS);
  }
  return flag;
}

template<typename TIterator , typename TInteger , int connectivity>

bool DGtal::FP< TIterator, TInteger, connectivity >::isValid ( ) const

inline

Checks the validity/consistency of the object.

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

Definition at line 316 of file FP.ih.

{
  return true;
}

template<typename TIterator , typename TInteger , int connectivity>

template<typename DSS , typename Adapter >

void DGtal::FP< TIterator, TInteger, connectivity >::mainAlgorithm	(	DSS &	currentDSS,
		Adapter *	adapter,
		bool	isConvex,
		typename DSS::ConstIterator	i,
		const typename DSS::ConstIterator &	end
	)		throw ( InputException )

inlineprivate

Main algorithm

Parameters:

currentDSS	a DSS lying on the range to process
adapter	an Adapter to currentDSS
isConvex,'true'	if currentDSS is in a convex part, 'false' otherwise
i	an iterator pointing after the front of currentDSS
end	iterator used to stop the algorithm (when i == end )

Definition at line 67 of file FP.ih.

                                                                                 {
  ASSERT(adapter != 0);
  //std::cerr << "first DSS" << std::endl;
  //std::cerr << currentDSS << std::endl;
  while (i != end) {
    //store the last leaning point 
    //if the first and last leaning points 
    //of the MS are not confounded
    if (adapter->firstLeaningPoint() != adapter->lastLeaningPoint()) {
      myPolygon.push_back(adapter->lastLeaningPoint());
    }
    //removing step
    while (!currentDSS.isExtendableForward(i)) {
      //remove a point from the back
      if ( currentDSS.retractForward() ) {
        //store the last leaning point
        if (adapter->lastLeaningPoint() != myPolygon.back()) {
          myPolygon.push_back(adapter->lastLeaningPoint());
        }
      } else {
        //disconnected digital curve
        throw InputException();
      }
    }
    //remove the last leaning point 
    //if the first and last leaning points 
    //of the current DSS are not confounded
    if (adapter->firstLeaningPoint() != adapter->lastLeaningPoint()) {
      myPolygon.pop_back();
    }    
    //adding step
    while ( (i != end)&&(currentDSS.extendForward(i)) ) {
      //store the first leaning point
      if (adapter->firstLeaningPoint() != myPolygon.back()) {
        myPolygon.push_back(adapter->firstLeaningPoint());
      }
      ++i; //move forward
    }
    //transition step
    if (i != end) {
      if ( (isConvex)&&( currentDSS.getRemainder(i) < 
                         (currentDSS.getMu()) ) ) {
        //from convex to concave
        isConvex = false;
        delete (adapter);
        adapter = new Adapter4ConcavePart<DSS>(currentDSS);
      } else if ( (!isConvex)&&( currentDSS.getRemainder(i) >= 
                                 (currentDSS.getMu()+currentDSS.getOmega()) ) ) {
        //from concave to convex
        isConvex = true;
        delete (adapter);
        adapter = new Adapter4ConvexPart<DSS>(currentDSS);
      }
    }
  }
  //std::cerr << "last DSS" << std::endl;
  //std::cerr << currentDSS << std::endl;
  //last removing step
  while (currentDSS.retractForward()) {
    //store the last leaning point
    if (adapter->lastLeaningPoint() != myPolygon.back()) {
      myPolygon.push_back(adapter->lastLeaningPoint());
    }
  }
}

template<typename TIterator, typename TInteger, int connectivity>

FP& DGtal::FP< TIterator, TInteger, connectivity >::operator= ( const FP< TIterator, TInteger, connectivity > & other )

private

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'. Forbidden by default.

template<typename TIterator, typename TInteger, int connectivity>

const Polygon& DGtal::FP< TIterator, TInteger, connectivity >::polygon ( ) const

inline

Returns:: the list where each vertex of the FP is stored.

Definition at line 274 of file FP.h.

References DGtal::FP< TIterator, TInteger, connectivity >::myPolygon.

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

    {
      return myPolygon;
    };

template<typename TIterator , typename TInteger , int connectivity>

bool DGtal::FP< TIterator, TInteger, connectivity >::quadrant	(	const Vector &	v,
		const int &	q
	)		const

inlineprivate

Returns the quadrant number of a vector

Parameters:

v	any ector
q	a quandrant number (0,1,2 or 3)

Returns:: 'true' if v lies in quadrant number q, 'false' otherwise

Definition at line 443 of file FP.ih.

                                               {
  if (q == 1) {
    return ( (v[0]>=0)&&(v[1]>=0) );
  } else if (q == 2) {
    return ( (v[0]>=0)&&(v[1]<=0) );
  } else if (q == 3) {
    return ( (v[0]<=0)&&(v[1]<=0) );
  } else if (q == 4) {
    return ( (v[0]<=0)&&(v[1]>=0) );
  } else {
    ASSERT(false && 
           "DGtal::FP<TIterator,TInteger,connectivity>::quadrant: quadrant number should be 0,1,2 or 3"  );
    return false;
  }
}

template<typename TIterator , typename TInteger , int connectivity>

void DGtal::FP< TIterator, TInteger, connectivity >::selfDisplay ( std::ostream & out ) const

inline

Definition at line 475 of file FP.ih.

{
  out << "[FP]" << endl;
  typename Polygon::const_iterator i = myPolygon.begin();
  for ( ;i != myPolygon.end();++i)
    {
      out << "\t " << (*i) << endl;
    }              
  out << "[end FP]" << endl;
}