DGtal  1.5.beta
DGtal::StabbingCircleComputer< TConstIterator > Class Template Reference

Aim: On-line recognition of a digital circular arcs (DCA) defined as a sequence of connected grid edges such that there is at least one (Euclidean) circle that separates the centers of the two incident pixels of each grid edge. More...

#include <DGtal/geometry/curves/StabbingCircleComputer.h>

Public Types

typedef TConstIterator ConstIterator
 
typedef StabbingCircleComputer< ConstIteratorSelf
 
typedef StabbingCircleComputer< ReverseIterator< ConstIterator > > Reverse
 
typedef IteratorCirculatorTraits< ConstIterator >::Value Pair
 
typedef Pair::first_type Point
 

Public Member Functions

 BOOST_STATIC_ASSERT ((concepts::ConceptUtils::SameType< typename Pair::first_type, typename Pair::second_type >::value))
 
 BOOST_STATIC_ASSERT ((Point::dimension==2))
 
 StabbingCircleComputer ()
 
 StabbingCircleComputer (const Self &other)
 
Selfoperator= (const Self &other)
 
 ~StabbingCircleComputer ()
 
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
 
bool isStraight () const
 
StabbingLineComputerPtr getStabbingLineComputerPtr () const
 
Circle getSeparatingCircle () const
 
void init (const ConstIterator &anIt)
 
bool extendFront ()
 
bool isExtendableFront ()
 
bool extendBack ()
 
bool isExtendableBack ()
 
void selfDisplay (std::ostream &out) const
 
std::string className () const
 

Private Types

typedef CowPtr< StabbingLineComputer< ConstIterator > > StabbingLineComputerPtr
 
typedef CircleFrom3Points< PointCircle
 
typedef functors::Point2ShapePredicate< Circle, false, true > PInCirclePred
 
typedef functors::Point2ShapePredicate< Circle, true, true > QInCirclePred
 

Private Member Functions

template<typename TIterator >
bool isCircularlySeparable (const TIterator &itb, const TIterator &ite, const Point &aPole, Point &Pf, Point &Pl, Point &Qf, Point &Ql)
 

Private Attributes

ConstIterator myBegin
 
ConstIterator myEnd
 
StabbingLineComputerPtr mySegPtr
 
Circle myCircle
 
bool myFlagIsInit
 

Detailed Description

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

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

The algorithm iteratively calls a routine (isCircularlySeparable) that uses Preimage2D in order to compute the whole set of separating (Euclidean) circles passing through a given point. It returns 'false' if the set is empty and 'true' otherwise.

The algorithm may be divided into two steps:

  • The first one consists in the on-line recognition of a DSS using StabbingLineComputer (using at its turn Preimage2D). Once the recogntion stops, the main routine is run. The two incident pixels of each grid edge are scanned a second time in order to compute the whole set of separating (Euclidean) circles passing through the point that made the recognition stop. If the set is not empty, one of the separating circles is chosen as a solution.
  • The second step consists in checking if the centers of the two incident pixels of the next grid edge are lying on either side of the current solution circle. If it turns out that a point is outside of the current solution circle instead of being inside or conversely, the main routine is run. The two incident pixels of each grid edge are scanned a new time in order to compute the whole set of separating (Euclidean) circles passing through the point that made the current solution circle not separating. If the set is not empty, one of the separating circles is chosen as a new solution and so on.

For a DCA of \( n \) grid edges, a trivial upper bound of this algorithm is \( O(n^2) \) because the linear-time routine may be possibly called \( n \) times. But we observed in practice that the routine is called only a few times and that the algorithm is fast.

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();
StabbingCircleComputer<Curve::IncidentPointsRange::ConstIterator> s;
//extension
s.init( r.begin() );
while ( ( s.end() != itEnd )
&&( s.extendFront() ) ) {}
MyDigitalSurface::ConstIterator ConstIterator
Template Parameters
TConstIteratorConstIterator type on STL pairs of 2D points
See also
testStabbingCircleComputer.cpp exampleStabbingCircleComputer.cpp testStabbingLineComputer.cpp exampleStabbingLineComputer.cpp

Definition at line 112 of file StabbingCircleComputer.h.

Member Typedef Documentation

◆ Circle

