DGtal  1.3.beta
Data Structures | Public Types | Protected Attributes | Private Member Functions | Friends
DGtal::TangencyComputer< TKSpace > Class Template Reference

Aim: A class that computes tangency to a given digital set. It provides services to compute all the cotangent points to a given point, or to compute shortest paths. More...

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

Data Structures

struct  ShortestPaths
 

Public Types

typedef TangencyComputer< TKSpace > Self
 
typedef TKSpace KSpace
 
typedef KSpace::Space Space
 
typedef KSpace::Point Point
 
typedef KSpace::Vector Vector
 
typedef HyperRectDomain< SpaceDomain
 
typedef std::size_t Index
 
typedef std::size_t Size
 
typedef std::vector< IndexPath
 

Public Member Functions

Standard services (construction, initialization, assignment)
 TangencyComputer ()=default
 Constructor. The object is invalid. More...
 
 TangencyComputer (const Self &other)=default
 
 TangencyComputer (Self &&other)=default
 
Selfoperator= (const Self &other)=default
 
Selfoperator= (Self &&other)=default
 
 TangencyComputer (Clone< KSpace > aK)
 
template<typename PointIterator >
void init (PointIterator itB, PointIterator itE)
 
Accessors services
const KSpacespace () const
 
Size size () const
 
const std::vector< Point > & points () const
 
const Pointpoint (Index i) const
 
Size index (const Point &a) const
 
const CellGeometry< KSpace > & cellCover () const
 
double length (const Path &path) const
 
Tangency services
bool arePointsCotangent (const Point &a, const Point &b) const
 
std::vector< IndexgetCotangentPoints (const Point &a) const
 
std::vector< IndexgetCotangentPoints (const Point &a, const std::vector< bool > &to_avoid) const
 
Shortest paths services
ShortestPaths makeShortestPaths (double secure=sqrt(KSpace::dimension)) const
 
std::vector< PathshortestPaths (const std::vector< Index > &sources, const std::vector< Index > &targets, double secure=sqrt(KSpace::dimension), bool verbose=false) const
 
Path shortestPath (Index source, Index target, double secure=sqrt(KSpace::dimension), bool verbose=false) const
 

Protected Attributes

KSpace myK
 The cellular grid space where computations are done. More...
 
DigitalConvexity< KSpacemyDConv
 The digital convexity object used to check full convexity. More...
 
std::vector< VectormyN
 The vector of all vectors to neighbors (8 in 2D, 26 in 3D, etc). More...
 
std::vector< double > myDN
 
std::vector< PointmyX
 The vector of points defining the digital shape under study. More...
 
CellGeometry< KSpacemyCellCover
 The cell geometry representing all the cells touching the digital shape. More...
 
std::unordered_map< Point, IndexmyPt2Index
 A map giving for each point its index. More...
 

Private Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CCellularGridSpaceND< TKSpace >))
 
void setUp ()
 Precomputes some neighborhood tables at construction. More...
 

Friends

class ShortestPaths
 ShortestPaths may access to datas of TangencyComputer. More...
 

Detailed Description

template<typename TKSpace>
class DGtal::TangencyComputer< TKSpace >

Aim: A class that computes tangency to a given digital set. It provides services to compute all the cotangent points to a given point, or to compute shortest paths.

Description of template class 'TangencyComputer'

See also
moduleDigitalConvexityApplications
Template Parameters
TKSpacean arbitrary model of CCellularGridSpaceND.
Examples
geometry/volumes/fullConvexityShortestPaths3D.cpp, and geometry/volumes/fullConvexitySphereGeodesics.cpp.

Definition at line 72 of file TangencyComputer.h.

Member Typedef Documentation

◆ Domain

template<typename TKSpace >
typedef HyperRectDomain< Space > DGtal::TangencyComputer< TKSpace >::Domain

Definition at line 82 of file TangencyComputer.h.

◆ Index

template<typename TKSpace >
typedef std::size_t DGtal::TangencyComputer< TKSpace >::Index

Definition at line 83 of file TangencyComputer.h.

◆ KSpace

template<typename TKSpace >
typedef TKSpace DGtal::TangencyComputer< TKSpace >::KSpace

Definition at line 78 of file TangencyComputer.h.

