DGtal  1.4.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
 
typedef CellGeometry< KSpaceCellCover
 
typedef LatticeSetByIntervals< SpaceLatticeCellCover
 

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, bool use_lattice_cell_cover=false)
 
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 CellCovercellCover () const
 
const LatticeCellCoverlatticeCellCover () const
 
double length (const Path &path) const
 
Tangency services
bool arePointsCotangent (const Point &a, const Point &b) const
 
bool arePointsCotangent (const Point &a, const Point &b, const Point &c) 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...
 
bool myUseLatticeCellCover
 Tells if one must use CellCover or LatticeCellCover for computations. More...
 
CellCover myCellCover
 
LatticeCellCover myLatticeCellCover
 
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.

Definition at line 73 of file TangencyComputer.h.

Member Typedef Documentation

◆ CellCover

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

Definition at line 87 of file TangencyComputer.h.

◆ Domain

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

Definition at line 83 of file TangencyComputer.h.

◆ Index

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

Definition at line 84 of file TangencyComputer.h.

◆ KSpace

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

Definition at line 79 of file TangencyComputer.h.

◆ LatticeCellCover

template<typename TKSpace >
typedef LatticeSetByIntervals< Space > DGtal::TangencyComputer< TKSpace >::LatticeCellCover

Definition at line 88 of file TangencyComputer.h.

◆ Path

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

Definition at line 86 of file TangencyComputer.h.

◆ Point

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

Definition at line 81 of file TangencyComputer.h.

◆ Self

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

Definition at line 78 of file TangencyComputer.h.

◆ Size

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

Definition at line 85 of file TangencyComputer.h.

◆ Space

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

Definition at line 80 of file TangencyComputer.h.

◆ Vector

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

Definition at line 82 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() [1/2]

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

Tells if 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.

◆ arePointsCotangent() [2/2]

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

Tells if three points are cotangent with respect to the current digital set.

Parameters
[in]aany point
[in]bany point
[in]cany 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 CellCover& DGtal::TangencyComputer< TKSpace >::cellCover ( ) const
inline
Returns
a const reference to the cell geometry of the current digital set.

Definition at line 450 of file TangencyComputer.h.

451  { 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 443 of file TangencyComputer.h.

444  {
445  const auto p = myPt2Index.find( a );
446  return p == myPt2Index.cend() ? size() : p->second;
447  }
std::unordered_map< Point, Index > myPt2Index
A map giving for each point its index.

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,
bool  use_lattice_cell_cover = false 
)

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.
[in]use_lattice_cell_coverif 'true' uses LatticeSetByIntervals to represent the cell geometry instead of CellGeometry. Generally a little bit slower for digital surfaces, but may be faster for volumetric objects.

◆ latticeCellCover()

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

Definition at line 455 of file TangencyComputer.h.

456  { return myLatticeCellCover; }
LatticeCellCover myLatticeCellCover

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

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

461  {
462  auto eucl_d = [] ( const Point& p, const Point& q )
463  { return ( p - q ).norm(); };
464  double l = 0.0;
465  for ( auto i = 1; i < path.size(); i++ )
466  l += eucl_d( point( path[ i-1 ] ), point( path[ i ] ) );
467  return l;
468  }
const Point & point(Index i) const
MyPointD Point
Definition: testClone2.cpp:383

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

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

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

438  { return myX[ i ]; }
std::vector< Point > myX
The vector of points defining the digital shape under study.

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

Referenced by DGtal::TangencyComputer< TKSpace >::length(), 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 432 of file TangencyComputer.h.

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

◆ size()

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

Definition at line 428 of file TangencyComputer.h.

429  { return myX.size(); }

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

Referenced by DGtal::TangencyComputer< TKSpace >::index(), 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 424 of file TangencyComputer.h.

425  { return myK; }
KSpace myK
The cellular grid space where computations are done.

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

Field Documentation

◆ myCellCover

template<typename TKSpace >
CellCover DGtal::TangencyComputer< TKSpace >::myCellCover
protected

The cell geometry representing all the cells touching the digital shape (uses UnorderedSetByBlock behind)

Definition at line 613 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 601 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 606 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 599 of file TangencyComputer.h.

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

◆ myLatticeCellCover

template<typename TKSpace >
LatticeCellCover DGtal::TangencyComputer< TKSpace >::myLatticeCellCover
protected

The lattice cell geometry representing all the cells touching the digital shape (uses LatticeSetByIntervals behind).

Definition at line 616 of file TangencyComputer.h.

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

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

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

◆ myUseLatticeCellCover

template<typename TKSpace >
bool DGtal::TangencyComputer< TKSpace >::myUseLatticeCellCover
protected

Tells if one must use CellCover or LatticeCellCover for computations.

Definition at line 610 of file TangencyComputer.h.

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