template<typename TConstIterator >
typedef CircleFrom3Points<Point> DGtal::StabbingCircleComputer< TConstIterator >::Circle
private

Definition at line 133 of file StabbingCircleComputer.h.

◆ ConstIterator

template<typename TConstIterator >
typedef TConstIterator DGtal::StabbingCircleComputer< TConstIterator >::ConstIterator

Definition at line 118 of file StabbingCircleComputer.h.

◆ Pair

template<typename TConstIterator >
typedef IteratorCirculatorTraits<ConstIterator>::Value DGtal::StabbingCircleComputer< TConstIterator >::Pair

Definition at line 123 of file StabbingCircleComputer.h.

◆ PInCirclePred

template<typename TConstIterator >
typedef functors::Point2ShapePredicate<Circle,false,true> DGtal::StabbingCircleComputer< TConstIterator >::PInCirclePred
private

Definition at line 137 of file StabbingCircleComputer.h.

◆ Point

template<typename TConstIterator >
typedef Pair::first_type DGtal::StabbingCircleComputer< TConstIterator >::Point

Definition at line 126 of file StabbingCircleComputer.h.

◆ QInCirclePred

template<typename TConstIterator >
typedef functors::Point2ShapePredicate<Circle,true,true> DGtal::StabbingCircleComputer< TConstIterator >::QInCirclePred
private

Definition at line 139 of file StabbingCircleComputer.h.

◆ Reverse

template<typename TConstIterator >
typedef StabbingCircleComputer<ReverseIterator<ConstIterator> > DGtal::StabbingCircleComputer< TConstIterator >::Reverse

Definition at line 120 of file StabbingCircleComputer.h.

◆ Self

template<typename TConstIterator >
typedef StabbingCircleComputer<ConstIterator> DGtal::StabbingCircleComputer< TConstIterator >::Self

Definition at line 119 of file StabbingCircleComputer.h.

◆ StabbingLineComputerPtr

template<typename TConstIterator >
typedef CowPtr<StabbingLineComputer<ConstIterator> > DGtal::StabbingCircleComputer< TConstIterator >::StabbingLineComputerPtr
private

Definition at line 132 of file StabbingCircleComputer.h.

Constructor & Destructor Documentation

◆ StabbingCircleComputer() [1/2]

template<typename TConstIterator >
DGtal::StabbingCircleComputer< TConstIterator >::StabbingCircleComputer ( )

Constructor.

◆ StabbingCircleComputer() [2/2]

template<typename TConstIterator >
DGtal::StabbingCircleComputer< TConstIterator >::StabbingCircleComputer ( const Self other)

Copy constructor.

Parameters
otherthe object to clone.

◆ ~StabbingCircleComputer()

template<typename TConstIterator >
DGtal::StabbingCircleComputer< TConstIterator >::~StabbingCircleComputer ( )

Destructor.

Member Function Documentation

◆ begin()

template<typename TConstIterator >
ConstIterator DGtal::StabbingCircleComputer< TConstIterator >::begin ( ) const
Returns
segment begin iterator.

Referenced by testStabbingCircleComputer().

◆ BOOST_STATIC_ASSERT() [1/2]

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

◆ BOOST_STATIC_ASSERT() [2/2]

template<typename TConstIterator >
DGtal::StabbingCircleComputer< TConstIterator >::BOOST_STATIC_ASSERT ( (Point::dimension==2)  )

◆ className()

template<typename TConstIterator >
std::string DGtal::StabbingCircleComputer< TConstIterator >::className ( ) const
Returns
the name of the class.

◆ end()

template<typename TConstIterator >
ConstIterator DGtal::StabbingCircleComputer< TConstIterator >::end ( ) const
Returns
segment end iterator.

Referenced by testStabbingCircleComputer().

◆ extendBack()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::extendBack ( )

Backward extension of the segment.

NB: linear in the size of the segment is the worst case

Referenced by testStabbingCircleComputer().

◆ extendFront()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::extendFront ( )

Forward extension of the segment.

NB: linear in the size of the segment is the worst case

Referenced by testStabbingCircleComputer().

◆ getReverse()

template<typename TConstIterator >
Reverse DGtal::StabbingCircleComputer< TConstIterator >::getReverse ( ) const
Returns
a default-constructed instance of Reverse.

