DGtal  1.4.beta
EhrhartPolynomial.h
1 
17 #pragma once
18 
31 #if defined(EhrhartPolynomial_RECURSES)
32 #error Recursive header files inclusion detected in EhrhartPolynomial.h
33 #else // defined(EhrhartPolynomial_RECURSES)
34 
35 #define EhrhartPolynomial_RECURSES
36 
37 #if !defined EhrhartPolynomial_h
38 
39 #define EhrhartPolynomial_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <vector>
45 #include "DGtal/base/Common.h"
46 #include "DGtal/kernel/NumberTraits.h"
47 #include "DGtal/kernel/CInteger.h"
48 #include "DGtal/kernel/CSpace.h"
49 #include "DGtal/math/LagrangeInterpolation.h"
50 #include "DGtal/geometry/volumes/BoundedLatticePolytope.h"
52 
53 namespace DGtal
54 {
65  template <typename TSpace, typename TInteger>
67  {
70 
71  // ----------------------- public types -----------------------------------
72  public:
74  typedef TSpace Space;
75  typedef TInteger Integer;
78  typedef typename Lagrange::Polynomial Polynomial;
79  typedef std::size_t Size;
80 
81  // ----------------------- Standard services ------------------------------
82  public:
83 
87  ~EhrhartPolynomial() = default;
88 
93  : myE(), myD( NumberTraits< Integer >::ZERO )
94  {}
95 
100  {
101  init( polytope );
102  }
103 
108  EhrhartPolynomial( const EhrhartPolynomial & other ) = default;
109 
114  EhrhartPolynomial( EhrhartPolynomial&& other ) = default;
115 
121  EhrhartPolynomial & operator=( const EhrhartPolynomial & other ) = default;
122 
128  EhrhartPolynomial & operator=( EhrhartPolynomial&& other ) = default;
129 
131  inline Polynomial numerator() const
132  {
133  return myE;
134  }
135 
137  inline Integer denominator() const
138  {
139  return myD;
140  }
141 
145  void init( const LatticePolytope& polytope )
146  {
147  std::vector< Integer > X( Space::dimension + 1 );
148  std::vector< Integer > Y( Space::dimension + 1 );
151  for ( Integer i = 1; i <= Space::dimension; ++i )
152  {
153  LatticePolytope Q = i * polytope;
154  Integer nb = Q.count();
155  X[ i ] = i;
156  Y[ i ] = nb;
157  }
158  // Compute polynomial (degree d)
159  Lagrange L( X );
160  myE = L.polynomial( Y );
161  myD = L.denominator();
162  }
163 
164  // @param t the dilation factor for this polytope P
165  // @return the number of lattice points of t * P
166  Integer count( Integer t ) const
167  {
168  return myE( t ) / myD;
169  }
170 
171  // @param t the dilation factor for this polytope P
172  // @return 0 if everything is correct.
174  {
175  return myE( t ) % myD;
176  }
177 
178  // @param t the dilation factor for this polytope P
179  // @return the number of lattice points interior to t * P
180  // @note Use reciprocity formula (-1)^d E(-t)
182  return myE.degree() % 2 == 0
183  ? ( myE( -t ) / myD )
184  : - ( myE( -t ) / myD );
185  }
186 
187  // @param t the dilation factor for this polytope P
188  // @return 0 if everything is correct.
190  return myE.degree() % 2 == 0
191  ? ( myE( -t ) % myD )
192  : - ( myE( -t ) % myD );
193  }
194 
195  // ----------------------- Interface --------------------------------------
196  public:
197 
202  void selfDisplay( std::ostream & that_stream ) const
203  {
204  that_stream << "[EhrhartPolynomial num=" << numerator()
205  << " den=" << denominator() << " ]" << std::endl;
206  }
207 
212  bool OK() const
213  {
215  }
216 
217  // ------------------------- Datas ----------------------------------------
218  protected:
219 
224 
225  };
226 
235  template <typename TSpace, typename TInteger>
236  std::ostream&
237  operator<<( std::ostream & that_stream,
238  const EhrhartPolynomial< TSpace, TInteger > & that_object_to_display )
239  {
240  that_object_to_display.selfDisplay( that_stream );
241  return that_stream;
242  }
243 
244 
245 } // namespace DGtal
246 
247 
249 // Includes inline functions/methods if necessary.
250 
251 // //
253 
254 #endif // !defined EhrhartPolynomial_h
255 
256 #undef EhrhartPolynomial_RECURSES
257 #endif // else defined(EhrhartPolynomial_RECURSES)
DGtal::EhrhartPolynomial::remainder
Integer remainder(Integer t) const
Definition: EhrhartPolynomial.h:173
DGtal::EhrhartPolynomial::operator=
EhrhartPolynomial & operator=(const EhrhartPolynomial &other)=default
DGtal::concepts::CSpace
Aim: Defines the concept describing a digital space, ie a cartesian product of integer lines.
Definition: CSpace.h:105
DGtal::EhrhartPolynomial::EhrhartPolynomial
EhrhartPolynomial(const LatticePolytope &polytope)
Definition: EhrhartPolynomial.h:99
DGtal::concepts::CInteger
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:87
DGtal::NumberTraits
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:562
DGtal::EhrhartPolynomial::remainderInterior
Integer remainderInterior(Integer t) const
Definition: EhrhartPolynomial.h:189
DGtal::EhrhartPolynomial::countInterior
Integer countInterior(Integer t) const
Definition: EhrhartPolynomial.h:181
DGtal::EhrhartPolynomial::Polynomial
Lagrange::Polynomial Polynomial
Definition: EhrhartPolynomial.h:78
DGtal::EhrhartPolynomial::EhrhartPolynomial
EhrhartPolynomial()
Definition: EhrhartPolynomial.h:92
DGtal::EhrhartPolynomial::Size
std::size_t Size
Definition: EhrhartPolynomial.h:79
DGtal::operator<<
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
DGtal::EhrhartPolynomial::numerator
Polynomial numerator() const
Definition: EhrhartPolynomial.h:131
DGtal::EhrhartPolynomial::denominator
Integer denominator() const
The (integral) denominator of the Ehrhart polynomial.
Definition: EhrhartPolynomial.h:137
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::EhrhartPolynomial::~EhrhartPolynomial
~EhrhartPolynomial()=default
DGtal::LagrangeInterpolation::denominator
Ring denominator() const
Definition: LagrangeInterpolation.h:138
DGtal::SpaceND::dimension
static const Dimension dimension
static constants to store the dimension.
Definition: SpaceND.h:132
DGtal::EhrhartPolynomial::LatticePolytope
BoundedLatticePolytope< Space > LatticePolytope
Definition: EhrhartPolynomial.h:76
DGtal::BoundedLatticePolytope::count
Integer count() const
DGtal::LagrangeInterpolation::polynomial
Polynomial polynomial(const std::vector< Ring > &yvalues)
Definition: LagrangeInterpolation.h:182
DGtal::EhrhartPolynomial::Space
TSpace Space
Definition: EhrhartPolynomial.h:74
DGtal::EhrhartPolynomial::myD
Integer myD
The (integral) denominator of the Ehrhart polynomial.
Definition: EhrhartPolynomial.h:223
DGtal::LagrangeInterpolation
Aim: This class implements Lagrange basis functions and Lagrange interpolation.
Definition: LagrangeInterpolation.h:62
DGtal::EhrhartPolynomial::selfDisplay
void selfDisplay(std::ostream &that_stream) const
Definition: EhrhartPolynomial.h:202
DGtal::MPolynomial::degree
int degree() const
Definition: MPolynomial.h:1109
DGtal::EhrhartPolynomial
Aim: This class implements the class Ehrhart Polynomial which is related to lattice point enumeration...
Definition: EhrhartPolynomial.h:66
DGtal::MPolynomial
Aim: Represents a multivariate polynomial, i.e. an element of , where K is some ring or field.
Definition: MPolynomial.h:58
DGtal::EhrhartPolynomial::Self
EhrhartPolynomial< TSpace, TInteger > Self
Definition: EhrhartPolynomial.h:73
DGtal::BoundedLatticePolytope
Aim: Represents an nD lattice polytope, i.e. a convex polyhedron bounded with vertices with integer c...
Definition: BoundedLatticePolytope.h:73
DGtal::EhrhartPolynomial::BOOST_CONCEPT_ASSERT
BOOST_CONCEPT_ASSERT((concepts::CSpace< TSpace >))
DGtal::EhrhartPolynomial::myE
Polynomial myE
The Ehrhart polynomial (integral numerator part)
Definition: EhrhartPolynomial.h:221
DGtal::EhrhartPolynomial::Integer
TInteger Integer
Definition: EhrhartPolynomial.h:75
DGtal::EhrhartPolynomial::init
void init(const LatticePolytope &polytope)
Definition: EhrhartPolynomial.h:145
DGtal::EhrhartPolynomial::OK
bool OK() const
Definition: EhrhartPolynomial.h:212
DGtal::EhrhartPolynomial::count
Integer count(Integer t) const
Definition: EhrhartPolynomial.h:166
DGtal::EhrhartPolynomial::Lagrange
LagrangeInterpolation< Integer > Lagrange
Definition: EhrhartPolynomial.h:77