DGtal  1.1.0
Public Types | Static Public Attributes | Protected Attributes | Private Member Functions
DGtal::DigitalConvexity< TKSpace > Class Template Reference

Aim: A helper class to build polytopes from digital sets and to check digital k-convexity. More...

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

Public Types

typedef DigitalConvexity< TKSpace > Self
 
typedef TKSpace KSpace
 
typedef KSpace::Integer Integer
 
typedef KSpace::Point Point
 
typedef KSpace::Vector Vector
 
typedef KSpace::Cell Cell
 
typedef KSpace::Space Space
 
typedef DGtal::BoundedLatticePolytope< SpacePolytope
 
typedef DGtal::BoundedLatticePolytope< SpaceLatticePolytope
 
typedef DGtal::BoundedRationalPolytope< SpaceRationalPolytope
 
typedef DGtal::CellGeometry< KSpaceCellGeometry
 
typedef std::vector< PointPointRange
 

Public Member Functions

Standard services (construction, initialization, assignment)
 ~DigitalConvexity ()=default
 
 DigitalConvexity ()=default
 
 DigitalConvexity (const Self &other)=default
 
 DigitalConvexity (Clone< KSpace > K)
 
 DigitalConvexity (Point lo, Point hi)
 
Selfoperator= (const Self &other)=default
 
const KSpacespace () const
 
Cell geometry services
template<typename PointIterator >
CellGeometry makeCellCover (PointIterator itB, PointIterator itE, Dimension i=0, Dimension k=KSpace::dimension) const
 
CellGeometry makeCellCover (const LatticePolytope &P, Dimension i=0, Dimension k=KSpace::dimension) const
 
CellGeometry makeCellCover (const RationalPolytope &P, Dimension i=0, Dimension k=KSpace::dimension) const
 
Convexity services for lattice polytopes
bool isKConvex (const LatticePolytope &P, const Dimension k) const
 
bool isFullyConvex (const LatticePolytope &P) const
 
bool isKSubconvex (const LatticePolytope &P, const CellGeometry &C, const Dimension k) const
 
bool isFullySubconvex (const LatticePolytope &P, const CellGeometry &C) const
 
Convexity services for rational polytopes
bool isKConvex (const RationalPolytope &P, const Dimension k) const
 
bool isFullyConvex (const RationalPolytope &P) const
 
bool isKSubconvex (const RationalPolytope &P, const CellGeometry &C, const Dimension k) const
 
bool isFullySubconvex (const RationalPolytope &P, const CellGeometry &C) const
 
Interface services
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 

Static Public Member Functions

Lattice and rational polytope services
static PointRange insidePoints (const LatticePolytope &polytope)
 
static PointRange interiorPoints (const LatticePolytope &polytope)
 
static PointRange insidePoints (const RationalPolytope &polytope)
 
static PointRange interiorPoints (const RationalPolytope &polytope)
 

Static Public Attributes

static const Dimension dimension = KSpace::dimension
 

Protected Attributes

KSpace myK
 The cellular grid space where computations are done. More...
 

Private Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CCellularGridSpaceND< TKSpace >))
 

Simplex services

enum  SimplexType { SimplexType::INVALID, SimplexType::DEGENERATED, SimplexType::UNITARY, SimplexType::COMMON }
 The possible types for simplices. More...
 
template<typename PointIterator >
static LatticePolytope makeSimplex (PointIterator itB, PointIterator itE)
 
static LatticePolytope makeSimplex (std::initializer_list< Point > l)
 
template<typename PointIterator >
static RationalPolytope makeRationalSimplex (Integer d, PointIterator itB, PointIterator itE)
 
static RationalPolytope makeRationalSimplex (std::initializer_list< Point > l)
 
template<typename PointIterator >
static bool isSimplexFullDimensional (PointIterator itB, PointIterator itE)
 
static bool isSimplexFullDimensional (std::initializer_list< Point > l)
 