◆ Path

template<typename TKSpace >
typedef std::vector< Index > DGtal::TangencyComputer< TKSpace >::Path

Definition at line 85 of file TangencyComputer.h.

◆ Point

template<typename TKSpace >
typedef KSpace::Point DGtal::TangencyComputer< TKSpace >::Point

Definition at line 80 of file TangencyComputer.h.

◆ Self

template<typename TKSpace >
typedef TangencyComputer< TKSpace > DGtal::TangencyComputer< TKSpace >::Self

Definition at line 77 of file TangencyComputer.h.

◆ Size

template<typename TKSpace >
typedef std::size_t DGtal::TangencyComputer< TKSpace >::Size

Definition at line 84 of file TangencyComputer.h.

◆ Space

template<typename TKSpace >
typedef KSpace::Space DGtal::TangencyComputer< TKSpace >::Space

Definition at line 79 of file TangencyComputer.h.

◆ Vector

template<typename TKSpace >
typedef KSpace::Vector DGtal::TangencyComputer< TKSpace >::Vector

Definition at line 81 of file TangencyComputer.h.

Constructor & Destructor Documentation

◆ TangencyComputer() [1/4]

template<typename TKSpace >
DGtal::TangencyComputer< TKSpace >::TangencyComputer ( )
default

Constructor. The object is invalid.

◆ TangencyComputer() [2/4]

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

Copy constructor.

Parameters
otherthe object to clone.

◆ TangencyComputer() [3/4]

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

Move constructor.

Parameters
otherthe object to move

◆ TangencyComputer() [4/4]

template<typename TKSpace >
DGtal::TangencyComputer< TKSpace >::TangencyComputer ( Clone< KSpace aK)

Constructor from digital space.

Parameters
aKthe input Khalimsky space, which is cloned.

Member Function Documentation

◆ arePointsCotangent()

template<typename TKSpace >
bool DGtal::TangencyComputer< TKSpace >::arePointsCotangent ( const Point a,
const Point b 
) const

Tells is two points are cotangent with respect to the current digital set.

Parameters
[in]aany point
[in]bany point
Returns
'true' if and only if a and b are cotangent in this set.

◆ BOOST_CONCEPT_ASSERT()

template<typename TKSpace >
DGtal::TangencyComputer< TKSpace >::BOOST_CONCEPT_ASSERT ( (concepts::CCellularGridSpaceND< TKSpace >)  )
private

◆ cellCover()

template<typename TKSpace >
const CellGeometry< KSpace >& DGtal::TangencyComputer< TKSpace >::cellCover ( ) const
inline
Returns
a const reference to the cell geometry of the current digital set.

Definition at line 441 of file TangencyComputer.h.

442  { return myCellCover; }

References DGtal::TangencyComputer< TKSpace >::myCellCover.

◆ getCotangentPoints() [1/2]

template<typename TKSpace >
std::vector< Index > DGtal::TangencyComputer< TKSpace >::getCotangentPoints ( const Point a) const

Extracts cotangent points by a breadth-first traversal.

Parameters
[in]aany point
Returns
the indices of the other points of the shape that are cotangent to a.

◆ getCotangentPoints() [2/2]

template<typename TKSpace >
std::vector< Index > DGtal::TangencyComputer< TKSpace >::getCotangentPoints ( const Point a,
const std::vector< bool > &  to_avoid 
) const

Extracts a subset of cotangent points by a breadth-first traversal.

Parameters
[in]aany point
[in]to_avoidif 'to_avoid[ i ]' is true, then the point of index i is not visited by the bft.
Returns
the indices of the other points of the shape that are cotangent to a.

◆ index()

template<typename TKSpace >
Size DGtal::TangencyComputer< TKSpace >::index ( const Point a) const
inline
Parameters
aany point
Returns
its index or size() if the point is not in the object
Note
Time complexity is amortized constant.

Definition at line 434 of file TangencyComputer.h.

435  {
436  const auto p = myPt2Index.find( a );
437  return p == myPt2Index.cend() ? size() : p->second;
438  }

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

◆ init()

template<typename TKSpace >
template<typename PointIterator >
void DGtal::TangencyComputer< TKSpace >::init ( PointIterator  itB,
PointIterator  itE 
)

