DGtal  1.5.beta
BoundedLatticePolytope.h
1 
17 #pragma once
18 
31 #if defined(BoundedLatticePolytope_RECURSES)
32 #error Recursive header files inclusion detected in BoundedLatticePolytope.h
33 #else // defined(BoundedLatticePolytope_RECURSES)
35 #define BoundedLatticePolytope_RECURSES
36 
37 #if !defined BoundedLatticePolytope_h
39 #define BoundedLatticePolytope_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <list>
45 #include <vector>
46 #include <string>
47 #include "DGtal/base/Common.h"
48 #include "DGtal/kernel/CSpace.h"
49 #include "DGtal/kernel/domains/HyperRectDomain.h"
50 #include "DGtal/arithmetic/IntegerComputer.h"
51 #include "DGtal/arithmetic/ClosedIntegerHalfPlane.h"
53 
54 namespace DGtal
55 {
57  // template class BoundedLatticePolytope
72  template < typename TSpace >
74  {
76 
77  public:
79  typedef TSpace Space;
80  typedef typename Space::Integer Integer;
81  typedef typename Space::Point Point;
82  typedef typename Space::Vector Vector;
83  typedef std::vector<Vector> InequalityMatrix;
84  typedef std::vector<Integer> InequalityVector;
87 #ifdef WITH_BIGINTEGER
89 #else
90  typedef DGtal::int64_t BigInteger;
91 #endif
92  static const Dimension dimension = Space::dimension;
93 
98  struct UnitSegment {
100  UnitSegment( Dimension d ) : k( d ) {}
101  };
102 
110  };
111 
119  };
120 
126  struct UnitCell {
127  std::vector<Dimension> dims;
128  UnitCell( std::initializer_list<Dimension> l )
129  : dims( l.begin(), l.end() ) {}
130 
137  friend std::ostream&
138  operator<< ( std::ostream & out,
139  const UnitCell & object )
140  {
141  out << "{";
142  for ( Dimension i = 0; i < object.dims.size(); ++i ) out << object.dims[ i ];
143  out << "}";
144  return out;
145  }
146  };
147 
154  std::vector<Dimension> dims;
155  RightStrictUnitCell( std::initializer_list<Dimension> l )
156  : dims( l.begin(), l.end() ) {}
157 
164  friend std::ostream&
165  operator<< ( std::ostream & out,
166  const RightStrictUnitCell & object )
167  {
168  out << "{";
169  for ( Dimension i = 0; i < object.dims.size(); ++i ) out << object.dims[ i ];
170  out << "}";
171  return out;
172  }
173  };
174 
181  std::vector<Dimension> dims;
182  LeftStrictUnitCell( std::initializer_list<Dimension> l )
183  : dims( l.begin(), l.end() ) {}
184 
191  friend std::ostream&
192  operator<< ( std::ostream & out,
193  const LeftStrictUnitCell & object )
194  {
195  out << "{";
196  for ( Dimension i = 0; i < object.dims.size(); ++i ) out << object.dims[ i ];
197  out << "}";
198  return out;
199  }
200  };
201 
204 
209 
214 
219  BoundedLatticePolytope ( const Self & other ) = default;
220 
221 
228  BoundedLatticePolytope( std::initializer_list<Point> l );
229 
238  template <typename PointIterator>
239  BoundedLatticePolytope( PointIterator itB, PointIterator itE );
240 
260  template <typename HalfSpaceIterator>
262  HalfSpaceIterator itB, HalfSpaceIterator itE,
263  bool valid_edge_constraints = false,
264  bool check_duplicate_constraints = false );
265 
285  template <typename HalfSpaceIterator>
286  void init( const Domain& domain,
287  HalfSpaceIterator itB, HalfSpaceIterator itE,
288  bool valid_edge_constraints = false,
289  bool check_duplicate_constraints = false );
290 
291 
304  template <typename PointIterator>
305  bool init( PointIterator itB, PointIterator itE );
306 
312  Self & operator= ( const Self & other ) = default;
313 
315  void clear();
316 
320 
324 
326 
327  // ----------------------- Accessor services ------------------------------
328  public:
331 
333  const Domain& getDomain() const;
334 
336  unsigned int nbHalfSpaces() const;
337 
343  const Vector& getA( unsigned int i ) const;
344 
350  Integer getB( unsigned int i ) const;
351 
357  bool isLarge( unsigned int i ) const;
358 
360  const InequalityMatrix& getA() const;
361 
363  const InequalityVector& getB() const;
367  const std::vector<bool>& getI() const;
368 
373  bool canBeSummed() const;
374 
376 
377  // ----------------------- Check point services ------------------------------
378  public:
379 
382 
387  bool isInside( const Point& p ) const;
388 
395  bool isDomainPointInside( const Point& p ) const;
396 
401  bool isInterior( const Point& p ) const;
402 
407  bool isBoundary( const Point& p ) const;
408 
410 
411  // ----------------------- Modification services ------------------------------
412  public:
413 
416 
417 
430  unsigned int cut( Dimension k, bool pos, Integer b, bool large = true );
431 
449  unsigned int cut( const Vector& a, Integer b, bool large = true,
450  bool valid_edge_constraint = false );
451 
468  unsigned int cut( const HalfSpace & hs, bool large = true,
469  bool valid_edge_constraint = false );
470 
475  void swap( BoundedLatticePolytope & other );
476 
477 
484 
492 
500 
508 
516 
524 
533 
534  // ----------------------- Enumeration services ------------------------------
535  public:
536 
539 
548  Integer count() const;
549 
562 
575 
587  Integer countWithin( Point low, Point hi ) const;
588 
607 
617  void getPoints( std::vector<Point>& pts ) const;
618 
633  void getKPoints( std::vector<Point>& pts, const Point& alpha_shift ) const;
634 
644  void getInteriorPoints( std::vector<Point>& pts ) const;
645 
655  void getBoundaryPoints( std::vector<Point>& pts ) const;
656 
668  template <typename PointSet>
669  void insertPoints( PointSet& pts_set ) const;
670 
687  template <typename PointSet>
688  void insertKPoints( PointSet& pts_set, const Point& alpha_shift ) const;
689 
691 
692  // -------------- Enumeration services (old methods by scanning ) --------------
693  public:
694 
697 
706 
718 
730 
742 
760 
769  void getPointsByScanning( std::vector<Point>& pts ) const;
770 
779  void getInteriorPointsByScanning( std::vector<Point>& pts ) const;
780 
789  void getBoundaryPointsByScanning( std::vector<Point>& pts ) const;
790 
801  template <typename PointSet>
802  void insertPointsByScanning( PointSet& pts_set ) const;
803 
805 
806 
807  // ----------------------- Interface --------------------------------------
808  public:
811 
816  void selfDisplay ( std::ostream & out ) const;
817 
824  bool isValid() const;
825 
829  std::string className() const;
830 
832 
833  // ------------------------- Protected Datas ------------------------------
834  protected:
842  std::vector<bool> I;
845 
846  // ------------------------- Private Datas --------------------------------
847  private:
848 
849 
850  // ------------------------- Internals ------------------------------------
851  private:
859 
866 
873 
874  }; // end of class BoundedLatticePolytope
875 
876  namespace detail {
885  template <DGtal::Dimension N, typename TInteger>
887  typedef TInteger Integer;
889  typedef typename Space::Point Point;
890  typedef typename Space::Vector Vector;
893 
906  static void
907  addEdgeConstraint( Polytope& , unsigned int , unsigned int ,
908  const std::vector<Point>& )
909  {
910  trace.error() << "[BoundedLatticePolytopeHelper::addEdgeConstraint]"
911  << " this method is only implemented in 3D." << std::endl;
912  }
913 
916  static
917  Vector crossProduct( const Vector& , const Vector& )
918  {
919  trace.error() << "[BoundedLatticePolytopeHelper::crossProduct]"
920  << " this method is only implemented in 3D." << std::endl;
921  return Vector::zero;
922  }
923  };
924 
932  template <typename TInteger>
933  struct BoundedLatticePolytopeSpecializer<3, TInteger> {
934  typedef TInteger Integer;
936  typedef typename Space::Point Point;
937  typedef typename Space::Vector Vector;
940 
950  static void
951  addEdgeConstraint( Polytope& P, unsigned int i, unsigned int j,
952  const std::vector<Point>& pts )
953  {
954  Vector ab = pts[ i ] - pts[ j ];
955  for ( int s = 0; s < 2; s++ )
956  for ( Dimension k = 0; k < dimension; ++k )
957  {
958  Vector n = ab.crossProduct( Point::base( k, (s == 0) ? 1 : -1 ) );
959  Integer b = n.dot( pts[ i ] );
960  std::size_t nb_in = 0;
961  for ( auto p : pts ) {
962  Integer v = n.dot( p );
963  if ( v < b ) nb_in++;
964  }
965  if ( nb_in == pts.size() - 2 ) {
966  P.cut( n, b, true, true );
967  }
968  }
969  }
974  static
975  Vector crossProduct( const Vector& v1, const Vector& v2 )
976  {
977  return v1.crossProduct( v2 );
978  }
979  };
980  }
981 
984 
991  template <typename TSpace>
992  std::ostream&
993  operator<< ( std::ostream & out,
994  const BoundedLatticePolytope<TSpace> & object );
995 
996 
1002  template <typename TSpace>
1005  const BoundedLatticePolytope<TSpace> & P );
1006 
1007 
1015  template <typename TSpace>
1019 
1027  template <typename TSpace>
1031 
1039  template <typename TSpace>
1043 
1051  template <typename TSpace>
1055 
1063  template <typename TSpace>
1067 
1075  template <typename TSpace>
1079 
1081 
1082 } // namespace DGtal
1083 
1084 
1086 // Includes inline functions.
1087 #include "BoundedLatticePolytope.ih"
1088 
1089 // //
1091 
1092 #endif // !defined BoundedLatticePolytope_h
1093 
1094 #undef BoundedLatticePolytope_RECURSES
1095 #endif // else defined(BoundedLatticePolytope_RECURSES)
Aim: Represents an nD lattice polytope, i.e. a convex polyhedron bounded with vertices with integer c...
void init(const Domain &domain, HalfSpaceIterator itB, HalfSpaceIterator itE, bool valid_edge_constraints=false, bool check_duplicate_constraints=false)
Integer countWithin(Point low, Point hi) const
void getInteriorPoints(std::vector< Point > &pts) const
unsigned int nbHalfSpaces() const
BoundedLatticePolytope(PointIterator itB, PointIterator itE)
void getInteriorPointsByScanning(std::vector< Point > &pts) const
bool isInside(const Point &p) const
Integer countByScanning() const
BoundedLatticePolytope(const Domain &domain, HalfSpaceIterator itB, HalfSpaceIterator itE, bool valid_edge_constraints=false, bool check_duplicate_constraints=false)
Integer getB(unsigned int i) const
BoundedLatticePolytope(const Self &other)=default
const std::vector< bool > & getI() const
BOOST_CONCEPT_ASSERT((concepts::CSpace< TSpace >))
Integer countInteriorByScanning() const
void getKPoints(std::vector< Point > &pts, const Point &alpha_shift) const
void clear()
Clears the polytope.
Self & operator+=(UnitCell c)
unsigned int cut(Dimension k, bool pos, Integer b, bool large=true)
ClosedIntegerHalfPlane< Space > HalfSpace
Integer countUpToByScanning(Integer max) const
void swap(BoundedLatticePolytope &other)
std::vector< bool > I
Are inequalities large ?
bool isLarge(unsigned int i) const
unsigned int cut(const Vector &a, Integer b, bool large=true, bool valid_edge_constraint=false)
std::vector< Vector > InequalityMatrix
bool init(PointIterator itB, PointIterator itE)
const Vector & getA(unsigned int i) const
bool internalInitFromSegment2D(Point a, Point b)
BoundedLatticePolytope interiorPolytope() const
unsigned int cut(const HalfSpace &hs, bool large=true, bool valid_edge_constraint=false)
Integer countBoundaryByScanning() const
std::vector< Integer > InequalityVector
Self & operator+=(UnitSegment s)
Self & operator+=(RightStrictUnitSegment s)
BoundedLatticePolytope< TSpace > Self
bool internalInitFromTriangle3D(Point a, Point b, Point c)
void getBoundaryPoints(std::vector< Point > &pts) const
Integer countWithinByScanning(Point low, Point hi) const
InequalityMatrix A
The matrix A in the polytope representation .
bool isBoundary(const Point &p) const
void getPointsByScanning(std::vector< Point > &pts) const
void selfDisplay(std::ostream &out) const
Self & operator+=(RightStrictUnitCell c)
HyperRectDomain< Space > Domain
void insertKPoints(PointSet &pts_set, const Point &alpha_shift) const
const InequalityVector & getB() const
Self & operator=(const Self &other)=default
void getBoundaryPointsByScanning(std::vector< Point > &pts) const
std::string className() const
const Domain & getDomain() const
Self & operator*=(Integer t)
bool internalInitFromSegment3D(Point a, Point b)
Integer countUpTo(Integer max) const
bool isDomainPointInside(const Point &p) const
Self & operator+=(LeftStrictUnitCell c)
BoundedLatticePolytope(std::initializer_list< Point > l)
bool myValidEdgeConstraints
Indicates if Minkowski sums with segments will be valid.
BoundedLatticePolytope closurePolytope() const
bool isInterior(const Point &p) const
void insertPointsByScanning(PointSet &pts_set) const
void insertPoints(PointSet &pts_set) const
void getPoints(std::vector< Point > &pts) const
InequalityVector B
The vector B in the polytope representation .
const InequalityMatrix & getA() const
Self & operator+=(LeftStrictUnitSegment s)
static Self base(Dimension k, Component val=1)
auto crossProduct(const PointVector< dim, OtherComponent, OtherStorage > &v) const -> decltype(DGtal::crossProduct(*this, v))
Cross product with a PointVector.
static Self zero
Static const for zero PointVector.
Definition: PointVector.h:1595
TInteger Integer
Arithmetic ring induced by (+,-,*) and Integer numbers.
Definition: SpaceND.h:102
static const Dimension dimension
static constants to store the dimension.
Definition: SpaceND.h:132
std::ostream & error()
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
DGtal::uint32_t Dimension
Definition: Common.h:136
Trace trace
Definition: Common.h:153
KForm< Calculus, order, duality > operator*(const typename Calculus::Scalar &scalar, const KForm< Calculus, order, duality > &form)
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition: BasicTypes.h:79
Circulator< TIterator > operator+(typename IteratorCirculatorTraits< TIterator >::Difference d, Circulator< TIterator > &object)
Definition: Circulator.h:453
friend std::ostream & operator<<(std::ostream &out, const LeftStrictUnitCell &object)
LeftStrictUnitCell(std::initializer_list< Dimension > l)
RightStrictUnitCell(std::initializer_list< Dimension > l)
friend std::ostream & operator<<(std::ostream &out, const RightStrictUnitCell &object)
friend std::ostream & operator<<(std::ostream &out, const UnitCell &object)
UnitCell(std::initializer_list< Dimension > l)
Aim: A half-space specified by a vector N and a constant c. The half-space is the set .
Aim: Defines the concept describing a digital space, ie a cartesian product of integer lines.
Definition: CSpace.h:106
static void addEdgeConstraint(Polytope &P, unsigned int i, unsigned int j, const std::vector< Point > &pts)
static Vector crossProduct(const Vector &v1, const Vector &v2)
Aim: It is just a helper class for BoundedLatticePolytope to add dimension specific static methods.
static Vector crossProduct(const Vector &, const Vector &)
static void addEdgeConstraint(Polytope &, unsigned int, unsigned int, const std::vector< Point > &)
int max(int a, int b)
Domain domain