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>

Data Structures
class	Backpath

class	Cone

struct	Tools

Public Types
typedef TInteger	Integer

typedef TIterator	ConstIterator

typedef FrechetShortcut< ConstIterator, Integer >	Self

typedef FrechetShortcut< std::reverse_iterator< ConstIterator >, Integer >	Reverse

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)

FrechetShortcut &	operator= (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< Backpath >	myBackpath

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

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

◆ 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<ConstIterator>::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<std::reverse_iterator<ConstIterator>,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<ConstIterator,Integer> 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<ConstIterator>::Value DGtal::FrechetShortcut< TIterator, TInteger >::Vector

Definition at line 126 of file FrechetShortcut.h.

Constructor & Destructor Documentation

◆ 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{};

Member Function Documentation

◆ 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

Field Documentation

◆ myBackpath

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

FrechetShortcut.h

Data Structures

Public Types

Public Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ConstIterator

◆ Coordinate

◆ Integer

◆ Point

◆ Reverse

◆ Self

◆ Vector

Constructor & Destructor Documentation

◆ FrechetShortcut() [1/3]

◆ FrechetShortcut() [2/3]

◆ FrechetShortcut() [3/3]

◆ ~FrechetShortcut()

Member Function Documentation

◆ begin()

◆ BOOST_CONCEPT_ASSERT()

◆ className()

◆ computeNewCone()

◆ end()

◆ extendFront()

◆ getReverse()

◆ getSelf()

◆ init()

◆ isBackpathOk()

◆ isExtendableFront()

◆ isValid()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ resetBackpath()

◆ resetCone()

◆ selfDisplay()

◆ testUpdateBackpath()

◆ testUpdateWidth()

◆ updateBackpath()

◆ updateWidth()

Field Documentation

◆ myBackpath

◆ myBegin

◆ myCone

◆ myEnd

◆ myError