template<typename PointIterator >
static SimplexType simplexType (PointIterator itB, PointIterator itE)
 
static SimplexType simplexType (std::initializer_list< Point > l)
 
template<typename PointIterator >
static void displaySimplex (std::ostream &out, PointIterator itB, PointIterator itE)
 
static void displaySimplex (std::ostream &out, std::initializer_list< Point > l)
 

Detailed Description

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

Aim: A helper class to build polytopes from digital sets and to check digital k-convexity.

Description of template class 'DigitalConvexity'

It is a model of boost::CopyConstructible, boost::DefaultConstructible, boost::Assignable.

Template Parameters
TKSpacean arbitrary model of CCellularGridSpaceND.
Examples
geometry/curves/exampleDigitalConvexity.cpp, and geometry/curves/exampleRationalConvexity.cpp.

Definition at line 73 of file DigitalConvexity.h.

Member Typedef Documentation

◆ Cell

template<typename TKSpace >
typedef KSpace::Cell DGtal::DigitalConvexity< TKSpace >::Cell

Definition at line 83 of file DigitalConvexity.h.

◆ CellGeometry

template<typename TKSpace >
typedef DGtal::CellGeometry< KSpace > DGtal::DigitalConvexity< TKSpace >::CellGeometry

Definition at line 88 of file DigitalConvexity.h.

◆ Integer

template<typename TKSpace >
typedef KSpace::Integer DGtal::DigitalConvexity< TKSpace >::Integer

Definition at line 80 of file DigitalConvexity.h.

◆ KSpace

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

Definition at line 79 of file DigitalConvexity.h.

◆ LatticePolytope

template<typename TKSpace >
typedef DGtal::BoundedLatticePolytope< Space > DGtal::DigitalConvexity< TKSpace >::LatticePolytope

Definition at line 86 of file DigitalConvexity.h.

◆ Point

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

Definition at line 81 of file DigitalConvexity.h.

◆ PointRange

template<typename TKSpace >
typedef std::vector<Point> DGtal::DigitalConvexity< TKSpace >::PointRange

Definition at line 89 of file DigitalConvexity.h.

◆ Polytope

template<typename TKSpace >
typedef DGtal::BoundedLatticePolytope< Space > DGtal::DigitalConvexity< TKSpace >::Polytope

Definition at line 85 of file DigitalConvexity.h.

◆ RationalPolytope

template<typename TKSpace >
typedef DGtal::BoundedRationalPolytope< Space > DGtal::DigitalConvexity< TKSpace >::RationalPolytope

Definition at line 87 of file DigitalConvexity.h.

◆ Self

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

Definition at line 78 of file DigitalConvexity.h.

◆ Space

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

Definition at line 84 of file DigitalConvexity.h.

◆ Vector

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

Definition at line 82 of file DigitalConvexity.h.

Member Enumeration Documentation

◆ SimplexType

template<typename TKSpace >
enum DGtal::DigitalConvexity::SimplexType
strong

The possible types for simplices.

Enumerator
INVALID 

When there are not the right number of vertices.

DEGENERATED 

When the points of the simplex are not in general position.

UNITARY 

When its edges form a unit parallelotope (det = +/- 1)

COMMON 

Common simplex.

Definition at line 222 of file DigitalConvexity.h.

222  {
223  INVALID,
224  DEGENERATED,
225  UNITARY,
226  COMMON
227  };

Constructor & Destructor Documentation

◆ ~DigitalConvexity()

template<typename TKSpace >
DGtal::DigitalConvexity< TKSpace >::~DigitalConvexity ( )
default

Destructor.

◆ DigitalConvexity() [1/4]

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

Constructor.

◆ DigitalConvexity() [2/4]

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

Copy constructor.

Parameters
otherthe object to clone.

◆ DigitalConvexity() [3/4]

