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.
|
|
|
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 |
|
|
- Note
- These services consider the rational polytope embedded as continuous polytope. Therefore even vertices of the rational polytope may not be lattice points if their coordinates do not reduce to an integer when divided by the denominator of the rational polytope.
|
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: