DGtal  1.4.beta
DGtal::FrechetShortcut< TIterator, TInteger > Class Template Reference

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

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

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

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 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
 TIterator Iterator type on 2D digital points, TInteger type of integer
exampleFrechetShortcut.cpp testFrechetShortcut.cpp
Examples
geometry/curves/exampleFrechetShortcut.cpp.

Definition at line 107 of file FrechetShortcut.h.

## ◆ ConstIterator

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.

## ◆ Coordinate

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.

## ◆ Integer

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.

## ◆ Point

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

Definition at line 125 of file FrechetShortcut.h.

## ◆ Reverse

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

Definition at line 122 of file FrechetShortcut.h.

## ◆ Self

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

Definition at line 121 of file FrechetShortcut.h.

## ◆ Vector

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

Definition at line 126 of file FrechetShortcut.h.

## ◆ FrechetShortcut() [1/3]

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

Default constructor. not valid

## ◆ FrechetShortcut() [2/3]

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

Constructor with initialisation

Parameters
 error an iterator on 2D points

## ◆ FrechetShortcut() [3/3]

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

Copy constructor.

Parameters
 other the object to clone.

## ◆ ~FrechetShortcut()

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

Destructor.

Definition at line 766 of file FrechetShortcut.h.

766 {};

## ◆ begin()

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

## ◆ BOOST_CONCEPT_ASSERT()

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

## ◆ className()

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 std::string DGtal::FrechetShortcut< TIterator, TInteger >::className ( ) const
Returns
the name of the class.

## ◆ computeNewCone()

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

## ◆ end()

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

## ◆ extendFront()

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.

## ◆ getReverse()

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 Reverse DGtal::FrechetShortcut< TIterator, TInteger >::getReverse ( ) const
Returns
a reverse version of '*this'.

## ◆ getSelf()

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

## ◆ init()

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 void DGtal::FrechetShortcut< TIterator, TInteger >::init ( const ConstIterator & it )

Initialisation.

Parameters
 it an iterator on 2D points

## ◆ isBackpathOk()

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

## ◆ isExtendableFront()

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.

## ◆ isValid()

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.

## ◆ operator!=()

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 bool DGtal::FrechetShortcut< TIterator, TInteger >::operator!= ( const Self & other ) const

Difference operator.

Parameters
 other the object to compare with.
Returns
'false' if equal 'true' otherwise

## ◆ operator=()

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 FrechetShortcut& DGtal::FrechetShortcut< TIterator, TInteger >::operator= ( const Self & other )

Assignment.

Parameters
 other the object to copy.
Returns
a reference on 'this'.

## ◆ operator==()

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 bool DGtal::FrechetShortcut< TIterator, TInteger >::operator== ( const Self & other ) const

Equality operator.

Parameters
 other the object to compare with.
Returns
'true' if the objects are equal, false otherwise

## ◆ resetBackpath()

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

## ◆ resetCone()

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

## ◆ selfDisplay()

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
 out the output stream where the object is written.

## ◆ testUpdateBackpath()

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.

## ◆ testUpdateWidth()

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

## ◆ updateBackpath()

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

## ◆ updateWidth()

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

## ◆ myBackpath

template<typename TIterator , typename TInteger = typename IteratorCirculatorTraits<TIterator>::Value::Coordinate>
 std::vector 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 828 of file FrechetShortcut.h.

## ◆ myBegin

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 838 of file FrechetShortcut.h.

## ◆ myCone

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 833 of file FrechetShortcut.h.

## ◆ myEnd

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 842 of file FrechetShortcut.h.

## ◆ myError

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 822 of file FrechetShortcut.h.

The documentation for this class was generated from the following file:
DGtal::trace
Trace trace
Definition: Common.h:154
DGtal::SaturatedSegmentation::SegmentComputerIterator
Aim: Specific iterator to visit all the maximal segments of a saturated segmentation.
Definition: SaturatedSegmentation.h:179
DGtal::Trace::info
std::ostream & info()
DGtal::SaturatedSegmentation::SegmentComputerIterator::begin
const ConstIterator begin() const
LibBoard::Board::BoundingBox
@ BoundingBox
Definition: Board.h:42
DGtal::SaturatedSegmentation::SegmentComputerIterator::end
const ConstIterator end() const
Segmentation
SaturatedSegmentation< SegmentComputer > Segmentation
Definition: testArithmeticalDSSComputerOnSurfels.cpp:56
DGtal::SaturatedSegmentation
Aim: Computes the saturated segmentation, that is the whole set of maximal segments within a range gi...
Definition: SaturatedSegmentation.h:153