template<typename TKSpace >
DGtal::DigitalConvexity< TKSpace >::DigitalConvexity ( Clone< KSpace K)

Constructor from cellular space.

Parameters
Kany cellular grid space.

◆ DigitalConvexity() [4/4]

template<typename TKSpace >
DGtal::DigitalConvexity< TKSpace >::DigitalConvexity ( Point  lo,
Point  hi 
)

Constructor from lower and upper points.

Parameters
lothe lowest point of the domain (bounding box for computations).
hithe highest point of the domain (bounding box for computations).

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT()

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

◆ displaySimplex() [1/2]

template<typename TKSpace >
template<typename PointIterator >
static void DGtal::DigitalConvexity< TKSpace >::displaySimplex ( std::ostream &  out,
PointIterator  itB,
PointIterator  itE 
)
static

Displays information about the simplex formed by the given range [itB,itE) of lattice points.

Template Parameters
PointIteratorany model of forward iterator on Point.
Parameters
[in,out]outthe output stream where information is outputed.
itBthe start of the range of n+1 points defining the simplex.
itEpast the end the range of n+1 points defining the simplex.

◆ displaySimplex() [2/2]

template<typename TKSpace >
static void DGtal::DigitalConvexity< TKSpace >::displaySimplex ( std::ostream &  out,
std::initializer_list< Point l 
)
static

Displays information about simplex formed by the given list l of lattice points.

Parameters
[in,out]outthe output stream where information is outputed.
lany list of lattice points.

◆ insidePoints() [1/2]

template<typename TKSpace >
static PointRange DGtal::DigitalConvexity< TKSpace >::insidePoints ( const LatticePolytope polytope)
static
Parameters
polytopeany lattice polytope.
Returns
the range of digital points that belongs to the polytope.

◆ insidePoints() [2/2]

template<typename TKSpace >
static PointRange DGtal::DigitalConvexity< TKSpace >::insidePoints ( const RationalPolytope polytope)
static
Parameters
polytopeany rational polytope.
Returns
the range of digital points that belongs to the polytope.

◆ interiorPoints() [1/2]

template<typename TKSpace >
static PointRange DGtal::DigitalConvexity< TKSpace >::interiorPoints ( const LatticePolytope polytope)
static
Parameters
polytopeany lattice polytope.
Returns
the range of digital points that belongs to the interior of the polytope.

◆ interiorPoints() [2/2]

template<typename TKSpace >
static PointRange DGtal::DigitalConvexity< TKSpace >::interiorPoints ( const RationalPolytope polytope)
static
Parameters
polytopeany rational polytope.
Returns
the range of digital points that belongs to the interior of the polytope.

◆ isFullyConvex() [1/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isFullyConvex ( const LatticePolytope P) const

Tells if a given polytope P is fully digitally convex. The digital 0-convexity is the usual property \( Conv( P \cap Z^d ) = P \cap Z^d) \). Otherwise the property asks that the points inside P touch as many k-cells that the convex hull of P, for any valid dimension k.

Parameters
Pany lattice polytope such that P.canBeSummed() == true.
Returns
'true' iff the polytope P is fully digitally convex.
Note
A polytope is always digitally 0-convex. Furthermore, if it is not digitally d-1-convex then it is digitally d-convex (d := KSpace::dimension). Hence, we only check k-convexity for 1 <= k <= d-1.

◆ isFullyConvex() [2/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isFullyConvex ( const RationalPolytope P) const

Tells if a given polytope P is fully digitally convex. The digital 0-convexity is the usual property \( Conv( P \cap Z^d ) = P \cap Z^d) \). Otherwise the property asks that the points inside P touch as many k-cells that the convex hull of P, for any valid dimension k.

Parameters
Pany rational polytope such that P.canBeSummed() == true.
Returns
'true' iff the polytope P is fully digitally convex.
Note
A polytope is always digitally 0-convex. Furthermore, if it is not digitally d-1-convex then it is digitally d-convex (d := KSpace::dimension). Hence, we only check k-convexity for 1 <= k <= d-1.

