DGtal  1.3.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)
34 
35 #define TangencyComputer_RECURSES
36 
37 #if !defined TangencyComputer_h
38 
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/geometry/volumes/CellGeometry.h"
53 #include "DGtal/geometry/volumes/DigitalConvexity.h"
55 
56 namespace DGtal
57 {
58 
60  // template class TangencyComputer
71  template < typename TKSpace >
73  {
75 
76  public:
78  typedef TKSpace KSpace;
79  typedef typename KSpace::Space Space;
80  typedef typename KSpace::Point Point;
81  typedef typename KSpace::Vector Vector;
83  typedef std::size_t Index;
84  typedef std::size_t Size;
85  typedef std::vector< Index > Path;
86 
87  // ------------------------- Shortest path services --------------------------------
88  public:
89 
92  struct ShortestPaths {
94  typedef std::tuple< Index, Index, double > Node;
95 
100  struct Comparator {
104  bool operator() ( const Node& p1,
105  const Node& p2 ) const
106  {
107  return std::get<2>( p1 ) > std::get<2>( p2 );
108  }
109  };
110 
113  : myTgcyComputer( nullptr ), mySecure( 0.0 )
114  {}
115 
118  ShortestPaths( const ShortestPaths& other ) = default;
121  ShortestPaths( ShortestPaths&& other ) = default;
125  ShortestPaths& operator=( const ShortestPaths& other ) = default;
129  ShortestPaths& operator=( ShortestPaths&& other ) = default;
130 
148  double secure = sqrt( KSpace::dimension ) )
149  : myTgcyComputer( &tgcy_computer ),
150  mySecure( std::max( secure, 0.0 ) )
151  {
152  clear();
153  }
154 
157  {
158  return myTgcyComputer;
159  }
160 
162  Index size() const
163  {
164  return myTgcyComputer->size();
165  }
166 
169  void clear()
170  {
171  const int nb = size();
172  myAncestor = std::vector< Index > ( nb, nb );
173  myDistance = std::vector< double >( nb, std::numeric_limits<double>::infinity() );
174  myVisited = std::vector< bool > ( nb, false );
175  myQ = std::priority_queue< Node, std::vector< Node >, Comparator >();
176  }
177 
181  void init( Index i )
182  {
183  ASSERT( 0 <= i && i < size() );
184  myQ.push( std::make_tuple( i, i, 0.0 ) );
185  myAncestor[ i ] = i;
186  myDistance[ i ] = 0.0;
187  myVisited [ i ] = true;
188  }
189 
196  template < typename IndexFwdIterator >
197  void init( IndexFwdIterator it, IndexFwdIterator itE )
198  {
199  for ( ; it != itE; ++it )
200  {
201  const auto i = *it;
202  ASSERT( 0 <= i && i < size() );
203  myQ.push( std::make_tuple( i, i, 0.0 ) );
204  }
205  const auto elem = myQ.top();
206  const auto i = std::get<0>( elem );
207  myAncestor[ i ] = i;
208  myDistance[ i ] = 0.0;
209  myVisited [ i ] = true;
210  }
211 
214  bool finished() const
215  {
216  return myQ.empty();
217  }
218 
225  const Node& current() const
226  {
227  ASSERT( ! finished() );
228  return myQ.top();
229  }
230 
235  void expand();
236 
237 
239  bool isValid() const
240  {
241  return myTgcyComputer != nullptr;
242  }
243 
246  const Point& point( Index i ) const
247  {
248  ASSERT( 0 <= i && i < size() );
249  return myTgcyComputer->point( i );
250  }
251 
258  Index ancestor( Index i ) const
259  {
260  ASSERT( 0 <= i && i < size() );
261  return myAncestor[ i ];
262  }
263 
270  double distance( Index i ) const
271  {
272  ASSERT( 0 <= i && i < size() );
273  return myDistance[ i ];
274  }
275 
281  bool isVisited( Index i ) const
282  {
283  return ancestor( i ) < size();
284  }
285 
287  static double infinity()
288  {
289  return std::numeric_limits<double>::infinity();
290  }
291 
298  {
299  Path P;
300  if ( ! isVisited( i ) ) return P;
301  P.push_back( i );
302  while ( ancestor( i ) != i )
303  {
304  i = ancestor( i );
305  P.push_back( i );
306  }
307  return P;
308  }
309 
313  const std::vector< Index >& ancestors() const
314  { return myAncestor; }
315 
318  const std::vector< double >& distances() const
319  { return myDistance; }
320 
323  const std::vector< bool >& visitedPoints() const
324  { return myVisited; }
325 
326  protected:
335  double mySecure;
338  std::vector< Index > myAncestor;
340  std::vector< double > myDistance;
342  std::vector< bool > myVisited;
344  std::priority_queue< Node, std::vector< Node >, Comparator > myQ;
345 
346  protected:
347 
352  void propagate( Index current );
353 
360  std::vector< Index >
361  getCotangentPoints( Index i ) const;
362 
363  };
364 
366  friend class ShortestPaths;
367 
368  // ------------------------- Standard services --------------------------------
369  public:
372 
374  TangencyComputer() = default;
375 
378  TangencyComputer( const Self& other ) = default;
379 
382  TangencyComputer( Self&& other ) = default;
383 
387  Self& operator=( const Self& other ) = default;
388 
392  Self& operator=( Self&& other ) = default;
393 
397 
404  template < typename PointIterator >
405  void init( PointIterator itB, PointIterator itE );
406 
408 
409  // ------------------------- Accessors services --------------------------------
410  public:
413 
415  const KSpace& space() const
416  { return myK; }
417 
419  Size size() const
420  { return myX.size(); }
421 
423  const std::vector< Point >& points() const
424  { return myX; }
425 
428  const Point& point( Index i ) const
429  { return myX[ i ]; }
430 
434  Size index( const Point& a ) const
435  {
436  const auto p = myPt2Index.find( a );
437  return p == myPt2Index.cend() ? size() : p->second;
438  }
439 
442  { return myCellCover; }
443 
446  double length( const Path& path ) const
447  {
448  auto eucl_d = [] ( const Point& p, const Point& q )
449  { return ( p - q ).norm(); };
450  double l = 0.0;
451  for ( auto i = 1; i < path.size(); i++ )
452  l += eucl_d( point( path[ i-1 ] ), point( path[ i ] ) );
453  return l;
454  }
455 
457 
458  // ------------------------- Tangency services --------------------------------
459  public:
462 
467  bool arePointsCotangent( const Point& a, const Point& b ) const;
468 
472  std::vector< Index >
473  getCotangentPoints( const Point& a ) const;
474 
482  std::vector< Index >
483  getCotangentPoints( const Point& a,
484  const std::vector< bool > & to_avoid ) const;
485 
487 
488  // ------------------------- Shortest paths services --------------------------------
489  public:
492 
510  makeShortestPaths( double secure = sqrt( KSpace::dimension ) ) const;
511 
536  std::vector< Path >
537  shortestPaths( const std::vector< Index >& sources,
538  const std::vector< Index >& targets,
539  double secure = sqrt( KSpace::dimension ),
540  bool verbose = false ) const;
541 
567  Path
568  shortestPath( Index source, Index target,
569  double secure = sqrt( KSpace::dimension ),
570  bool verbose = false ) const;
571 
573 
574  // ------------------------- Protected Datas ------------------------------
575  protected:
576 
582  std::vector< Vector > myN;
585  std::vector< double > myDN;
587  std::vector< Point > myX;
591  std::unordered_map< Point, Index > myPt2Index;
592 
593  // ------------------------- Private Datas --------------------------------
594  private:
595 
596 
597  // ------------------------- Internals ------------------------------------
598  private:
599 
601  void setUp();
602 
603  }; // end of class TangencyComputer
604 
607 
614  template <typename TKSpace>
615  std::ostream&
616  operator<< ( std::ostream & out,
617  const TangencyComputer<TKSpace> & object );
618 
620 
621 } // namespace DGtal
622 
623 
625 // Includes inline functions.
626 #include "TangencyComputer.ih"
627 
628 // //
630 
631 #endif // !defined TangencyComputer_h
632 
633 #undef TangencyComputer_RECURSES
634 #endif // else defined(TangencyComputer_RECURSES)
635 
636 
DGtal::TangencyComputer::Index
std::size_t Index
Definition: TangencyComputer.h:83
DGtal::Clone
Aim: This class encapsulates its parameter class to indicate that the given parameter is required to ...
Definition: Clone.h:266
DGtal::TangencyComputer::myK
KSpace myK
The cellular grid space where computations are done.
Definition: TangencyComputer.h:578
DGtal::TangencyComputer::points
const std::vector< Point > & points() const
Definition: TangencyComputer.h:423
DGtal::ConstAlias
Aim: This class encapsulates its parameter class so that to indicate to the user that the object/poin...
Definition: ConstAlias.h:186
DGtal::TangencyComputer::ShortestPaths::Node
std::tuple< Index, Index, double > Node
Type used for Dijkstra's algorithm queue (point, ancestor, distance).
Definition: TangencyComputer.h:94
DGtal::HyperRectDomain< Space >
DGtal::TangencyComputer::ShortestPaths::isValid
bool isValid() const
Definition: TangencyComputer.h:239
max
int max(int a, int b)
Definition: testArithmeticalDSS.cpp:1108
DGtal::TangencyComputer::ShortestPaths::myTgcyComputer
const TangencyComputer * myTgcyComputer
A pointer toward the tangency computer.
Definition: TangencyComputer.h:328
DGtal::TangencyComputer::ShortestPaths::Comparator
Definition: TangencyComputer.h:100
DGtal::TangencyComputer::ShortestPaths::ShortestPaths
ShortestPaths()
Default constructor. The object is not valid.
Definition: TangencyComputer.h:112
DGtal::TangencyComputer::ShortestPaths::ancestor
Index ancestor(Index i) const
Definition: TangencyComputer.h:258
Index
SMesh::Index Index
Definition: fullConvexitySphereGeodesics.cpp:117
DGtal::concepts::CCellularGridSpaceND
Aim: This concept describes a cellular grid space in nD. In these spaces obtained by cartesian produc...
Definition: CCellularGridSpaceND.h:162
DGtal::TangencyComputer::ShortestPaths::distance
double distance(Index i) const
Definition: TangencyComputer.h:270
DGtal::TangencyComputer::Space
KSpace::Space Space
Definition: TangencyComputer.h:79
DGtal::TangencyComputer
Aim: A class that computes tangency to a given digital set. It provides services to compute all the c...
Definition: TangencyComputer.h:72
DGtal::TangencyComputer::point
const Point & point(Index i) const
Definition: TangencyComputer.h:428
DGtal::TangencyComputer::ShortestPaths::expand
void expand()
DGtal::TangencyComputer::ShortestPaths::clear
void clear()
Definition: TangencyComputer.h:169
DGtal::TangencyComputer::myDN
std::vector< double > myDN
Definition: TangencyComputer.h:585
DGtal::TangencyComputer::ShortestPaths::current
const Node & current() const
Definition: TangencyComputer.h:225
DGtal::TangencyComputer::ShortestPaths::propagate
void propagate(Index current)
DGtal::TangencyComputer::ShortestPaths::myQ
std::priority_queue< Node, std::vector< Node >, Comparator > myQ
The queue of points being currently processed.
Definition: TangencyComputer.h:344
DGtal::TangencyComputer::ShortestPaths::isVisited
bool isVisited(Index i) const
Definition: TangencyComputer.h:281
DGtal::TangencyComputer::ShortestPaths::myAncestor
std::vector< Index > myAncestor
Definition: TangencyComputer.h:338
DGtal::TangencyComputer::myN
std::vector< Vector > myN
The vector of all vectors to neighbors (8 in 2D, 26 in 3D, etc).
Definition: TangencyComputer.h:582
DGtal::TangencyComputer::Self
TangencyComputer< TKSpace > Self
Definition: TangencyComputer.h:77
DGtal::TangencyComputer::arePointsCotangent
bool arePointsCotangent(const Point &a, const Point &b) const
DGtal::TangencyComputer::ShortestPaths
friend class ShortestPaths
ShortestPaths may access to datas of TangencyComputer.
Definition: TangencyComputer.h:366
DGtal::operator<<
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
DGtal::TangencyComputer::makeShortestPaths
ShortestPaths makeShortestPaths(double secure=sqrt(KSpace::dimension)) const
DGtal::TangencyComputer::myCellCover
CellGeometry< KSpace > myCellCover
The cell geometry representing all the cells touching the digital shape.
Definition: TangencyComputer.h:589
DGtal::SpaceND
Definition: SpaceND.h:95
DGtal::TangencyComputer::BOOST_CONCEPT_ASSERT
BOOST_CONCEPT_ASSERT((concepts::CCellularGridSpaceND< TKSpace >))
DGtal::TangencyComputer::index
Size index(const Point &a) const
Definition: TangencyComputer.h:434
DGtal::TangencyComputer::myDConv
DigitalConvexity< KSpace > myDConv
The digital convexity object used to check full convexity.
Definition: TangencyComputer.h:580
DGtal::KhalimskySpaceND::dimension
static const constexpr Dimension dimension
Definition: KhalimskySpaceND.h:430
DGtal::TangencyComputer::ShortestPaths::size
Index size() const
Definition: TangencyComputer.h:162
DGtal::TangencyComputer::ShortestPaths::tangencyComputerPtr
const TangencyComputer * tangencyComputerPtr() const
Definition: TangencyComputer.h:156
DGtal::TangencyComputer::ShortestPaths::myDistance
std::vector< double > myDistance
Stores for each point its distance to the closest source.
Definition: TangencyComputer.h:340
DGtal::TangencyComputer::Domain
HyperRectDomain< Space > Domain
Definition: TangencyComputer.h:82
DGtal::TangencyComputer::ShortestPaths::mySecure
double mySecure
Definition: TangencyComputer.h:335
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::TangencyComputer::TangencyComputer
TangencyComputer()=default
Constructor. The object is invalid.
DGtal::TangencyComputer::ShortestPaths::init
void init(IndexFwdIterator it, IndexFwdIterator itE)
Definition: TangencyComputer.h:197
DGtal::TangencyComputer::ShortestPaths::myVisited
std::vector< bool > myVisited
Remembers for each point if it is already visited.
Definition: TangencyComputer.h:342
DGtal::TangencyComputer::Point
KSpace::Point Point
Definition: TangencyComputer.h:80
DGtal::TangencyComputer::KSpace
TKSpace KSpace
Definition: TangencyComputer.h:78
DGtal::TangencyComputer::ShortestPaths::distances
const std::vector< double > & distances() const
Definition: TangencyComputer.h:318
DGtal::TangencyComputer::myPt2Index
std::unordered_map< Point, Index > myPt2Index
A map giving for each point its index.
Definition: TangencyComputer.h:591
DGtal::TangencyComputer::size
Size size() const
Definition: TangencyComputer.h:419
DGtal::TangencyComputer::Path
std::vector< Index > Path
Definition: TangencyComputer.h:85
DGtal::TangencyComputer::ShortestPaths::point
const Point & point(Index i) const
Definition: TangencyComputer.h:246
DGtal::TangencyComputer::getCotangentPoints
std::vector< Index > getCotangentPoints(const Point &a) const
DGtal::TangencyComputer::ShortestPaths::ancestors
const std::vector< Index > & ancestors() const
Definition: TangencyComputer.h:313
DGtal::TangencyComputer::init
void init(PointIterator itB, PointIterator itE)
DGtal::TangencyComputer::ShortestPaths::finished
bool finished() const
Definition: TangencyComputer.h:214
DGtal::TangencyComputer::cellCover
const CellGeometry< KSpace > & cellCover() const
Definition: TangencyComputer.h:441
DGtal::TangencyComputer::myX
std::vector< Point > myX
The vector of points defining the digital shape under study.
Definition: TangencyComputer.h:587
DGtal::TangencyComputer::space
const KSpace & space() const
Definition: TangencyComputer.h:415
DGtal::CellGeometry< KSpace >
DGtal::TangencyComputer::ShortestPaths::operator=
ShortestPaths & operator=(const ShortestPaths &other)=default
DGtal::TangencyComputer::setUp
void setUp()
Precomputes some neighborhood tables at construction.
DGtal::PointVector< dim, Integer >
DGtal::TangencyComputer::ShortestPaths::infinity
static double infinity()
Definition: TangencyComputer.h:287
DGtal::TangencyComputer::shortestPath
Path shortestPath(Index source, Index target, double secure=sqrt(KSpace::dimension), bool verbose=false) const
DGtal::TangencyComputer::ShortestPaths::Comparator::operator()
bool operator()(const Node &p1, const Node &p2) const
Definition: TangencyComputer.h:104
DGtal::TangencyComputer::shortestPaths
std::vector< Path > shortestPaths(const std::vector< Index > &sources, const std::vector< Index > &targets, double secure=sqrt(KSpace::dimension), bool verbose=false) const
DGtal::TangencyComputer::ShortestPaths::ShortestPaths
ShortestPaths(ConstAlias< TangencyComputer > tgcy_computer, double secure=sqrt(KSpace::dimension))
Definition: TangencyComputer.h:147
DGtal::TangencyComputer::Vector
KSpace::Vector Vector
Definition: TangencyComputer.h:81
DGtal::DigitalConvexity< KSpace >
DGtal::TangencyComputer::length
double length(const Path &path) const
Definition: TangencyComputer.h:446
DGtal::TangencyComputer::Size
std::size_t Size
Definition: TangencyComputer.h:84
Point
MyPointD Point
Definition: testClone2.cpp:383
DGtal::TangencyComputer::operator=
Self & operator=(const Self &other)=default
DGtal::TangencyComputer::ShortestPaths::pathToSource
Path pathToSource(Index i) const
Definition: TangencyComputer.h:297
DGtal::TangencyComputer::ShortestPaths
Definition: TangencyComputer.h:92
DGtal::TangencyComputer::ShortestPaths::getCotangentPoints
std::vector< Index > getCotangentPoints(Index i) const
DGtal::TangencyComputer::ShortestPaths::visitedPoints
const std::vector< bool > & visitedPoints() const
Definition: TangencyComputer.h:323
DGtal::TangencyComputer::ShortestPaths::init
void init(Index i)
Definition: TangencyComputer.h:181