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< Space >	Domain

typedef std::size_t	Index

typedef std::size_t	Size

typedef std::vector< Index >	Path

typedef CellGeometry< KSpace >	CellCover

typedef LatticeSetByIntervals< Space >	LatticeCellCover

Public Member Functions
Standard services (construction, initialization, assignment)
	TangencyComputer ()=default
	Constructor. The object is invalid.

	TangencyComputer (const Self &other)=default

	TangencyComputer (Self &&other)=default

Self &	operator= (const Self &other)=default

Self &	operator= (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 KSpace &	space () const

Size	size () const

const std::vector< Point > &	points () const

const Point &	point (Index i) const

Size	index (const Point &a) const

const CellCover &	cellCover () const

const LatticeCellCover &	latticeCellCover () 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< Index >	getCotangentPoints (const Point &a) const

std::vector< Index >	getCotangentPoints (const Point &a, const std::vector< bool > &to_avoid) const

Shortest paths services
ShortestPaths	makeShortestPaths (double secure=sqrt(KSpace::dimension)) const

std::vector< Path >	shortestPaths (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.

DigitalConvexity< KSpace >	myDConv
	The digital convexity object used to check full convexity.

std::vector< Vector >	myN
	The vector of all vectors to neighbors (8 in 2D, 26 in 3D, etc).

std::vector< double >	myDN

std::vector< Point >	myX
	The vector of points defining the digital shape under study.

bool	myUseLatticeCellCover
	Tells if one must use CellCover or LatticeCellCover for computations.

CellCover	myCellCover

LatticeCellCover	myLatticeCellCover

std::unordered_map< Point, Index >	myPt2Index
	A map giving for each point its index.

Private Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::CCellularGridSpaceND< TKSpace >))

void	setUp ()
	Precomputes some neighborhood tables at construction.

Friends
struct	ShortestPaths
	ShortestPaths may access to datas of TangencyComputer.

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

TKSpace an arbitrary model of CCellularGridSpaceND.

Examples: geometry/volumes/fullConvexityShortestPaths3D.cpp, and geometry/volumes/fullConvexitySphereGeodesics.cpp.

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

other the object to clone.

◆ TangencyComputer() [3/4]

template<typename TKSpace >

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

default

Move constructor.

Parameters

other the object to move

◆ TangencyComputer() [4/4]

template<typename TKSpace >

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

Constructor from digital space.

Parameters

aK	the 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]	a	any point
[in]	b	any 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]	a	any point
[in]	b	any point
[in]	c	any 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; }

DGtal::TangencyComputer::myCellCover

CellCover myCellCover

Definition TangencyComputer.h:613

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] a any 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]	a	any point
[in]	to_avoid	if '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

a any 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.

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

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

PointIterator any model of ForwardIterator on Point.

Parameters

[in]	itB	an iterator pointing at the beginning of the range.
[in]	itE	an iterator pointing after the end of the range.
[in]	use_lattice_cell_cover	if '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; }

DGtal::TangencyComputer::myLatticeCellCover

LatticeCellCover myLatticeCellCover

Definition TangencyComputer.h:616

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

◆ length()

template<typename TKSpace >

double DGtal::TangencyComputer< TKSpace >::length ( const Path & path ) const

inline

Parameters

[in] path a sequence of point indices describing a valid path.

Returns: its Euclidean length.

Definition at line 460 of file TangencyComputer.h.

    {
      auto eucl_d = [] ( const Point& p, const Point& q )
      { return ( p - q ).norm(); };
      double l = 0.0;
      for ( auto i = 1; i < path.size(); i++ )
        l += eucl_d( point( path[ i-1 ] ), point( path[ i ] ) );
      return l;
    }

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

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.

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

other the 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

other the object to clone

Returns: a reference to 'this'

◆ point()

template<typename TKSpace >

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

inline

Parameters

i	any 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 ]; }

DGtal::TangencyComputer::myX

std::vector< Point > myX

The vector of points defining the digital shape under study.

Definition TangencyComputer.h:608

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]	source	the index of the source point.
[in]	target	the index of the target point.
	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.
[in]	verbose	when '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]	sources	the indices of the `n` source points.
[in]	targets	the indices of the possible target points.
	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.
[in]	verbose	when '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; }

DGtal::TangencyComputer::myK

KSpace myK

The cellular grid space where computations are done.

Definition TangencyComputer.h:599

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

Friends And Related Symbol Documentation

◆ ShortestPaths

template<typename TKSpace >

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

TangencyComputer.h

Data Structures

Public Types

Public Member Functions

Protected Attributes

Private Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ CellCover

◆ Domain

◆ Index

◆ KSpace

◆ LatticeCellCover

◆ Path

◆ Point

◆ Self

◆ Size

◆ Space

◆ Vector

Constructor & Destructor Documentation

◆ TangencyComputer() [1/4]

◆ TangencyComputer() [2/4]

◆ TangencyComputer() [3/4]

◆ TangencyComputer() [4/4]

Member Function Documentation

◆ arePointsCotangent() [1/2]

◆ arePointsCotangent() [2/2]

◆ BOOST_CONCEPT_ASSERT()

◆ cellCover()

◆ getCotangentPoints() [1/2]

◆ getCotangentPoints() [2/2]

◆ index()

◆ init()

◆ latticeCellCover()

◆ length()

◆ makeShortestPaths()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ point()

◆ points()

◆ setUp()

◆ shortestPath()

◆ shortestPaths()

◆ size()

◆ space()

Friends And Related Symbol Documentation

◆ ShortestPaths

Field Documentation

◆ myCellCover

◆ myDConv

◆ myDN

◆ myK

◆ myLatticeCellCover

◆ myN

◆ myPt2Index

◆ myUseLatticeCellCover

◆ myX