◆ isFullySubconvex() [1/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isFullySubconvex ( const LatticePolytope P,
const CellGeometry C 
) const

Tells if a given polytope P is digitally fully subconvex to some cell cover C. The digital 0-subconvexity is the usual property \( Conv( P \cap Z^d ) \subset C \cap Z^d) \). Otherwise the property asks that the k-cells intersected by the convex hull of P is a subset of the k-cells of C.

Parameters
Pany lattice polytope such that P.canBeSummed() == true.
Cany cell cover geometry (i.e. a cubical complex).
Returns
'true' iff the polytope P is digitally fully subconvex to C.
Note
This method only checks the k-subconvexity for valid dimensions stored in C.

Referenced by main().

◆ isFullySubconvex() [2/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isFullySubconvex ( const RationalPolytope P,
const CellGeometry C 
) const

Tells if a given polytope P is digitally fully subconvex to some cell cover C. The digital 0-subconvexity is the usual property \( Conv( P \cap Z^d ) \subset C \cap Z^d) \). Otherwise the property asks that the k-cells intersected by the convex hull of P is a subset of the k-cells of C.

Parameters
Pany rational polytope such that P.canBeSummed() == true.
Cany cell cover geometry (i.e. a cubical complex).
Returns
'true' iff the polytope P is digitally fully subconvex to C.
Note
This method only checks the k-subconvexity for valid dimensions stored in C.

◆ isKConvex() [1/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isKConvex ( const LatticePolytope P,
const Dimension  k 
) const

Tells if a given polytope P is digitally k-convex. The digital 0-convexity is the usual property \( Conv( P \cap Z^d ) = P \cap Z^d) \). Otherwise the property asks that the points inside P touch as many k-cells that the convex hull of P.

Parameters
Pany lattice polytope such that P.canBeSummed() == true.
kthe dimension for which the digital k-convexity is checked, 0 <= k <= KSpace::dimension.
Returns
'true' iff the polytope P is digitally k-convex.
Note
A polytope is always digitally 0-convex. Furthermore, if it is not digitally d-1-convex then it is digitally not d-convex (d := KSpace::dimension).

◆ isKConvex() [2/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isKConvex ( const RationalPolytope P,
const Dimension  k 
) const

Tells if a given polytope P is digitally k-convex. The digital 0-convexity is the usual property \( Conv( P \cap Z^d ) = P \cap Z^d) \). Otherwise the property asks that the points inside P touch as many k-cells that the convex hull of P.

Parameters
Pany rational polytope such that P.canBeSummed() == true.
kthe dimension for which the digital k-convexity is checked, 0 <= k <= KSpace::dimension.
Returns
'true' iff the polytope P is digitally k-convex.
Note
A polytope is always digitally 0-convex. Furthermore, if it is not digitally d-1-convex then it is digitally not d-convex (d := KSpace::dimension).

◆ isKSubconvex() [1/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isKSubconvex ( const LatticePolytope P,
const CellGeometry C,
const Dimension  k 
) const

Tells if a given polytope P is digitally k-subconvex of some cell cover C. The digital 0-subconvexity is the usual property \( Conv( P \cap Z^d ) \subset C \cap Z^d) \). Otherwise the property asks that the k-cells intersected by the convex hull of P is a subset of the k-cells of C.

Parameters
Pany lattice polytope such that P.canBeSummed() == true.
Cany cell cover geometry (i.e. a cubical complex).
kthe dimension for which the digital k-convexity is checked, 0 <= k <= KSpace::dimension.
Returns
'true' iff the polytope P is a digitally k-subconvex of C.

◆ isKSubconvex() [2/2]

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isKSubconvex ( const RationalPolytope P,
const CellGeometry C,
const Dimension  k 
) const

