DGtal  0.9.3beta
Data Structures | Public Types | Public Member Functions | Protected Attributes
DGtal::FrechetShortcut< TIterator, TInteger > Class Template Reference

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

Inheritance diagram for DGtal::FrechetShortcut< TIterator, TInteger >:
[legend]
Collaboration diagram for DGtal::FrechetShortcut< TIterator, TInteger >:
[legend]

Data Structures

class  Backpath
 
class  Cone
 
struct  Tools
 

Public Types

typedef TInteger Integer
 
typedef TIterator ConstIterator
 
typedef FrechetShortcut< ConstIterator, IntegerSelf
 
typedef FrechetShortcut< std::reverse_iterator< ConstIterator >, IntegerReverse
 
typedef IteratorCirculatorTraits< ConstIterator >::Value Point
 
typedef IteratorCirculatorTraits< ConstIterator >::Value Vector
 
typedef Vector::Coordinate Coordinate
 

Public Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CInteger< TInteger >))
 
 FrechetShortcut ()
 
 FrechetShortcut (double error)
 
void init (const ConstIterator &it)
 
FrechetShortcut getSelf ()
 
 FrechetShortcut (const Self &other)
 
FrechetShortcutoperator= (const Self &other)
 
Reverse getReverse () const
 
bool operator== (const Self &other) const
 
bool operator!= (const Self &other) const
 
 ~FrechetShortcut ()
 
bool isExtendableFront ()
 
bool extendFront ()
 
ConstIterator begin () const
 
ConstIterator end () const
 
std::string className () const
 
bool isValid () const
 
bool updateBackpath ()
 
bool testUpdateBackpath ()
 
bool isBackpathOk ()
 
void resetBackpath ()
 
void resetCone ()
 
bool testUpdateWidth ()
 
Cone computeNewCone ()
 
bool updateWidth ()
 
void selfDisplay (std::ostream &out) const
 

Protected Attributes

double myError
 
std::vector< BackpathmyBackpath
 
Cone myCone
 
ConstIterator myBegin
 
ConstIterator myEnd
 

Detailed Description

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
class DGtal::FrechetShortcut< TIterator, TInteger >

Aim: On-line computation Computation of the longest shortcut according to the Fréchet distance for a given error. See related article: Sivignon, I., (2011). A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance. DGCI 2011. Retrieved from http://link.springer.com/chapter/10.1007/978-3-642-19867-0_28.

Description of class 'FrechetShortcut'

The algorithm we propose uses an approximation of the Fréchet distance, but a guarantee over the quality of the simplification is proved. Moreover, even if the theoretical complexity of the algorithm is in \( O(n log(n)) \), experiments show a linear behaviour in practice.

We denote by \( error(i,j) \) the Fréchet distance between the segment \([p_ip_j]\) and the part of the curve between the points \(p_i\) and \(p_j\). The approximation of the Fréchet distance is based on the fact that \( error(i,j) \) can be upper and lower bounded by a function of two values, namely \( w(i,j)$ \) and \( b(i,j) \), where \( w(i,j)$ \) is the width of the points between \(p_i\) and \(p_j\) in the direction \( p_ip_j \) and \( b(i,j) \) is the length of the longest backpath in this direction.

Then, the algorithm consists in greedily reading the points of the curves from a first point given by myBegin, while updating the values \( w(i,j) \) and \( b(i,j) \) on the fly.

This class is a model of the concept CForwardSegmentComputer

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

Curve::PointsRange r = c.getPointsRange();
typedef FrechetShortcut<Curve::PointsRange::ConstIterator,int> Shortcut;
// Computation of one shortcut
Shortcut s(error);
s.init( r.begin() );
while ( ( s.end() != r.end() )
&&( s.extendFront() ) ) {}
// Computation of a greedy segmentation
typedef GreedySegmentation<Shortcut> Segmentation;
Segmentation theSegmentation( r.begin(), r.end(), Shortcut(error) );
// the segmentation is computed here
Segmentation::SegmentComputerIterator it = theSegmentation.begin();
Segmentation::SegmentComputerIterator itEnd = theSegmentation.end();
for ( ; it != itEnd; ++it) {
s=Shortcut(*it);
trace.info() << s << std::endl;
board << s;
}
board.saveEPS("FrechetShortcutExample.eps", Board2D::BoundingBox, 5000 );
Template Parameters
TIteratorIterator type on 2D digital points, TInteger type of integer
See also
exampleFrechetShortcut.cpp testFrechetShortcut.cpp
Examples:
geometry/curves/exampleFrechetShortcut.cpp.

Definition at line 107 of file FrechetShortcut.h.

Member Typedef Documentation

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef TIterator DGtal::FrechetShortcut< TIterator, TInteger >::ConstIterator

Definition at line 120 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef Vector::Coordinate DGtal::FrechetShortcut< TIterator, TInteger >::Coordinate

Definition at line 127 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef TInteger DGtal::FrechetShortcut< TIterator, TInteger >::Integer

Definition at line 115 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef IteratorCirculatorTraits<ConstIterator>::Value DGtal::FrechetShortcut< TIterator, TInteger >::Point