Init the object with the points of the range itB, itE Points within this range are indexed in the same order.

Template Parameters
PointIteratorany model of ForwardIterator on Point.
Parameters
[in]itBan iterator pointing at the beginning of the range.
[in]itEan iterator pointing after the end of the range.

Referenced by main(), and SCENARIO().

◆ length()

template<typename TKSpace >
double DGtal::TangencyComputer< TKSpace >::length ( const Path path) const
inline
Parameters
[in]patha sequence of point indices describing a valid path.
Returns
its Euclidean length.

Definition at line 446 of file TangencyComputer.h.

447  {
448  auto eucl_d = [] ( const Point& p, const Point& q )
449  { return ( p - q ).norm(); };
450  double l = 0.0;
451  for ( auto i = 1; i < path.size(); i++ )
452  l += eucl_d( point( path[ i-1 ] ), point( path[ i ] ) );
453  return l;
454  }

References DGtal::TangencyComputer< TKSpace >::point().

Referenced by main().

◆ makeShortestPaths()

template<typename TKSpace >
ShortestPaths DGtal::TangencyComputer< TKSpace >::makeShortestPaths ( double  secure = sqrt(KSpace::dimension)) const

Returns a ShortestPaths object that gives a lot of control when computing shortest paths. You should use it instead of TangencyComputer::shortestPaths or TangencyComputer::shortestPath when (1) you wish to compute distances to several sources, (2) you wish to store the result for further use, (4) and more generally if you wish to have more control on distance computations.

Parameters
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.
Returns
a ShortestPaths object that allows shortest path computations.

Referenced by main(), and SCENARIO().

◆ operator=() [1/2]

template<typename TKSpace >
Self& DGtal::TangencyComputer< TKSpace >::operator= ( const Self other)
default

Assigment

Parameters
otherthe object to clone
Returns
a reference to 'this'

◆ operator=() [2/2]

template<typename TKSpace >
Self& DGtal::TangencyComputer< TKSpace >::operator= ( Self &&  other)
default

Move assigment

Parameters
otherthe object to clone
Returns
a reference to 'this'

◆ point()

template<typename TKSpace >
const Point& DGtal::TangencyComputer< TKSpace >::point ( Index  i) const
inline
Parameters
iany valid point index (between 0 included and 'size()' excluded)
Returns
a const reference to the corresponding point.

Definition at line 428 of file TangencyComputer.h.

429  { return myX[ i ]; }

References DGtal::TangencyComputer< TKSpace >::myX.