Tells if a given polytope P is digitally k-subconvex of some cell cover C. The digital 0-subconvexity is the usual property \( Conv( P \cap Z^d ) \subset C \cap Z^d) \). Otherwise the property asks that the k-cells intersected by the convex hull of P is a subset of the k-cells of C.

Parameters
Pany rational polytope such that P.canBeSummed() == true.
Cany cell cover geometry (i.e. a cubical complex).
kthe dimension for which the digital k-convexity is checked, 0 <= k <= KSpace::dimension.
Returns
'true' iff the polytope P is a digitally k-subconvex of C.

◆ isSimplexFullDimensional() [1/2]

template<typename TKSpace >
template<typename PointIterator >
static bool DGtal::DigitalConvexity< TKSpace >::isSimplexFullDimensional ( PointIterator  itB,
PointIterator  itE 
)
static

Checks if the given range [itB,itE) of lattice points form a full dimensional simplex, i.e. it must contain Space::dimension+1 points in general position.

Template Parameters
PointIteratorany model of forward iterator on Point.
Parameters
itBthe start of the range of n+1 points defining the simplex.
itEpast the end the range of n+1 points defining the simplex.

Referenced by main().

◆ isSimplexFullDimensional() [2/2]

template<typename TKSpace >
static bool DGtal::DigitalConvexity< TKSpace >::isSimplexFullDimensional ( std::initializer_list< Point l)
static

Checks if the given list of lattice points l form a full dimensional simplex, i.e. it must contain Space::dimension+1 points in general position.

Parameters
lany list of d+1 points in general positions.

◆ isValid()

template<typename TKSpace >
bool DGtal::DigitalConvexity< TKSpace >::isValid ( ) const

Checks the validity/consistency of the object. If the polytope has been default constructed, it is invalid.

Returns
'true' if the object is valid, 'false' otherwise.

◆ makeCellCover() [1/3]

template<typename TKSpace >
CellGeometry DGtal::DigitalConvexity< TKSpace >::makeCellCover ( const LatticePolytope P,
Dimension  i = 0,
Dimension  k = KSpace::dimension 
) const

Builds the cell geometry containing all the j-cells touching the lattice polytope P, for i <= j <= k. It conbains thus all the j-cells intersecting the convex enveloppe of P.

Parameters
Pany lattice polytope such that P.canBeSummed() == true.
ithe first dimension for which the cell cover is computed.
kthe last dimension for which the cell cover is computed.

◆ makeCellCover() [2/3]

template<typename TKSpace >
CellGeometry DGtal::DigitalConvexity< TKSpace >::makeCellCover ( const RationalPolytope P,
Dimension  i = 0,
Dimension  k = KSpace::dimension 
) const

Builds the cell geometry containing all the j-cells touching the rational polytope P, for i <= j <= k. It conbains thus all the j-cells intersecting the convex enveloppe of P.

Parameters
Pany rational polytope such that P.canBeSummed() == true.
ithe first dimension for which the cell cover is computed.
kthe last dimension for which the cell cover is computed.

◆ makeCellCover() [3/3]

template<typename TKSpace >
template<typename PointIterator >
CellGeometry DGtal::DigitalConvexity< TKSpace >::makeCellCover ( PointIterator  itB,
PointIterator  itE,
Dimension  i = 0,
Dimension  k = KSpace::dimension 
) const

Builds the cell geometry containing all the j-cells touching a point of [itB,itE), for i <= j <= k.

Template Parameters
PointIteratorany model of input iterator on Points.
Parameters
itBstart of a range of arbitrary points.
itEpast the end of a range of arbitrary points.
ithe first dimension for which the cell cover is computed.
kthe last dimension for which the cell cover is computed.

Referenced by main().

◆ makeRationalSimplex() [1/2]

template<typename TKSpace >
template<typename PointIterator >
static RationalPolytope DGtal::DigitalConvexity< TKSpace >::makeRationalSimplex ( Integer  d,
PointIterator  itB,
PointIterator  itE 
)
static

