DGtal: 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. More...

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

Public Types
typedef TConstIterator	ConstIterator

typedef StabbingCircleComputer< ConstIterator >	Self

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)

Self &	operator= (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< Point >	Circle

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 >

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(); 
  Curve::IncidentPointsRange::ConstIterator itEnd (r.end()); 
 
  StabbingCircleComputer<Curve::IncidentPointsRange::ConstIterator> s; 
  //extension
  s.init( r.begin() );
  while ( ( s.end() != itEnd )
        &&( s.extendFront() ) ) {}

Template Parameters

TConstIterator ConstIterator 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

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

anIt	any 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

itb	begin iterator on STL pairs of 2D points.
ite	end iterator on STL pairs of 2D points.
aPole	the 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

TIterator type 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

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

other the object to copy.

Returns: a reference on 'this'.

◆ operator==()

template<typename TConstIterator >

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

Equality operator

Parameters

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

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

StabbingCircleComputer.h

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

◆ Circle

◆ ConstIterator

◆ Pair

◆ PInCirclePred

◆ Point

◆ QInCirclePred

◆ Reverse

◆ Self

◆ StabbingLineComputerPtr

Constructor & Destructor Documentation

◆ StabbingCircleComputer() [1/2]

◆ StabbingCircleComputer() [2/2]

◆ ~StabbingCircleComputer()

Member Function Documentation

◆ begin()

◆ BOOST_STATIC_ASSERT() [1/2]

◆ BOOST_STATIC_ASSERT() [2/2]

◆ className()

◆ end()

◆ extendBack()

◆ extendFront()

◆ getReverse()

◆ getSelf()

◆ getSeparatingCircle()

◆ getStabbingLineComputerPtr()

◆ init()

◆ isCircularlySeparable()

◆ isExtendableBack()

◆ isExtendableFront()

◆ isStraight()

◆ isValid()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ selfDisplay()

Field Documentation

◆ myBegin

◆ myCircle

◆ myEnd

◆ myFlagIsInit

◆ mySegPtr

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