Referenced by testStabbingCircleComputer().

◆ getSelf()

template<typename TConstIterator >
Self DGtal::StabbingCircleComputer< TConstIterator >::getSelf ( ) const
Returns
a default-constructed instance of Self

◆ getSeparatingCircle()

template<typename TConstIterator >
Circle DGtal::StabbingCircleComputer< TConstIterator >::getSeparatingCircle ( ) const
Returns
a separating circle.

◆ getStabbingLineComputerPtr()

template<typename TConstIterator >
StabbingLineComputerPtr DGtal::StabbingCircleComputer< TConstIterator >::getStabbingLineComputerPtr ( ) const
Returns
a cow pointer on the StabbingLineComputer used during the initialization step.
See also
isStraight

◆ init()

template<typename TConstIterator >
void DGtal::StabbingCircleComputer< TConstIterator >::init ( const ConstIterator anIt)

Segment initialization

Parameters
anItany iterator

Referenced by main(), and testStabbingCircleComputer().

◆ isCircularlySeparable()

template<typename TConstIterator >
template<typename TIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::isCircularlySeparable ( const TIterator &  itb,
const TIterator &  ite,
const Point aPole,
Point Pf,
Point Pl,
Point Qf,
Point Ql 
)
private

Check if the two sets of points can be separated by circles passing through the given point aPole. If yes, return the four points of support of the partial preimage. The pole and either Pf and Ql or Qf and Pl implicitely describe a separating circle.

Parameters
itbbegin iterator on STL pairs of 2D points.
iteend iterator on STL pairs of 2D points.
aPolethe point the circles pass through.
Pf(returned) first inner point of support.
Pl(returned) last inner point of support.
Qf(returned) first outer point of support.
Ql(returned) last outer point of support.
Template Parameters
TIteratortype of iterator (normal or reverse type)
Returns
'true' if the sets of points can be separated, 'false' otherwise

◆ isExtendableBack()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::isExtendableBack ( )

Backward extension test.

NB: linear in the size of the segment is the worst case

◆ isExtendableFront()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::isExtendableFront ( )

Forward extension test.

NB: linear in the size of the segment is the worst case

Referenced by testStabbingCircleComputer().

◆ isStraight()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::isStraight ( ) const
Returns
boolean equal to 'true' is the segment is straight (infinite radius) and 'false' otherwise.

◆ isValid()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::isValid ( ) const

Checks the validity/consistency of the object.

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

Referenced by testStabbingCircleComputer().

◆ operator!=()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::operator!= ( const Self other) const

Difference operator

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

NB: linear in the size of the segment

◆ operator=()

template<typename TConstIterator >
Self& DGtal::StabbingCircleComputer< TConstIterator >::operator= ( const Self other)

Assignment.

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

◆ operator==()

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::operator== ( const Self other) const

Equality operator

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

NB: linear in the size of the segment

◆ selfDisplay()

template<typename TConstIterator >
void DGtal::StabbingCircleComputer< TConstIterator >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

Field Documentation

◆ myBegin

template<typename TConstIterator >
ConstIterator DGtal::StabbingCircleComputer< TConstIterator >::myBegin
private

segment begin iterator.

Definition at line 292 of file StabbingCircleComputer.h.

◆ myCircle

template<typename TConstIterator >
Circle DGtal::StabbingCircleComputer< TConstIterator >::myCircle
private

Separating circle.

Definition at line 304 of file StabbingCircleComputer.h.

◆ myEnd

template<typename TConstIterator >
ConstIterator DGtal::StabbingCircleComputer< TConstIterator >::myEnd
private

segment end iterator.

Definition at line 296 of file StabbingCircleComputer.h.

◆ myFlagIsInit

template<typename TConstIterator >
bool DGtal::StabbingCircleComputer< TConstIterator >::myFlagIsInit
private

Flag equal to 'true' if mySegPtr has finished its extension 'false' otherwise.

Definition at line 309 of file StabbingCircleComputer.h.

◆ mySegPtr

template<typename TConstIterator >
StabbingLineComputerPtr DGtal::StabbingCircleComputer< TConstIterator >::mySegPtr
private

Pointer to the geometrical DSS.

Definition at line 300 of file StabbingCircleComputer.h.


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