Constructs a rational polytope from a rational simplex given as a range [itB,itE) of lattice points. Note that the range must contain Space::dimension+1 points or less in general position.

Template Parameters
PointIteratorany model of forward iterator on Point.
Parameters
dthe common denominator of all given lattice point coordinates.
itBthe start of the range of no more than n+1 points defining the simplex.
itEpast the end the range of no more than n+1 points defining the simplex.
Note
If your range is [itB,itE) = { (3,2), (1,7), (6,6) } and the denominator d = 4, then your polytope has vertices { (3/4,2/4), (1/4,7/4), (6/4,6/4) }.

◆ makeRationalSimplex() [2/2]

template<typename TKSpace >
static RationalPolytope DGtal::DigitalConvexity< TKSpace >::makeRationalSimplex ( std::initializer_list< Point l)
static

Constructs a rational polytope from a simplex given as an initializer_list.

Parameters
lany list where the first point give the denominator and then no more than d+1 points in general positions.
Note
If your list is l = { (4,x), (3,2), (1,7), (6,6) }, then the denominator is d = 4 and your polytope has vertices { (3/4,2/4), (1/4,7/4), (6/4,6/4) }.

◆ makeSimplex() [1/2]

template<typename TKSpace >
template<typename PointIterator >
static LatticePolytope DGtal::DigitalConvexity< TKSpace >::makeSimplex ( PointIterator  itB,
PointIterator  itE 
)
static

Constructs a lattice polytope from a simplex given as a range [itB,itE) of lattice points. Note that the range must contain Space::dimension+1 points or less in general position.

Template Parameters
PointIteratorany model of forward iterator on Point.
Parameters
itBthe start of the range of no more than n+1 points defining the simplex.
itEpast the end the range of no more than n+1 points defining the simplex.

Referenced by main().

◆ makeSimplex() [2/2]

template<typename TKSpace >
static LatticePolytope DGtal::DigitalConvexity< TKSpace >::makeSimplex ( std::initializer_list< Point l)
static

Constructs a lattice polytope from a simplex given as an initializer_list.

Parameters
lany list of no more than d+1 points in general positions.
Precondition
Note that the list must contain no more than Space::dimension+1 points in general position.

◆ operator=()

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

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'.

◆ selfDisplay()

template<typename TKSpace >
void DGtal::DigitalConvexity< TKSpace >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

◆ simplexType() [1/2]

template<typename TKSpace >
template<typename PointIterator >
static SimplexType DGtal::DigitalConvexity< TKSpace >::simplexType ( PointIterator  itB,
PointIterator  itE 
)
static

Returns the type of simplex formed by the given range [itB,itE) of lattice points.

Template Parameters
PointIteratorany model of forward iterator on Point.
Parameters
itBthe start of the range of n+1 points defining the simplex.
itEpast the end the range of n+1 points defining the simplex.
Returns
the type of simplex formed by the given range [itB,itE) of lattice points.

◆ simplexType() [2/2]

template<typename TKSpace >
static SimplexType DGtal::DigitalConvexity< TKSpace >::simplexType ( std::initializer_list< Point l)
static

Returns the type of simplex formed by the given list l of lattice points.

Parameters
lany list of lattice points.
Returns
the type of simplex formed by the given list of lattice points.

◆ space()

template<typename TKSpace >
const KSpace& DGtal::DigitalConvexity< TKSpace >::space ( ) const
Returns
a const reference to the cellular grid space used by this object.

Field Documentation

◆ dimension

template<typename TKSpace >
const Dimension DGtal::DigitalConvexity< TKSpace >::dimension = KSpace::dimension
static

Definition at line 91 of file DigitalConvexity.h.

◆ myK

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

The cellular grid space where computations are done.

Definition at line 496 of file DigitalConvexity.h.


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