Definition at line 125 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef FrechetShortcut<std::reverse_iterator<ConstIterator>,Integer> DGtal::FrechetShortcut< TIterator, TInteger >::Reverse

Definition at line 122 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef FrechetShortcut<ConstIterator,Integer> DGtal::FrechetShortcut< TIterator, TInteger >::Self

Definition at line 121 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
typedef IteratorCirculatorTraits<ConstIterator>::Value DGtal::FrechetShortcut< TIterator, TInteger >::Vector

Definition at line 126 of file FrechetShortcut.h.

Constructor & Destructor Documentation

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
DGtal::FrechetShortcut< TIterator, TInteger >::FrechetShortcut ( )

Default constructor. not valid

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
DGtal::FrechetShortcut< TIterator, TInteger >::FrechetShortcut ( double  error)

Constructor with initialisation

Parameters
erroran iterator on 2D points
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
DGtal::FrechetShortcut< TIterator, TInteger >::FrechetShortcut ( const Self other)

Copy constructor.

Parameters
otherthe object to clone.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
DGtal::FrechetShortcut< TIterator, TInteger >::~FrechetShortcut ( )
inline

Destructor.

Definition at line 760 of file FrechetShortcut.h.

760 {};

Member Function Documentation

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
ConstIterator DGtal::FrechetShortcut< TIterator, TInteger >::begin ( ) const
Returns
begin iterator of the FrechetShortcut range.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
DGtal::FrechetShortcut< TIterator, TInteger >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< TInteger >)  )
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
std::string DGtal::FrechetShortcut< TIterator, TInteger >::className ( ) const
Returns
the name of the class.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
Cone DGtal::FrechetShortcut< TIterator, TInteger >::computeNewCone ( )

Computes the cone defined by the point *myBegin and the new point myEnd + 1 and intersect it with myCone (unchanged)

Returns
the new cone
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
ConstIterator DGtal::FrechetShortcut< TIterator, TInteger >::end ( ) const
Returns
end iterator of the FrechetShortcut range.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::extendFront ( )

Tests whether the FrechetShortcut can be extended at the front. Extend the FrechetShortcut if yes.

Returns
'true' if yes, 'false' otherwise.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
Reverse DGtal::FrechetShortcut< TIterator, TInteger >::getReverse ( ) const
Returns
a reverse version of '*this'.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
FrechetShortcut DGtal::FrechetShortcut< TIterator, TInteger >::getSelf ( )
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
void DGtal::FrechetShortcut< TIterator, TInteger >::init ( const ConstIterator it)

Initialisation.

Parameters
itan iterator on 2D points
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::isBackpathOk ( )

Test if there exist a backpath of length greater than the threshold

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::isExtendableFront ( )

Tests whether the FrechetShortcut can be extended at the front.

Returns
'true' if yes, 'false' otherwise.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::operator!= ( const Self other) const

Difference operator.

Parameters
otherthe object to compare with.
Returns
'false' if equal 'true' otherwise
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
FrechetShortcut& DGtal::FrechetShortcut< TIterator, TInteger >::operator= ( const Self other)

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::operator== ( const Self other) const

Equality operator.

Parameters
otherthe object to compare with.
Returns
'true' if the objects are equal, false otherwise
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
void DGtal::FrechetShortcut< TIterator, TInteger >::resetBackpath ( )

Reset the backpaths before the computation of a new shortcut

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
void DGtal::FrechetShortcut< TIterator, TInteger >::resetCone ( )

Reset the cone before the computation of a new shortcut

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
void DGtal::FrechetShortcut< TIterator, TInteger >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::testUpdateBackpath ( )

Test if there exist a backpath of length greater than the threshold after the addition of the point pointed by *myEnd+1, but does not modify myBackpath.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::testUpdateWidth ( )

Test if the new direction belongs to the new cone, but does not modify myCone

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::updateBackpath ( )

Updates the backpaths (one per octant) according to the new point

Returns
'true' if the length of the longest backpath is lower than the threshold, false otherwise
template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
bool DGtal::FrechetShortcut< TIterator, TInteger >::updateWidth ( )

Updates the width according to the new point

Returns
true if the width is lower than the error, false otherwise

Field Documentation

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
std::vector<Backpath> DGtal::FrechetShortcut< TIterator, TInteger >::myBackpath
protected

Vector of 8 backpaths, one per octant. Stores all the information needed to update the length of the longest backpath.

Definition at line 822 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
ConstIterator DGtal::FrechetShortcut< TIterator, TInteger >::myBegin
protected

ConstIterator pointing to the back of the shortcut

Definition at line 832 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
Cone DGtal::FrechetShortcut< TIterator, TInteger >::myCone
protected

Cone used to update the width

Definition at line 827 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
ConstIterator DGtal::FrechetShortcut< TIterator, TInteger >::myEnd
protected

ConstIterator pointing to the front of the shortcut

Definition at line 836 of file FrechetShortcut.h.

template<typename TIterator, typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
double DGtal::FrechetShortcut< TIterator, TInteger >::myError
protected

Error parameter used to compute the shortcut

Definition at line 816 of file FrechetShortcut.h.


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