DGtal  1.5.beta
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). More...
 

Public Member Functions

 ShortestPaths ()
 Default constructor. The object is not valid. More...
 
 ShortestPaths (const ShortestPaths &other)=default
 
 ShortestPaths (ShortestPaths &&other)=default
 
ShortestPathsoperator= (const ShortestPaths &other)=default
 
ShortestPathsoperator= (ShortestPaths &&other)=default
 
 ShortestPaths (ConstAlias< TangencyComputer > tgcy_computer, double secure=sqrt(KSpace::dimension))
 
const TangencyComputertangencyComputerPtr () const
 
Index size () const
 
void clear ()
 
void init (Index i)
 
template<typename IndexFwdIterator >
void init (IndexFwdIterator it, IndexFwdIterator itE)
 
bool finished () const
 
const Nodecurrent () const
 
void expand ()
 
bool isValid () const
 
const Pointpoint (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< IndexgetCotangentPoints (Index i) const
 

Protected Attributes

const TangencyComputermyTgcyComputer
 A pointer toward the tangency computer. More...
 
double mySecure
 
std::vector< IndexmyAncestor
 
std::vector< double > myDistance
 Stores for each point its distance to the closest source. More...
 
std::vector< bool > myVisited
 Remembers for each point if it is already visited. More...
 
std::priority_queue< Node, std::vector< Node >, ComparatormyQ
 The queue of points being currently processed. More...
 

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.

116  : myTgcyComputer( nullptr ), mySecure( 0.0 )
117  {}
const TangencyComputer * myTgcyComputer
A pointer toward the tangency computer.

◆ ShortestPaths() [2/4]

template<typename TKSpace >
DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths ( const ShortestPaths other)
default

Copy constructor

Parameters
otherthe object to clone.

◆ ShortestPaths() [3/4]

template<typename TKSpace >
DGtal::TangencyComputer< TKSpace >::ShortestPaths::ShortestPaths ( ShortestPaths &&  other)
default

Move constructor

Parameters
otherthe 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_computerthe tangency computer where shortest paths are computed.
[in]secureThis 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.

152  : myTgcyComputer( &tgcy_computer ),
153  mySecure( std::max( secure, 0.0 ) )
154  {
155  clear();
156  }
int max(int a, int b)

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]iany 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 261 of file TangencyComputer.h.

262  {
263  ASSERT( i < size() );
264  return myAncestor[ i ];
265  }

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 316 of file TangencyComputer.h.

317  { 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.

173  {
174  const auto nb = size();
175  myAncestor = std::vector< Index > ( nb, nb );
176  myDistance = std::vector< double >( nb, std::numeric_limits<double>::infinity() );
177  myVisited = std::vector< bool > ( nb, false );
178  myQ = std::priority_queue< Node, std::vector< Node >, Comparator >();
179  }
std::priority_queue< Node, std::vector< Node >, Comparator > myQ
The queue of points being currently processed.
std::vector< bool > myVisited
Remembers for each point if it is already visited.
std::vector< double > myDistance
Stores for each point its distance to the closest source.

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().

◆ 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 228 of file TangencyComputer.h.

229  {
230  ASSERT( ! finished() );
231  return myQ.top();
232  }

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]iany 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 273 of file TangencyComputer.h.

274  {
275  ASSERT( i < size() );
276  return myDistance[ i ];
277  }

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 321 of file TangencyComputer.h.

322  { 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 217 of file TangencyComputer.h.

218  {
219  return myQ.empty();
220  }

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]ithe 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 290 of file TangencyComputer.h.

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

◆ 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]iany valid index
Note
Must be done before starting computations.

Definition at line 184 of file TangencyComputer.h.

185  {
186  ASSERT( i < size() );
187  myQ.push( std::make_tuple( i, i, 0.0 ) );
188  myAncestor[ i ] = i;
189  myDistance[ i ] = 0.0;
190  myVisited [ i ] = true;
191  }

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,itEa range of valid indices, which are the indices of source points.
Note
Must be done before starting computations.

Definition at line 200 of file TangencyComputer.h.

201  {
202  for ( ; it != itE; ++it )
203  {
204  const auto i = *it;
205  ASSERT( i < size() );
206  myQ.push( std::make_tuple( i, i, 0.0 ) );
207  }
208  const auto elem = myQ.top();
209  const auto i = std::get<0>( elem );
210  myAncestor[ i ] = i;
211  myDistance[ i ] = 0.0;
212  myVisited [ i ] = true;
213  }

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 242 of file TangencyComputer.h.

243  {
244  return myTgcyComputer != nullptr;
245  }

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

◆ isVisited()

template<typename TKSpace >
bool DGtal::TangencyComputer< TKSpace >::ShortestPaths::isVisited ( Index  i) const
inline
Parameters
[in]iany 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 284 of file TangencyComputer.h.

285  {
286  return ancestor( i ) < size();
287  }

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
otherthe 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
otherthe object to clone.
Returns
a reference to 'this'

◆ pathToSource()

template<typename TKSpace >
Path DGtal::TangencyComputer< TKSpace >::ShortestPaths::pathToSource ( Index  i) const
inline
Parameters
[in]iany 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 300 of file TangencyComputer.h.

301  {
302  Path P;
303  if ( ! isVisited( i ) ) return P;
304  P.push_back( i );
305  while ( ancestor( i ) != i )
306  {
307  i = ancestor( i );
308  P.push_back( i );
309  }
310  return P;
311  }
std::vector< Index > Path

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]iany valid index
Returns
the point with index i.

Definition at line 249 of file TangencyComputer.h.

250  {
251  ASSERT( i < size() );
252  return myTgcyComputer->point( i );
253  }
const Point & point(Index i) const

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
currentthe index of the point where we determine its adjacent (here cotangent) to update the queue of the bft.

◆ size()

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

160  {
161  return myTgcyComputer;
162  }

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 326 of file TangencyComputer.h.

327  { return myVisited; }

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

Field Documentation

◆ myAncestor

template<typename TKSpace >
std::vector< Index > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myAncestor
protected

◆ myDistance

template<typename TKSpace >
std::vector< double > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myDistance
protected

◆ myQ

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

◆ 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 338 of file TangencyComputer.h.

◆ myTgcyComputer

◆ myVisited

template<typename TKSpace >
std::vector< bool > DGtal::TangencyComputer< TKSpace >::ShortestPaths::myVisited
protected

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