Aim: A helper class to build polytopes from digital sets and to check digital k-convexity and full convexity.
More...
#include <DGtal/geometry/volumes/DigitalConvexity.h>
|
|
| | ~DigitalConvexity ()=default |
| |
| | DigitalConvexity ()=default |
| |
| | DigitalConvexity (const Self &other)=default |
| |
| | DigitalConvexity (Clone< KSpace > K) |
| |
| | DigitalConvexity (Point lo, Point hi) |
| |
| Self & | operator= (const Self &other)=default |
| |
| const KSpace & | space () const |
| |
|
| 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 |
| |
|
| LatticePolytope | makePolytope (const PointRange &X, bool safe=false) const |
| |
| PointRange | U (Dimension i, const PointRange &X) const |
| |
| bool | is0Convex (const PointRange &X, bool safe=false) const |
| |
| bool | isFullyConvex (const PointRange &X, bool convex0=false, bool safe=false) const |
| |
|
| 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 |
| |
| bool | isKSubconvex (const Point &a, const Point &b, const CellGeometry &C, const Dimension k) const |
| |
| bool | isFullySubconvex (const Point &a, const Point &b, const CellGeometry &C) const |
| |
|
| 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 |
| |
|
| void | selfDisplay (std::ostream &out) const |
| |
| bool | isValid () const |
| |
|
| 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) |
| |
template<typename TKSpace>
class DGtal::DigitalConvexity< TKSpace >
Aim: A helper class to build polytopes from digital sets and to check digital k-convexity and full convexity.
Description of template class 'DigitalConvexity'
- See also
- moduleDigitalConvexity
It is a model of boost::CopyConstructible, boost::DefaultConstructible, boost::Assignable.
- Template Parameters
-
| TKSpace | an arbitrary model of CCellularGridSpaceND. |
Definition at line 75 of file DigitalConvexity.h.
◆ Cell
template<typename TKSpace >
◆ CellGeometry
template<typename TKSpace >
◆ Integer
template<typename TKSpace >
◆ KSpace
template<typename TKSpace >
◆ LatticePolytope
template<typename TKSpace >
◆ Point
template<typename TKSpace >
◆ PointRange
template<typename TKSpace >
◆ PointSet
template<typename TKSpace >
◆ Polytope
template<typename TKSpace >
◆ RationalPolytope
template<typename TKSpace >
◆ Self
template<typename TKSpace >
◆ Space
template<typename TKSpace >
◆ Vector
template<typename TKSpace >
◆ SimplexType
template<typename TKSpace >
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 225 of file DigitalConvexity.h.
◆ ~DigitalConvexity()
template<typename TKSpace >
◆ DigitalConvexity() [1/4]
template<typename TKSpace >
◆ DigitalConvexity() [2/4]
template<typename TKSpace >
Copy constructor.
- Parameters
-
| other | the object to clone. |
◆ DigitalConvexity() [3/4]
template<typename TKSpace >
Constructor from cellular space.
- Parameters
-
| K | any cellular grid space. |
◆ DigitalConvexity() [4/4]
template<typename TKSpace >
Constructor from lower and upper points.
- Parameters
-
| lo | the lowest point of the domain (bounding box for computations). |
| hi | the highest point of the domain (bounding box for computations). |
◆ BOOST_CONCEPT_ASSERT()
template<typename TKSpace >
◆ 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
-
| PointIterator | any model of forward iterator on Point. |
- Parameters
-
| [in,out] | out | the output stream where information is outputed. |
| itB | the start of the range of n+1 points defining the simplex. |
| itE | past the end the range of n+1 points defining the simplex. |
◆ displaySimplex() [2/2]
template<typename TKSpace >
Displays information about simplex formed by the given list l of lattice points.
- Parameters
-
| [in,out] | out | the output stream where information is outputed. |
| l | any list of lattice points. |
◆ insidePoints() [1/2]
template<typename TKSpace >
- Parameters
-
| polytope | any lattice polytope. |
- Returns
- the range of digital points that belongs to the polytope.
◆ insidePoints() [2/2]
template<typename TKSpace >
- Parameters
-
| polytope | any rational polytope. |
- Returns
- the range of digital points that belongs to the polytope.
◆ interiorPoints() [1/2]
template<typename TKSpace >
- Parameters
-
| polytope | any lattice polytope. |
- Returns
- the range of digital points that belongs to the interior of the polytope.
◆ interiorPoints() [2/2]
template<typename TKSpace >
- Parameters
-
| polytope | any rational polytope. |
- Returns
- the range of digital points that belongs to the interior of the polytope.
◆ is0Convex()
template<typename TKSpace >
◆ isFullyConvex() [1/3]
template<typename TKSpace >
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
-
| P | any 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/3]
template<typename TKSpace >
Tells if a given point range X is fully digitally convex. The test uses the morphological characterization of full convexity. It is slightly slower than testing full convexity on simplices, but it works for arbitrary set of points in arbitrary dimenion.
- Parameters
-
| X | any range of pairwise distinct points |
| convex0 | when 'true' indicates that X is known to be digitally 0-convex, otherwise the method will check it also. |
| safe | when 'true' performs computations with arbitrary precision integer (if available), otherwise chooses a compromise between speed and precision (int64_t). |
- Returns
- 'true' iff X is fully digitally convex.
Referenced by DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isComplementaryFullyConvex(), DGtal::NeighborhoodConvexityAnalyzer< TKSpace, K >::isFullyConvex(), and SCENARIO().
◆ isFullyConvex() [3/3]
template<typename TKSpace >
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
-
| P | any 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/3]
template<typename TKSpace >
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
-
| P | any lattice polytope such that P.canBeSummed() == true. |
| C | any 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/3]
template<typename TKSpace >
Tells if a given segment from a to b is digitally fully subconvex (i.e. tangent) 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 the segment is a subset of the k-cells of C.
- Parameters
-
| a | any point |
| b | any point |
| C | any cell cover geometry (i.e. a cubical complex). |
- Returns
- 'true' iff the segment is a digitally fully subconvex of C, i.e. the two points are cotangent.
- Note
- Three times faster than building a (degenerated) lattice polytope and then checking if it subconvex.
◆ isFullySubconvex() [3/3]
template<typename TKSpace >
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
-
| P | any rational polytope such that P.canBeSummed() == true. |
| C | any 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 >
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
-
| P | any lattice polytope such that P.canBeSummed() == true. |
| k | the 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 >
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
-
| P | any rational polytope such that P.canBeSummed() == true. |
| k | the 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/3]
template<typename TKSpace >
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
-
| P | any lattice polytope such that P.canBeSummed() == true. |
| C | any cell cover geometry (i.e. a cubical complex). |
| k | the 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/3]
template<typename TKSpace >
Tells if a given segment from a to b is digitally k-subconvex (i.e. k-tangent) 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 the segment is a subset of the k-cells of C.
- Parameters
-
| a | any point |
| b | any point |
| C | any cell cover geometry (i.e. a cubical complex). |
| k | the dimension for which the digital k-convexity is checked, 0 <= k <= KSpace::dimension. |
- Returns
- 'true' iff the segment is a digitally k-subconvex of C, i.e. the two points are k-cotangent.
- Note
- Three times faster than building a (degenerated) lattice polytope and then checking if it subconvex.
◆ isKSubconvex() [3/3]
template<typename TKSpace >
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
-
| P | any rational polytope such that P.canBeSummed() == true. |
| C | any cell cover geometry (i.e. a cubical complex). |
| k | the 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 >
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
-
| PointIterator | any model of forward iterator on Point. |
- Parameters
-
| itB | the start of the range of n+1 points defining the simplex. |
| itE | past the end the range of n+1 points defining the simplex. |
Referenced by main(), and SCENARIO().
◆ isSimplexFullDimensional() [2/2]
template<typename TKSpace >
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
-
| l | any list of d+1 points in general positions. |
◆ isValid()
template<typename TKSpace >
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 >
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
-
| P | any lattice polytope such that P.canBeSummed() == true. |
| i | the first dimension for which the cell cover is computed. |
| k | the last dimension for which the cell cover is computed. |
◆ makeCellCover() [2/3]
template<typename TKSpace >
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
-
| P | any rational polytope such that P.canBeSummed() == true. |
| i | the first dimension for which the cell cover is computed. |
| k | the last dimension for which the cell cover is computed. |
◆ makeCellCover() [3/3]
template<typename TKSpace >
template<typename PointIterator >
Builds the cell geometry containing all the j-cells touching a point of [itB,itE), for i <= j <= k.
- Template Parameters
-
| PointIterator | any model of input iterator on Points. |
- Parameters
-
| itB | start of a range of arbitrary points. |
| itE | past the end of a range of arbitrary points. |
| i | the first dimension for which the cell cover is computed. |
| k | the last dimension for which the cell cover is computed. |
Referenced by main().
◆ makePolytope()
template<typename TKSpace >
Given a range of distinct points X, computes the tightiest polytope that enclosed it. Note that this polytope may contain more lattice points than the given input points.
- Parameters
-
| X | any range of pairwise distinct points |
| safe | when 'true' performs computations with arbitrary precision integer (if available), otherwise chooses a compromise between speed and precision (int64_t). |
- Returns
- the corresponding lattice polytope.
Referenced by SCENARIO().
◆ makeRationalSimplex() [1/2]
template<typename TKSpace >
template<typename PointIterator >
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
-
| PointIterator | any model of forward iterator on Point. |
- Parameters
-
| d | the common denominator of all given lattice point coordinates. |
| itB | the start of the range of no more than n+1 points defining the simplex. |
| itE | past 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 >
Constructs a rational polytope from a simplex given as an initializer_list.
- Parameters
-
| l | any 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 >
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
-
| PointIterator | any model of forward iterator on Point. |
- Parameters
-
| itB | the start of the range of no more than n+1 points defining the simplex. |
| itE | past the end the range of no more than n+1 points defining the simplex. |
Referenced by main(), and SCENARIO().
◆ makeSimplex() [2/2]
template<typename TKSpace >
Constructs a lattice polytope from a simplex given as an initializer_list.
- Parameters
-
| l | any 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 >
Assignment.
- Parameters
-
- Returns
- a reference on 'this'.
◆ selfDisplay()
template<typename TKSpace >
Writes/Displays the object on an output stream.
- Parameters
-
| out | the output stream where the object is written. |
◆ simplexType() [1/2]
template<typename TKSpace >
template<typename PointIterator >
Returns the type of simplex formed by the given range [itB,itE) of lattice points.
- Template Parameters
-
| PointIterator | any model of forward iterator on Point. |
- Parameters
-
| itB | the start of the range of n+1 points defining the simplex. |
| itE | past 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 >
Returns the type of simplex formed by the given list l of lattice points.
- Parameters
-
| l | any list of lattice points. |
- Returns
- the type of simplex formed by the given list of lattice points.
◆ space()
template<typename TKSpace >
◆ U()
template<typename TKSpace >
Performs the digital Minkowski sum of X along direction i
- Parameters
-
| i | any valid dimension |
| X | any sorted range of digital points |
- Returns
- the sorted range of digital points X union the translation of X of one along direction i.
◆ dimension
template<typename TKSpace >
◆ myK
template<typename TKSpace >
The documentation for this class was generated from the following file:
