DGtal  1.5.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)
35 #define EhrhartPolynomial_RECURSES
36
37 #if !defined EhrhartPolynomial_h
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
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)
Aim: Represents an nD lattice polytope, i.e. a convex polyhedron bounded with vertices with integer c...
Aim: This class implements the class Ehrhart Polynomial which is related to lattice point enumeration...
Integer countInterior(Integer t) const
void init(const LatticePolytope &polytope)
EhrhartPolynomial & operator=(const EhrhartPolynomial &other)=default
BoundedLatticePolytope< Space > LatticePolytope
LagrangeInterpolation< Integer > Lagrange
void selfDisplay(std::ostream &that_stream) const
EhrhartPolynomial< TSpace, TInteger > Self
EhrhartPolynomial(const LatticePolytope &polytope)
EhrhartPolynomial(EhrhartPolynomial &&other)=default
Integer myD
The (integral) denominator of the Ehrhart polynomial.
Integer remainder(Integer t) const
Integer denominator() const
The (integral) denominator of the Ehrhart polynomial.
Lagrange::Polynomial Polynomial
Polynomial myE
The Ehrhart polynomial (integral numerator part)
BOOST_CONCEPT_ASSERT((concepts::CInteger< TInteger >))
EhrhartPolynomial(const EhrhartPolynomial &other)=default
Polynomial numerator() const
EhrhartPolynomial & operator=(EhrhartPolynomial &&other)=default
Integer count(Integer t) const
Integer remainderInterior(Integer t) const
BOOST_CONCEPT_ASSERT((concepts::CSpace< TSpace >))
Aim: This class implements Lagrange basis functions and Lagrange interpolation.
Polynomial polynomial(const std::vector< Ring > &yvalues)
Aim: Represents a multivariate polynomial, i.e. an element of , where K is some ring or field.
Definition: MPolynomial.h:965
int degree() const
Definition: MPolynomial.h:1119
DGtal is the top-level namespace which contains all DGtal functions and types.
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:564
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:88
Aim: Defines the concept describing a digital space, ie a cartesian product of integer lines.
Definition: CSpace.h:106