DGtal  1.4.beta
TangencyComputer.h
1 
17 #pragma once
18 
31 #if defined(TangencyComputer_RECURSES)
32 #error Recursive header files inclusion detected in TangencyComputer.h
33 #else // defined(TangencyComputer_RECURSES)
35 #define TangencyComputer_RECURSES
36 
37 #if !defined TangencyComputer_h
39 #define TangencyComputer_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <vector>
45 #include <string>
46 #include <limits>
47 #include <unordered_set>
48 #include "DGtal/base/Common.h"
49 #include "DGtal/base/Clone.h"
50 #include "DGtal/kernel/domains/HyperRectDomain.h"
51 #include "DGtal/topology/CCellularGridSpaceND.h"
52 #include "DGtal/kernel/LatticeSetByIntervals.h"
53 #include "DGtal/geometry/volumes/CellGeometry.h"
54 #include "DGtal/geometry/volumes/DigitalConvexity.h"
56 
57 namespace DGtal
58 {
59 
61  // template class TangencyComputer
72  template < typename TKSpace >
74  {
76 
77  public:
79  typedef TKSpace KSpace;
80  typedef typename KSpace::Space Space;
81  typedef typename KSpace::Point Point;
82  typedef typename KSpace::Vector Vector;
84  typedef std::size_t Index;
85  typedef std::size_t Size;
86  typedef std::vector< Index > Path;
89 
90  // ------------------------- Shortest path services --------------------------------
91  public:
92 
95  struct ShortestPaths {
97  typedef std::tuple< Index, Index, double > Node;
98 
103  struct Comparator {
107  bool operator() ( const Node& p1,
108  const Node& p2 ) const
109  {
110  return std::get<2>( p1 ) > std::get<2>( p2 );
111  }
112  };
113 
116  : myTgcyComputer( nullptr ), mySecure( 0.0 )
117  {}
118 
121  ShortestPaths( const ShortestPaths& other ) = default;
124  ShortestPaths( ShortestPaths&& other ) = default;
128  ShortestPaths& operator=( const ShortestPaths& other ) = default;
132  ShortestPaths& operator=( ShortestPaths&& other ) = default;
133 
151  double secure = sqrt( KSpace::dimension ) )
152  : myTgcyComputer( &tgcy_computer ),
153  mySecure( std::max( secure, 0.0 ) )
154  {
155  clear();
156  }
157 
160  {
161  return myTgcyComputer;
162  }
163 
165  Index size() const
166  {
167  return myTgcyComputer->size();
168  }
169 
172  void clear()
173  {
174  const auto nb = size();
175  myAncestor = std::vector< Index > ( nb, nb );
176  myDistance = std::vector< double >( nb, std::numeric_limits<double>::infinity() );
177  myVisited = std::vector< bool > ( nb, false );
178  myQ = std::priority_queue< Node, std::vector< Node >, Comparator >();
179  }
180 
184  void init( Index i )
185  {
186  ASSERT( 0 <= i && i < size() );
187  myQ.push( std::make_tuple( i, i, 0.0 ) );
188  myAncestor[ i ] = i;
189  myDistance[ i ] = 0.0;
190  myVisited [ i ] = true;
191  }
192 
199  template < typename IndexFwdIterator >
200  void init( IndexFwdIterator it, IndexFwdIterator itE )
201  {
202  for ( ; it != itE; ++it )
203  {
204  const auto i = *it;
205  ASSERT( 0 <= i && i < size() );
206  myQ.push( std::make_tuple( i, i, 0.0 ) );
207  }
208  const auto elem = myQ.top();
209  const auto i = std::get<0>( elem );
210  myAncestor[ i ] = i;
211  myDistance[ i ] = 0.0;
212  myVisited [ i ] = true;
213  }
214 
217  bool finished() const
218  {
219  return myQ.empty();
220  }
221 
228  const Node& current() const
229  {
230  ASSERT( ! finished() );
231  return myQ.top();
232  }
233 
238  void expand();
239 
240 
242  bool isValid() const
243  {
244  return myTgcyComputer != nullptr;
245  }
246 
249  const Point& point( Index i ) const
250  {
251  ASSERT( 0 <= i && i < size() );
252  return myTgcyComputer->point( i );
253  }
254 
261  Index ancestor( Index i ) const
262  {
263  ASSERT( 0 <= i && i < size() );
264  return myAncestor[ i ];
265  }
266 
273  double distance( Index i ) const
274  {
275  ASSERT( 0 <= i && i < size() );
276  return myDistance[ i ];
277  }
278 
284  bool isVisited( Index i ) const
285  {
286  return ancestor( i ) < size();
287  }
288 
290  static double infinity()
291  {
292  return std::numeric_limits<double>::infinity();
293  }
294 
301  {
302  Path P;
303  if ( ! isVisited( i ) ) return P;
304  P.push_back( i );
305  while ( ancestor( i ) != i )
306  {
307  i = ancestor( i );
308  P.push_back( i );
309  }
310  return P;
311  }
312 
316  const std::vector< Index >& ancestors() const
317  { return myAncestor; }
318 
321  const std::vector< double >& distances() const
322  { return myDistance; }
323 
326  const std::vector< bool >& visitedPoints() const
327  { return myVisited; }
328 
329  protected:
338  double mySecure;
341  std::vector< Index > myAncestor;
343  std::vector< double > myDistance;
345  std::vector< bool > myVisited;
347  std::priority_queue< Node, std::vector< Node >, Comparator > myQ;
348 
349  protected:
350 
356 
363  std::vector< Index >
365 
366  };
367 
369  friend class ShortestPaths;
370 
371  // ------------------------- Standard services --------------------------------
372  public:
375 
377  TangencyComputer() = default;
378 
381  TangencyComputer( const Self& other ) = default;
382 
385  TangencyComputer( Self&& other ) = default;
386 
390  Self& operator=( const Self& other ) = default;
391 
395  Self& operator=( Self&& other ) = default;
396 
400 
412  template < typename PointIterator >
413  void init( PointIterator itB, PointIterator itE,
414  bool use_lattice_cell_cover = false );
415 
417 
418  // ------------------------- Accessors services --------------------------------
419  public:
422 
424  const KSpace& space() const
425  { return myK; }
426 
428  Size size() const
429  { return myX.size(); }
430 
432  const std::vector< Point >& points() const
433  { return myX; }
434 
437  const Point& point( Index i ) const
438  { return myX[ i ]; }
439 
443  Size index( const Point& a ) const
444  {
445  const auto p = myPt2Index.find( a );
446  return p == myPt2Index.cend() ? size() : p->second;
447  }
448 
450  const CellCover& cellCover() const
451  { return myCellCover; }
452 
456  { return myLatticeCellCover; }
457 
460  double length( const Path& path ) const
461  {
462  auto eucl_d = [] ( const Point& p, const Point& q )
463  { return ( p - q ).norm(); };
464  double l = 0.0;
465  for ( auto i = 1; i < path.size(); i++ )
466  l += eucl_d( point( path[ i-1 ] ), point( path[ i ] ) );
467  return l;
468  }
469 
471 
472  // ------------------------- Tangency services --------------------------------
473  public:
476 
481  bool arePointsCotangent( const Point& a, const Point& b ) const;
482 
488  bool arePointsCotangent( const Point& a, const Point& b, const Point& c ) const;
489 
493  std::vector< Index >
494  getCotangentPoints( const Point& a ) const;
495 
503  std::vector< Index >
505  const std::vector< bool > & to_avoid ) const;
506 
508 
509  // ------------------------- Shortest paths services --------------------------------
510  public:
513 
531  makeShortestPaths( double secure = sqrt( KSpace::dimension ) ) const;
532 
557  std::vector< Path >
558  shortestPaths( const std::vector< Index >& sources,
559  const std::vector< Index >& targets,
560  double secure = sqrt( KSpace::dimension ),
561  bool verbose = false ) const;
562 
588  Path
589  shortestPath( Index source, Index target,
590  double secure = sqrt( KSpace::dimension ),
591  bool verbose = false ) const;
592 
594 
595  // ------------------------- Protected Datas ------------------------------
596  protected:
597 
603  std::vector< Vector > myN;
606  std::vector< double > myDN;
608  std::vector< Point > myX;
617 
619  std::unordered_map< Point, Index > myPt2Index;
620 
621  // ------------------------- Private Datas --------------------------------
622  private:
623 
624 
625  // ------------------------- Internals ------------------------------------
626  private:
627 
629  void setUp();
630 
631  }; // end of class TangencyComputer
632 
635 
642  template <typename TKSpace>
643  std::ostream&
644  operator<< ( std::ostream & out,
645  const TangencyComputer<TKSpace> & object );
646 
648 
649 } // namespace DGtal
650 
651 
653 // Includes inline functions.
654 #include "TangencyComputer.ih"
655 
656 // //
658 
659 #endif // !defined TangencyComputer_h
660 
661 #undef TangencyComputer_RECURSES
662 #endif // else defined(TangencyComputer_RECURSES)
663 
664 
Aim: This class encapsulates its parameter class to indicate that the given parameter is required to ...
Definition: Clone.h:267
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:187
Aim: A class that computes tangency to a given digital set. It provides services to compute all the c...
KSpace myK
The cellular grid space where computations are done.
LatticeCellCover myLatticeCellCover
std::vector< Vector > myN
The vector of all vectors to neighbors (8 in 2D, 26 in 3D, etc).
TangencyComputer(Self &&other)=default
DigitalConvexity< KSpace > myDConv
The digital convexity object used to check full convexity.
const KSpace & space() const
void setUp()
Precomputes some neighborhood tables at construction.
Size index(const Point &a) const
const LatticeCellCover & latticeCellCover() const
bool arePointsCotangent(const Point &a, const Point &b, const Point &c) const
bool myUseLatticeCellCover
Tells if one must use CellCover or LatticeCellCover for computations.
std::unordered_map< Point, Index > myPt2Index
A map giving for each point its index.
TangencyComputer< TKSpace > Self
HyperRectDomain< Space > Domain
std::vector< Index > Path
LatticeSetByIntervals< Space > LatticeCellCover
double length(const Path &path) const
std::vector< Index > getCotangentPoints(const Point &a) const
bool arePointsCotangent(const Point &a, const Point &b) const
std::vector< double > myDN
const CellCover & cellCover() const
TangencyComputer(const Self &other)=default
TangencyComputer(Clone< KSpace > aK)
const Point & point(Index i) const
std::vector< Point > myX
The vector of points defining the digital shape under study.
Self & operator=(const Self &other)=default
ShortestPaths makeShortestPaths(double secure=sqrt(KSpace::dimension)) const
const std::vector< Point > & points() const
Path shortestPath(Index source, Index target, double secure=sqrt(KSpace::dimension), bool verbose=false) const
CellGeometry< KSpace > CellCover
std::vector< Path > shortestPaths(const std::vector< Index > &sources, const std::vector< Index > &targets, double secure=sqrt(KSpace::dimension), bool verbose=false) const
Self & operator=(Self &&other)=default
BOOST_CONCEPT_ASSERT((concepts::CCellularGridSpaceND< TKSpace >))
std::vector< Index > getCotangentPoints(const Point &a, const std::vector< bool > &to_avoid) const
TangencyComputer()=default
Constructor. The object is invalid.
void init(PointIterator itB, PointIterator itE, bool use_lattice_cell_cover=false)
DGtal is the top-level namespace which contains all DGtal functions and types.
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
bool operator()(const Node &p1, const Node &p2) const
std::priority_queue< Node, std::vector< Node >, Comparator > myQ
The queue of points being currently processed.
const std::vector< double > & distances() const
std::vector< Index > getCotangentPoints(Index i) const
ShortestPaths & operator=(const ShortestPaths &other)=default
ShortestPaths(ShortestPaths &&other)=default
std::vector< bool > myVisited
Remembers for each point if it is already visited.
ShortestPaths(const ShortestPaths &other)=default
const std::vector< bool > & visitedPoints() const
ShortestPaths(ConstAlias< TangencyComputer > tgcy_computer, double secure=sqrt(KSpace::dimension))
const Point & point(Index i) const
ShortestPaths()
Default constructor. The object is not valid.
void init(IndexFwdIterator it, IndexFwdIterator itE)
ShortestPaths & operator=(ShortestPaths &&other)=default
std::vector< double > myDistance
Stores for each point its distance to the closest source.
const TangencyComputer * tangencyComputerPtr() const
const std::vector< Index > & ancestors() const
const TangencyComputer * myTgcyComputer
A pointer toward the tangency computer.
std::tuple< Index, Index, double > Node
Type used for Dijkstra's algorithm queue (point, ancestor, distance).
Aim: This concept describes a cellular grid space in nD. In these spaces obtained by cartesian produc...
int max(int a, int b)