Aim: Represents an nD rational polytope, i.e. a convex polyhedron bounded by vertices with rational coordinates, as a set of inequalities. Otherwise said, it is a H-representation of a polytope (as an intersection of half-spaces). A limitation is that we model only bounded polytopes, i.e. polytopes that can be included in a finite bounding box.
More...
#include <DGtal/geometry/volumes/BoundedRationalPolytope.h>
|
|
| | ~BoundedRationalPolytope ()=default |
| |
| | BoundedRationalPolytope () |
| |
| | BoundedRationalPolytope (const Self &other)=default |
| |
| | BoundedRationalPolytope (std::initializer_list< Point > l) |
| |
| template<typename PointIterator > |
| | BoundedRationalPolytope (Integer d, PointIterator itB, PointIterator itE) |
| |
| template<typename HalfSpaceIterator > |
| | BoundedRationalPolytope (Integer d, const Domain &domain, HalfSpaceIterator itB, HalfSpaceIterator itE, bool valid_edge_constraints=false, bool check_duplicate_constraints=false) |
| |
| template<typename HalfSpaceIterator > |
| void | init (Integer d, const Domain &domain, HalfSpaceIterator itB, HalfSpaceIterator itE, bool valid_edge_constraints=false, bool check_duplicate_constraints=false) |
| |
| template<typename PointIterator > |
| bool | init (Integer d, PointIterator itB, PointIterator itE) |
| |
| Self & | operator= (const Self &other)=default |
| |
| void | clear () |
| | Clears the polytope. More...
|
| |
|
| const Domain & | getDomain () const |
| |
| const Domain & | getLatticeDomain () const |
| |
| const Domain & | getRationalDomain () const |
| |
| unsigned int | nbHalfSpaces () const |
| |
| Integer | denominator () const |
| |
| const Vector & | getA (unsigned int i) const |
| |
| Integer | getB (unsigned int i) const |
| |
| bool | isLarge (unsigned int i) const |
| |
| const InequalityMatrix & | getA () const |
| |
| const InequalityVector & | getB () const |
| |
| const std::vector< bool > & | getI () const |
| |
| bool | canBeSummed () const |
| |
|
| bool | isInside (const Point &p) const |
| |
| bool | isDomainPointInside (const Point &p) const |
| |
| bool | isInterior (const Point &p) const |
| |
| bool | isBoundary (const Point &p) const |
| |
|
| BoundedRationalPolytope | interiorPolytope () const |
| |
| unsigned int | cut (Dimension k, bool pos, Integer b, bool large=true) |
| |
| unsigned int | cut (const Vector &a, Integer b, bool large=true, bool valid_edge_constraint=false) |
| |
| unsigned int | cut (const HalfSpace &hs, bool large=true, bool valid_edge_constraint=false) |
| |
| void | swap (BoundedRationalPolytope &other) |
| |
| Self & | operator*= (Integer t) |
| |
| Self & | operator*= (Rational r) |
| |
| Self & | operator+= (UnitSegment s) |
| |
| Self & | operator+= (UnitCell c) |
| |
|
| Integer | count () const |
| |
| Integer | countInterior () const |
| |
| Integer | countBoundary () const |
| |
| Integer | countWithin (Point low, Point hi) const |
| |
| Integer | countUpTo (Integer max) const |
| |
| void | getPoints (std::vector< Point > &pts) const |
| |
| void | getInteriorPoints (std::vector< Point > &pts) const |
| |
| void | getBoundaryPoints (std::vector< Point > &pts) const |
| |
| template<typename PointSet > |
| void | insertPoints (PointSet &pts_set) const |
| |
|
| void | selfDisplay (std::ostream &out) const |
| |
| bool | isValid () const |
| |
| std::string | className () const |
| |
template<typename TSpace>
class DGtal::BoundedRationalPolytope< TSpace >
Aim: Represents an nD rational polytope, i.e. a convex polyhedron bounded by vertices with rational coordinates, as a set of inequalities. Otherwise said, it is a H-representation of a polytope (as an intersection of half-spaces). A limitation is that we model only bounded polytopes, i.e. polytopes that can be included in a finite bounding box.
Description of template class 'BoundedRationalPolytope'
It is a model of boost::CopyConstructible, boost::DefaultConstructible, boost::Assignable.
- Template Parameters
-
| TSpace | an arbitrary model of CSpace. |
Definition at line 74 of file BoundedRationalPolytope.h.
◆ BigInteger
template<typename TSpace >
◆ Domain
template<typename TSpace >
◆ HalfSpace
template<typename TSpace >
◆ InequalityMatrix
template<typename TSpace >
◆ InequalityVector
template<typename TSpace >
◆ Integer
template<typename TSpace >
◆ Point
template<typename TSpace >
◆ Self
template<typename TSpace >
◆ Space
template<typename TSpace >
◆ Vector
template<typename TSpace >
◆ ~BoundedRationalPolytope()
template<typename TSpace >
◆ BoundedRationalPolytope() [1/5]
template<typename TSpace >
◆ BoundedRationalPolytope() [2/5]
template<typename TSpace >
Copy constructor.
- Parameters
-
| other | the object to clone. |
◆ BoundedRationalPolytope() [3/5]
template<typename TSpace >
Constructs the 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) }.
◆ BoundedRationalPolytope() [4/5]
template<typename TSpace >
template<typename PointIterator >
Constructs the polytope from a simplex given as a range [itB,itE) of lattice points.
- 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) }.
◆ BoundedRationalPolytope() [5/5]
template<typename TSpace >
template<typename HalfSpaceIterator >
| DGtal::BoundedRationalPolytope< TSpace >::BoundedRationalPolytope |
( |
Integer |
d, |
|
|
const Domain & |
domain, |
|
|
HalfSpaceIterator |
itB, |
|
|
HalfSpaceIterator |
itE, |
|
|
bool |
valid_edge_constraints = false, |
|
|
bool |
check_duplicate_constraints = false |
|
) |
| |
Constructs a polytope from a domain and a collection of half-spaces.
- Template Parameters
-
| HalfSpaceIterator | any model of forward iterator on HalfSpace. |
- Parameters
-
| d | the common denominator of all given lattice point coordinates. |
| domain | a bounded lattice domain. |
| itB | the start of the range of half-spaces. |
| itE | past the end of the range of half-spaces. |
| valid_edge_constraints | when 'true', tells that there are half-spaces that represents th constraints on edges (n-2 cells) lying between two faces (n-1 cells) pointing to different orthants. |
| check_duplicate_constraints | when 'true', the initialization checks if the given range of half-spaces contains axis-aligned half-space constraints already defined by the domain and if so it merges the duplicated constraints, otherwise it accepts and stores the constraints as is. |
- Note
- Asumme your real domain is
{ (-2.25,-1), (3.75, 4.25) } and real halfspaces are ‘{ (1.5*x+2.5*y <= 3), (0.5*x-1.25*y <= 2.5) }. Then for denominator 'd = 4’, you must pass domain={ (-9,-4), (15,17) }, and [itB,itE) = { (6*x+10*y <= 12), (2*x-5*y <= 10) }.
◆ BOOST_CONCEPT_ASSERT()
template<typename TSpace >
◆ canBeSummed()
template<typename TSpace >
- Returns
- 'true' if we can perform exact Minkowksi sums on this polytope. This is related to the presence of valid edge constraints (n-k cells for k >= 2) in-between face constraints (n-1 cells) that change orthants.
◆ className()
template<typename TSpace >
- Returns
- the class name. It is notably used for drawing this object.
◆ clear()
template<typename TSpace >
◆ computeLatticeDomain()
template<typename TSpace >
Computes the lattice domain from the given rational domain, i.e. d/q
- Parameters
-
| d | a domain where integer coordinates (x,y,z) means rational coordinates (x/q,y/q,z/q) where q is the denominator of the rational polytope. |
◆ computeRationalDomain()
template<typename TSpace >
Computes the rational domain from the given lattice domain, i.e. d*q
- Parameters
-
| d | a domain where integer coordinates (x,y,z) means lattice coordinates. |
◆ count()
template<typename TSpace >
Computes the number of integer points lying within the polytope.
- Returns
- the number of integer points lying within the polytope.
- Note
- Quite slow: obtained by checking every point of the polytope domain.
◆ countBoundary()
template<typename TSpace >
Computes the number of integer points lying on the boundary of the polytope.
- Returns
- the number of integer points lying on the boundary of the polytope.
- Note
- Quite slow: obtained by checking every point of the polytope domain.
-
count() <= countInterior() + countBoundary() with equality when the polytope is closed.
◆ countInterior()
template<typename TSpace >
Computes the number of integer points lying within the interior of the polytope.
- Returns
- the number of integer points lying within the interior of the polytope.
- Note
- Quite slow: obtained by checking every point of the polytope domain.
-
count() <= countInterior() + countBoundary() with equality when the polytope is closed.
◆ countUpTo()
template<typename TSpace >
Computes the number of integer points within the polytope up to some maximum number max.
- Note
- For instance, a d-dimensional simplex that contains no integer points in its interior contains only d+1 points. If there is more, you know that the simplex has a non empty interior.
- Parameters
-
| [in] | max | the maximum number of points that are counted, the method exists when this number of reached. |
- Returns
- the number of integer points within the polytope up to .
- Note
- Quite slow: obtained by checking every point of the polytope domain.
◆ countWithin()
template<typename TSpace >
Computes the number of integer points within the polytope and the domain bounded by low and hi.
- Parameters
-
| [in] | low | the lowest lattice point of the domain. |
| [in] | hi | the highest lattice point of the domain. |
- Returns
- the number of integer points within the polytope.
- Note
- Quite slow: obtained by checking every point of the polytope domain.
◆ cut() [1/3]
template<typename TSpace >
Cuts the lattice polytope with the given half-space constraint.
- Parameters
-
| hs | any half-space constraint. |
| large | tells if the inequality is large (true) or strict (false). |
| valid_edge_constraint | when 'true', tells that the half-spaces that represents constraints on edges (n-2 cells) lying between two faces (n-1 cells) pointing to different orthants are still valid after this operation. |
- Returns
- the index of the constraint in the polytope.
- Note
- For now complexity is O(n) where n=A.rows() because it checks if a parallel closed half-space defines already a face of the polytope.
◆ cut() [2/3]
template<typename TSpace >
Cut the polytope by the given half space a.x <= b or a.x < b.
- Parameters
-
| a | any integer vector |
| b | any integer number |
| large | tells if the inequality is large (true) or strict (false). |
| valid_edge_constraint | when 'true', tells that the half-spaces that represents constraints on edges (n-2 cells) lying between two faces (n-1 cells) pointing to different orthants are still valid after this operation. |
- Returns
- the index of the constraint in the polytope.
- Note
- For now complexity is O(n) where n=A.rows() because it checks if a parallel closed half-space defines already a face of the polytope.
◆ cut() [3/3]
template<typename TSpace >
Cut the polytope by the given half space a.x <= b or a.x < b where a is some axis vector.
- Parameters
-
| k | the dimension of the axis vector \( +/- e_k \) |
| pos | 'true' is positive, 'false' is negative for the axis vector \( +/- e_k \) |
| b | any integer number |
| large | tells if the inequality is large (true) or strict (false). |
- Returns
- the index of the constraint in the polytope.
Referenced by DGtal::detail::BoundedRationalPolytopeSpecializer< 3, TInteger >::addEdgeConstraint().
◆ denominator()
template<typename TSpace >
- Returns
- the denominator of the polytope, i.e. vertices lattice coordinates must be divided by this value, or otherwise said, constraints are multiplied by this factor.
◆ getA() [1/2]
template<typename TSpace >
- Returns
- the matrix A in the polytope representation \( Ax \le B \).
◆ getA() [2/2]
template<typename TSpace >
- Parameters
-
| i | the index of the half-space constraint between 0 and nbHalfSpaces() (excluded). |
- Returns
- the normal vector of the i-th half space constraint (i.e.
A in constraint Ax <= b).
◆ getB() [1/2]
template<typename TSpace >
- Returns
- the vector B in the polytope representation \( Ax \le B \).
◆ getB() [2/2]
template<typename TSpace >
- Parameters
-
| i | the index of the half-space constraint between 0 and nbHalfSpaces() (excluded). |
- Returns
- the offset of the i-th half space constraint (i.e.
b in constraint Ax <= b).
◆ getBoundaryPoints()
template<typename TSpace >
Computes the integer points boundary to the polytope.
- Parameters
-
| [out] | pts | the integer points boundary to the polytope. |
- Note
- Quite slow: obtained by checking every point of the polytope domain.
-
At output, pts.size() == this->countBoundary()
◆ getDomain()
template<typename TSpace >
- Returns
- the lattice domain of the current polytope.
◆ getI()
template<typename TSpace >
- Returns
- the vector I telling if inequalities are large in the polytope representation \( Ax \prec B \), with \( \prec \in
\{ <, \le \} \).
◆ getInteriorPoints()
template<typename TSpace >
Computes the integer points interior to the polytope.
- Parameters
-
| [out] | pts | the integer points interior to the polytope. |
- Note
- Quite slow: obtained by checking every point of the polytope domain.
-
At output, pts.size() == this->countInterior()
◆ getLatticeDomain()
template<typename TSpace >
- Returns
- the lattice domain of the current polytope.
- Note
- same as getDomain
◆ getPoints()
template<typename TSpace >
Computes the integer points within the polytope.
- Parameters
-
| [out] | pts | the integer points within the polytope. |
- Note
- Quite slow: obtained by checking every point of the polytope domain.
-
At output, pts.size() == this->count()
◆ getRationalDomain()
template<typename TSpace >
- Returns
- the rational domain of the current polytope.
- Note
- when divided by the polytope denominator, it is the lattice domain.
◆ init() [1/2]
template<typename TSpace >
template<typename HalfSpaceIterator >
Initializes a polytope from a domain and a vector of half-spaces.
- Template Parameters
-
| HalfSpaceIterator | any model of forward iterator on HalfSpace. |
- Parameters
-
| d | the common denominator of all given lattice point coordinates. |
| domain | a bounded lattice domain. |
| itB | the start of the range of half-spaces. |
| itE | past the end of the range of half-spaces. |
| valid_edge_constraints | when 'true', tells that there are half-spaces that represents th constraints on edges (n-2 cells) lying between two faces (n-1 cells) pointing to different orthants. |
| check_duplicate_constraints | when 'true', the initialization checks if the given range of half-spaces contains axis-aligned half-space constraints already defined by the domain and if so it merges the duplicated constraints, otherwise it accepts and stores the constraints as is. |
- Note
- Asumme your real domain is
{ (-2.25,-1), (3.75, 4.25) } and real halfspaces are ‘{ (1.5*x+2.5*y <= 3), (0.5*x-1.25*y <= 2.5) }. Then for denominator 'd = 4’, you must pass domain={ (-9,-4), (15,17) }, and [itB,itE) = { (6*x+10*y <= 12), (2*x-5*y <= 10) }.
◆ init() [2/2]
template<typename TSpace >
template<typename PointIterator >
Initializes the polytope from a simplex given as a range [itB,itE) of points.
- 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. |
- Returns
- 'true' if [itB,itE) was a valid simplex, otherwise return 'false' and the polytope is empty.
- Note
- If your range is
[itB,itE) = { (3,2), (1,7), (6,6) } and the denominator d = 4, then your polytope is bounded by { (3/4,2/4), (1/4,7/4), (6/4,6/4) }.
-
Use DGtal SimpleMatrix::determinant which is not efficient when the dimension is high. Does not use Eigen to avoid dependency.
◆ insertPoints()
template<typename TSpace >
template<typename PointSet >
Computes the integer points within the polytope.
- Template Parameters
-
| PointSet | any model of set with a method insert( Point ). |
- Parameters
-
| [in,out] | pts_set | the set of points where points within this polytope are inserted. |
- Note
- Quite slow: obtained by checking every point of the polytope domain.
◆ interiorPolytope()
template<typename TSpace >
- Returns
- the interior (in the topological sense) of this polytope, by making all constraints strict.
◆ internalInitFromSegment2D()
template<typename TSpace >
In 2D, builds a valid lattice polytope with empty interior from 2 points.
- Parameters
-
- Returns
- 'true'
◆ internalInitFromSegment3D()
template<typename TSpace >
In 3D, builds a valid lattice polytope with empty interior from 2 points.
- Parameters
-
- Returns
- 'true'
◆ internalInitFromTriangle3D()
template<typename TSpace >
In 3D, builds a valid lattice polytope with empty interior from 3 non-colinear points.
- Parameters
-
| a | any point such that a, b, and c are not colinear. |
| b | any point such that a, b, and c are not colinear. |
| c | any point such that a, b, and c are not colinear. |
- Returns
- 'true' if they were not colinear, false otherwise.
◆ isBoundary()
template<typename TSpace >
- Parameters
-
- Returns
- 'true' if and only if p lies on the boundary of this polytope.
◆ isDomainPointInside()
template<typename TSpace >
- Parameters
-
| p | any point inside the domain of this polytope. |
- Returns
- 'true' if and only if p is inside this polytope.
- Note
- Slightly faster than isInside.
◆ isInside()
template<typename TSpace >
- Parameters
-
- Returns
- 'true' if and only if p is inside this polytope.
◆ isInterior()
template<typename TSpace >
- Parameters
-
- Returns
- 'true' if and only if p is strictly inside this polytope.
◆ isLarge()
template<typename TSpace >
- Parameters
-
| i | the index of the half-space constraint between 0 and nbHalfSpaces() (excluded). |
- Returns
- 'true' if the i-th half space constraint is of the form
Ax <= b, 'false' if it is of the form Ax < b.
◆ isValid()
template<typename TSpace >
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.
◆ nbHalfSpaces()
template<typename TSpace >
- Returns
- the number of half-space constraints.
◆ operator*=() [1/2]
template<typename TSpace >
Dilates this polytope P by t.
- Parameters
-
- Returns
- a reference to 'this', which is now the polytope tP.
◆ operator*=() [2/2]
template<typename TSpace >
Dilates this polytope P by rational r.p/r.q.
- Parameters
-
- Returns
- a reference to 'this', which is now the polytope rP.
◆ operator+=() [1/2]
template<typename TSpace >
Minkowski sum of this polytope with an axis-aligned unit cell.
- Parameters
-
- Returns
- a reference to 'this'.
◆ operator+=() [2/2]
template<typename TSpace >
Minkowski sum of this polytope with a unit segment aligned with some axis.
- Parameters
-
- Returns
- a reference to 'this'.
◆ operator=()
template<typename TSpace >
Assignment.
- Parameters
-
- Returns
- a reference on 'this'.
◆ selfDisplay()
template<typename TSpace >
Writes/Displays the object on an output stream.
- Parameters
-
| out | the output stream where the object is written. |
◆ swap()
template<typename TSpace >
Swaps the content of this object with other. O(1) complexity.
- Parameters
-
template<typename TSpace >
template<typename TSpace >
◆ dimension
template<typename TSpace >
template<typename TSpace >
◆ latticeD
template<typename TSpace >
◆ myValidEdgeConstraints
template<typename TSpace >
template<typename TSpace >
◆ rationalD
template<typename TSpace >
The documentation for this class was generated from the following file:
