DGtal::TangencyComputer< TKSpace >::ShortestPaths Struct Reference

#include <DGtal/geometry/volumes/TangencyComputer.h>

Data Structures
struct	Comparator

Public Types
typedef std::tuple< Index, Index, double >	Node
	Type used for Dijkstra's algorithm queue (point, ancestor, distance).

Public Member Functions
	ShortestPaths ()
	Default constructor. The object is not valid.
	ShortestPaths (const ShortestPaths &other)=default
	ShortestPaths (ShortestPaths &&other)=default
ShortestPaths &	operator= (const ShortestPaths &other)=default
ShortestPaths &	operator= (ShortestPaths &&other)=default
	ShortestPaths (ConstAlias< TangencyComputer > tgcy_computer, double secure=sqrt(KSpace::dimension))
const TangencyComputer *	tangencyComputerPtr () const
Index	size () const
void	clear ()
void	clearVisited (const std::vector< std::size_t > &visited)
void	init (Index i)
template<typename IndexFwdIterator >
void	init (IndexFwdIterator it, IndexFwdIterator itE)
bool	finished () const
const Node &	current () const
void	expand ()
bool	isValid () const
const Point &	point (Index i) const
Index	ancestor (Index i) const
double	distance (Index i) const
bool	isVisited (Index i) const
Path	pathToSource (Index i) const
const std::vector< Index > &	ancestors () const
const std::vector< double > &	distances () const
const std::vector< bool > &	visitedPoints () const

Static Public Member Functions
static double	infinity ()

Protected Member Functions
void	propagate (Index current)
std::vector< Index >	getCotangentPoints (Index i) const

Protected Attributes
const TangencyComputer *	myTgcyComputer
	A pointer toward the tangency computer.
double	mySecure
std::vector< Index >	myAncestor
std::vector< double >	myDistance
	Stores for each point its distance to the closest source.
std::vector< bool >	myVisited
	Remembers for each point if it is already visited.
std::priority_queue< Node, std::vector< Node >, Comparator >	myQ
	The queue of points being currently processed.

Detailed Description

template<typename TKSpace>
struct DGtal::TangencyComputer< TKSpace >::ShortestPaths

This structure is a state machine that computes shortest paths in a digital set. Internally, it references a TangencyComputer.

Definition at line 95 of file TangencyComputer.h.

Member Typedef Documentation

Node

template<typename TKSpace >

typedef std::tuple< Index, Index, double > DGtal::TangencyComputer< TKSpace >::ShortestPaths::Node

Type used for Dijkstra's algorithm queue (point, ancestor, distance).

Definition at line 97 of file TangencyComputer.h.

Constructor & Destructor Documentation

ShortestPaths() [1/4]

template<typename TKSpace >

DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths ( )

inline

Default constructor. The object is not valid.

Definition at line 115 of file TangencyComputer.h.

        : myTgcyComputer( nullptr ), mySecure( 0.0 )
      {}

ShortestPaths() [2/4]

template<typename TKSpace >

DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths ( const ShortestPaths &  other )

default

Copy constructor

Parameters

other

the object to clone.

ShortestPaths() [3/4]

template<typename TKSpace >

DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths ( ShortestPaths &&  other )

default

Move constructor

Parameters

other

the object to clone.

ShortestPaths() [4/4]

template<typename TKSpace >

DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths ( ConstAlias< TangencyComputer >  tgcy_computer, double  secure = sqrt( KSpace::dimension )  )

inline

Constructs a ShorthestPaths object and references the given TangencyComputer tgcy_computer. It initialized the object so that it can start a new computation.

Parameters

[in]	tgcy_computer	the tangency computer where shortest paths are computed.
[in]	secure	This value is used to prune vertices in the bft. If it is greater or equal to \( \sqrt{d} \) where d is the dimension, the shortest path algorithm is guaranteed to output the correct result. If the value is smaller (down to 0.0), the algorithm is much faster but a few shortest path may be missed.

Note

Takes O(n) time complexity, where n is the number of points in the TangencyComputer object.

Definition at line 150 of file TangencyComputer.h.

        : myTgcyComputer( &tgcy_computer ),
          mySecure( std::max( secure, 0.0 ) )
      {
        clear();
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear().

Member Function Documentation

ancestor()

template<typename TKSpace >

Index DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestor ( Index  i ) const

inline

Parameters

[in]

i

any valid index

Returns

the index of an ancestor to i.

Precondition

The ancestor is valid only when isVisited(i) is true, so after it was a current() node and expand() has been called.

Definition at line 283 of file TangencyComputer.h.

      {
        ASSERT( i < size() );
        return myAncestor[ i ];
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor, and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::isVisited(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::pathToSource().

ancestors()

template<typename TKSpace >

const std::vector< Index > & DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestors ( ) const

inline

Returns

a const reference to the array storing for each point its ancestor in the shortest path, or itself if it was a source.

Definition at line 338 of file TangencyComputer.h.

      { return myAncestor; }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor.

clear()

template<typename TKSpace >

void DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear ( )

inline

Clears the object and prepares it for a shortest path computation.

Definition at line 172 of file TangencyComputer.h.

      {
        const auto nb = size();
        myAncestor = std::vector< Index > ( nb, nb );
        myDistance = std::vector< double >( nb, std::numeric_limits<double>::infinity() );
        myVisited  = std::vector< bool >  ( nb, false );
        myQ        = std::priority_queue< Node, std::vector< Node >, Comparator >();
  }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited, and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths().

clearVisited()

template<typename TKSpace >

void DGtal::TangencyComputer< TKSpace >::ShortestPaths::clearVisited ( const std::vector< std::size_t > &  visited )

inline

Clears the object solely at the given range of points, and prepares it for a shortest path computation. Avoids complete reinitialization if a first computation was only local and touched only this range of points.

Parameters

visited

the range of points that was visited in a first computation pass.

Note

Complexity is O(card(visited)), while clear has linear complexity wrt the total number of points.

Definition at line 191 of file TangencyComputer.h.

      {
        const auto nb = size();
        for ( auto v : visited )
          {
            myAncestor[ v ] = nb;
            myDistance[ v ] = std::numeric_limits<double>::infinity();
            myVisited [ v ] = false;
          }
        myQ = std::priority_queue< Node, std::vector< Node >, Comparator >();
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited, and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

current()

template<typename TKSpace >

const Node & DGtal::TangencyComputer< TKSpace >::ShortestPaths::current ( ) const

inline

Returns

a const reference to the current node on top of the queue of bft, a triplet '(i,a,d)' where i is the index of the point, a is the index of its ancestor, d is the distance of i to the closest source.

Precondition

valid only if not 'finished()'.

Definition at line 250 of file TangencyComputer.h.

      {
        ASSERT( ! finished() );
        return myQ.top();
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::finished(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ.

distance()

template<typename TKSpace >

double DGtal::TangencyComputer< TKSpace >::ShortestPaths::distance ( Index  i ) const

inline

Parameters

[in]

i

any valid index

Returns

the distance of point i to the closest source.

Precondition

The distance is correct only when isVisited(i) is true, so after it was a current() node and expand() has been called.

Definition at line 295 of file TangencyComputer.h.

      {
        ASSERT( i < size() );
        return myDistance[ i ];
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance, and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

distances()

template<typename TKSpace >

const std::vector< double > & DGtal::TangencyComputer< TKSpace >::ShortestPaths::distances ( ) const

inline

Returns

a const reference to the array storing for each point its distance to the closest source.

Definition at line 343 of file TangencyComputer.h.

      { return myDistance; }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance.

expand()

template<typename TKSpace >

void DGtal::TangencyComputer< TKSpace >::ShortestPaths::expand

(

)

Goes to the next point in the bft.

Precondition

valid only if not already 'finished()'.

Note

The core method of shortest paths algorithm.

finished()

template<typename TKSpace >

bool DGtal::TangencyComputer< TKSpace >::ShortestPaths::finished ( ) const

inline

Returns

'true' if the traversal is finished, i.e. when the queue is empty.

Definition at line 239 of file TangencyComputer.h.

      {
        return myQ.empty();
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ.

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::current().

getCotangentPoints()

template<typename TKSpace >

std::vector< Index > DGtal::TangencyComputer< TKSpace >::ShortestPaths::getCotangentPoints ( Index  i ) const

protected

Extracts a subset of cotangent points by a breadth-first traversal. Used to update the queue when computing shortest paths.

Parameters

[in]

i

the index of a point

Returns

the indices of the other points of the shape that are cotangent to a.

infinity()

template<typename TKSpace >

static double DGtal::TangencyComputer< TKSpace >::ShortestPaths::infinity ( )

inlinestatic

Returns

the infinity distance (point is not computed or unreachable)

Definition at line 312 of file TangencyComputer.h.

      {
        return std::numeric_limits<double>::infinity();
      }

init() [1/2]

template<typename TKSpace >

void DGtal::TangencyComputer< TKSpace >::ShortestPaths::init ( Index  i )

inline

Adds the point with index i as a source point

Parameters

[in]

i

any valid index

Note

Must be done before starting computations.

Definition at line 206 of file TangencyComputer.h.

      {
        ASSERT( i < size() );
        myQ.push( std::make_tuple( i, i, 0.0 ) );
        myAncestor[ i ] = i;
        myDistance[ i ] = 0.0;
        myVisited [ i ] = true;
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited, and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

init() [2/2]

template<typename TKSpace >

template<typename IndexFwdIterator >

void DGtal::TangencyComputer< TKSpace >::ShortestPaths::init ( IndexFwdIterator  it, IndexFwdIterator  itE  )

inline

Adds a range of indices as source points

Parameters

[in]

it,itE

a range of valid indices, which are the indices of source points.

Note

Must be done before starting computations.

Definition at line 222 of file TangencyComputer.h.

      {
        for ( ; it != itE; ++it )
          {
            const auto i = *it;
            ASSERT( i < size() );
            myQ.push( std::make_tuple( i, i, 0.0 ) );
          }
        const auto elem = myQ.top();
        const auto i    = std::get<0>( elem );
        myAncestor[ i ] = i;
        myDistance[ i ] = 0.0;
        myVisited [ i ] = true;
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ, DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited, and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

isValid()

template<typename TKSpace >

bool DGtal::TangencyComputer< TKSpace >::ShortestPaths::isValid ( ) const

inline

Returns

'true' if the object is valid, i.e. when its tangency computer exists.

Definition at line 264 of file TangencyComputer.h.

      {
        return myTgcyComputer != nullptr;
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myTgcyComputer.

isVisited()

template<typename TKSpace >

bool DGtal::TangencyComputer< TKSpace >::ShortestPaths::isVisited ( Index  i ) const

inline

Parameters

[in]

i

any valid index

Returns

'true' iff point is already visited by the bft, i.e. after it was a current() node and expand() has been called.

Definition at line 306 of file TangencyComputer.h.

      {
        return ancestor( i ) < size();
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestor(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::pathToSource().

operator=() [1/2]

template<typename TKSpace >

ShortestPaths & DGtal::TangencyComputer< TKSpace >::ShortestPaths::operator= ( const ShortestPaths &  other )

default

Assignment

Parameters

other

the object to clone.

Returns

a reference to 'this'

operator=() [2/2]

template<typename TKSpace >

ShortestPaths & DGtal::TangencyComputer< TKSpace >::ShortestPaths::operator= ( ShortestPaths &&  other )

default

Move assignment

Parameters

other

the object to clone.

Returns

a reference to 'this'

pathToSource()

template<typename TKSpace >

Path DGtal::TangencyComputer< TKSpace >::ShortestPaths::pathToSource ( Index  i ) const

inline

Parameters

[in]

i

any valid point index

Returns

the path from this point to its closest source, or an empty path if it cannot be computed (for instance, the point was not visited yet).

Definition at line 322 of file TangencyComputer.h.

      {
        Path P;
        if ( ! isVisited( i ) ) return P;
        P.push_back( i );
        while ( ancestor( i ) != i )
          {
            i = ancestor( i );
            P.push_back( i );
          }
        return P;
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestor(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::isVisited().

point()

template<typename TKSpace >

const Point & DGtal::TangencyComputer< TKSpace >::ShortestPaths::point ( Index  i ) const

inline

Parameters

[in]

i

any valid index

Returns

the point with index i.

Definition at line 271 of file TangencyComputer.h.

      {
        ASSERT( i < size() );
        return myTgcyComputer->point( i );
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myTgcyComputer, DGtal::TangencyComputer< TKSpace >::point(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

propagate()

template<typename TKSpace >

void DGtal::TangencyComputer< TKSpace >::ShortestPaths::propagate ( Index  current )

protected

Updates the queue with the cotangent points of the point given in parameter.

Parameters

current

the index of the point where we determine its adjacent (here cotangent) to update the queue of the bft.

size()

template<typename TKSpace >

Index DGtal::TangencyComputer< TKSpace >::ShortestPaths::size ( ) const

inline

Returns

the number of points in the associated tangency computer

Definition at line 165 of file TangencyComputer.h.

      {
        return myTgcyComputer->size();
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myTgcyComputer, and DGtal::TangencyComputer< TKSpace >::size().

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestor(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clearVisited(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::distance(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::isVisited(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::point().

tangencyComputerPtr()

template<typename TKSpace >

const TangencyComputer * DGtal::TangencyComputer< TKSpace >::ShortestPaths::tangencyComputerPtr ( ) const

inline

Returns

a pointer on the tangency computer.

Definition at line 159 of file TangencyComputer.h.

      {
        return myTgcyComputer;
      }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myTgcyComputer.

visitedPoints()

template<typename TKSpace >

const std::vector< bool > & DGtal::TangencyComputer< TKSpace >::ShortestPaths::visitedPoints ( ) const

inline

Returns

a const reference to the array storing for each point if it is already visited.

Definition at line 348 of file TangencyComputer.h.

      { return myVisited; }

References DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited.

Field Documentation

myAncestor

template<typename TKSpace >

std::vector< Index > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor

protected

Stores for each point its ancestor in the shortest path, or itself if it was a source.

Definition at line 363 of file TangencyComputer.h.

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestor(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::ancestors(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clearVisited(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::init().

myDistance

template<typename TKSpace >

std::vector< double > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance

protected

Stores for each point its distance to the closest source.

Definition at line 365 of file TangencyComputer.h.

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clearVisited(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::distance(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::distances(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::init().

myQ

template<typename TKSpace >

std::priority_queue< Node, std::vector< Node >, Comparator > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myQ

protected

The queue of points being currently processed.

Definition at line 369 of file TangencyComputer.h.

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clearVisited(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::current(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::finished(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::init().

mySecure

template<typename TKSpace >

double DGtal::TangencyComputer< TKSpace >::ShortestPaths::mySecure

protected

This value is used to prune vertices in the bft. If it is greater or equal to \( \sqrt{d} \) where d is the dimension, the shortest path algorithm is guaranteed to output the correct result. If the value is smaller (down to 0.0), the algorithm is much faster but a few shortest path may be missed.

Definition at line 360 of file TangencyComputer.h.

myTgcyComputer

template<typename TKSpace >

const TangencyComputer* DGtal::TangencyComputer< TKSpace >::ShortestPaths::myTgcyComputer

protected

A pointer toward the tangency computer.

Definition at line 353 of file TangencyComputer.h.

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::isValid(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::point(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::size(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::tangencyComputerPtr().

myVisited

template<typename TKSpace >

std::vector< bool > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited

protected

Remembers for each point if it is already visited.

Definition at line 367 of file TangencyComputer.h.

Referenced by DGtal::TangencyComputer< TKSpace >::ShortestPaths::clear(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::clearVisited(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), DGtal::TangencyComputer< TKSpace >::ShortestPaths::init(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::visitedPoints().

---

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

• TangencyComputer.h