Referenced by DGtal::TangencyComputer< TKSpace >::length(), main(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::point().

◆ points()

template<typename TKSpace >
const std::vector< Point >& DGtal::TangencyComputer< TKSpace >::points ( ) const
inline
Returns
a const reference to the points defining the digital set.

Definition at line 423 of file TangencyComputer.h.

424  { return myX; }

References DGtal::TangencyComputer< TKSpace >::myX.

◆ setUp()

template<typename TKSpace >
void DGtal::TangencyComputer< TKSpace >::setUp ( )
private

Precomputes some neighborhood tables at construction.

◆ shortestPath()

template<typename TKSpace >
Path DGtal::TangencyComputer< TKSpace >::shortestPath ( Index  source,
Index  target,
double  secure = sqrt(KSpace::dimension),
bool  verbose = false 
) const

This function can be used to compute directly a shortest path from a source to a target, returned as a sequence of point indices, where the first is the source and the last is the target. It returns an empty sequence if there is no path between them.

Parameters
[in]sourcethe index of the source point.
[in]targetthe index of the target point.
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.
[in]verbosewhen 'true' some information are displayed during computation.
Returns
the sequence of point indices from source to target, i.e. [source, ..., target], which form a valid path in the object.
Note
Builds two ShortestPaths objects and stops when they meet.

◆ shortestPaths()

template<typename TKSpace >
std::vector< Path > DGtal::TangencyComputer< TKSpace >::shortestPaths ( const std::vector< Index > &  sources,
const std::vector< Index > &  targets,
double  secure = sqrt(KSpace::dimension),
bool  verbose = false 
) const

This function can be used to compute directly several shortest paths from given sources to a set of targets. Each returned path starts from the source and ends at the closest target. The path is empty if there is no path between them.

Parameters
[in]sourcesthe indices of the n source points.
[in]targetsthe indices of the possible target points.
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.
[in]verbosewhen 'true' some information are displayed during computation.
Returns
the n shortest paths from each source point to the closest target point.
Note
Builds one ShortestPaths object and stops when the bft is finished.

Referenced by main().

◆ size()

template<typename TKSpace >
Size DGtal::TangencyComputer< TKSpace >::size ( ) const
inline
Returns
the number of points in the digital set.

Definition at line 419 of file TangencyComputer.h.

420  { return myX.size(); }

References DGtal::TangencyComputer< TKSpace >::myX.

Referenced by DGtal::TangencyComputer< TKSpace >::index(), main(), and DGtal::TangencyComputer< TKSpace >::ShortestPaths::size().

◆ space()

template<typename TKSpace >
const KSpace& DGtal::TangencyComputer< TKSpace >::space ( ) const
inline
Returns
a const reference to the Khalimsky space.

Definition at line 415 of file TangencyComputer.h.

416  { return myK; }

References DGtal::TangencyComputer< TKSpace >::myK.

Friends And Related Function Documentation

◆ ShortestPaths

template<typename TKSpace >
friend class ShortestPaths
friend

ShortestPaths may access to datas of TangencyComputer.

Definition at line 366 of file TangencyComputer.h.

Field Documentation

◆ myCellCover

template<typename TKSpace >
CellGeometry< KSpace > DGtal::TangencyComputer< TKSpace >::myCellCover
protected

The cell geometry representing all the cells touching the digital shape.

Definition at line 589 of file TangencyComputer.h.

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

◆ myDConv

template<typename TKSpace >
DigitalConvexity< KSpace > DGtal::TangencyComputer< TKSpace >::myDConv
protected

The digital convexity object used to check full convexity.

Definition at line 580 of file TangencyComputer.h.

◆ myDN

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

The vector of all distances to neighbors (8 in 2D, 26 in 3D, etc), that is the norm of each value of myN.

Definition at line 585 of file TangencyComputer.h.

◆ myK

template<typename TKSpace >
KSpace DGtal::TangencyComputer< TKSpace >::myK
protected

The cellular grid space where computations are done.

Definition at line 578 of file TangencyComputer.h.

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

◆ myN

template<typename TKSpace >
std::vector< Vector > DGtal::TangencyComputer< TKSpace >::myN
protected

The vector of all vectors to neighbors (8 in 2D, 26 in 3D, etc).

Definition at line 582 of file TangencyComputer.h.

◆ myPt2Index

template<typename TKSpace >
std::unordered_map< Point, Index > DGtal::TangencyComputer< TKSpace >::myPt2Index
protected

A map giving for each point its index.

Definition at line 591 of file TangencyComputer.h.

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

◆ myX

template<typename TKSpace >
std::vector< Point > DGtal::TangencyComputer< TKSpace >::myX
protected

The vector of points defining the digital shape under study.

Definition at line 587 of file TangencyComputer.h.

Referenced by DGtal::TangencyComputer< TKSpace >::point(), DGtal::TangencyComputer< TKSpace >::points(), and DGtal::TangencyComputer< TKSpace >::size().


The documentation for this class was generated from the following file:
DGtal::TangencyComputer::myK
KSpace myK
The cellular grid space where computations are done.
Definition: TangencyComputer.h:578
DGtal::TangencyComputer::point
const Point & point(Index i) const
Definition: TangencyComputer.h:428
DGtal::TangencyComputer::myCellCover
CellGeometry< KSpace > myCellCover
The cell geometry representing all the cells touching the digital shape.
Definition: TangencyComputer.h:589
DGtal::TangencyComputer::myPt2Index
std::unordered_map< Point, Index > myPt2Index
A map giving for each point its index.
Definition: TangencyComputer.h:591
DGtal::TangencyComputer::size
Size size() const
Definition: TangencyComputer.h:419
DGtal::TangencyComputer::myX
std::vector< Point > myX
The vector of points defining the digital shape under study.
Definition: TangencyComputer.h:587
Point
MyPointD Point
Definition: testClone2.cpp:383