DGtal  1.5.beta
NeighborhoodConvexityAnalyzer.h
1 
17 #pragma once
18 
31 #if defined(NeighborhoodConvexityAnalyzer_RECURSES)
32 #error Recursive header files inclusion detected in NeighborhoodConvexityAnalyzer.h
33 #else // defined(NeighborhoodConvexityAnalyzer_RECURSES)
35 #define NeighborhoodConvexityAnalyzer_RECURSES
36 
37 #if !defined NeighborhoodConvexityAnalyzer_h
39 #define NeighborhoodConvexityAnalyzer_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <list>
45 #include <vector>
46 #include <string>
47 #include <bitset>
48 #include <unordered_set>
49 #include "DGtal/base/Common.h"
50 #include "DGtal/base/Clone.h"
51 #include "DGtal/base/ConstExpressions.h"
52 #include "DGtal/base/TimeStampMemoizer.h"
53 #include "DGtal/kernel/CPointPredicate.h"
54 #include "DGtal/kernel/CBoundedNumber.h"
55 #include "DGtal/kernel/domains/HyperRectDomain.h"
56 #include "DGtal/topology/CCellularGridSpaceND.h"
57 #include "DGtal/topology/KhalimskySpaceND.h"
58 #include "DGtal/geometry/volumes/DigitalConvexity.h"
60 
61 namespace DGtal
62 {
63 
65  // template class NeighborhoodConvexityAnalyzer
93  template < typename TKSpace, int K >
95  {
97 
98  public:
100  typedef TKSpace KSpace;
101  typedef typename KSpace::Space Space;
102  typedef typename KSpace::Integer Integer;
103  typedef typename KSpace::Point Point;
104  typedef typename KSpace::Vector Vector;
105  typedef typename KSpace::Cell Cell;
106  typedef std::vector<Point> PointRange;
108  typedef std::size_t Size;
109 
110  static const Dimension dimension = KSpace::dimension;
111  static const Size neigh_size = functions::const_pow( 2*K+1, dimension );
113  static const bool false_positive = ( dimension > 2 ) || ( K > 1 );
114 
115  typedef std::bitset< functions::const_pow( 2*K+1, dimension ) > Configuration;
116  typedef std::bitset< 9 > BasicConfiguration;
117 
118 
119  // ------------------------- Standard services --------------------------------
120  public:
123 
128 
133 
138  NeighborhoodConvexityAnalyzer ( const Self & other ) = default;
139 
147  NeighborhoodConvexityAnalyzer( Clone<KSpace> aKSpace, Size memoizer_size = 0 )
148  : myDigConv( aKSpace ), myMemoizer( memoizer_size )
149  {
150  myDomain = Domain( myDigConv.space().lowerBound(),
151  myDigConv.space().upperBound() );
152  myComputations = 0;
153  myResults = 0;
155  trace.info() << "Size=" << size() << " middle=" << middle << std::endl;
156  }
157 
167  Size memoizer_size = 0 )
168  : myDomain( lo, hi ), myDigConv( lo, hi ), myMemoizer( memoizer_size )
169  {
170  myComputations = 0;
171  myResults = 0;
173  trace.info() << "Size=" << size() << " middle=" << middle << std::endl;
174  }
175 
181  Self & operator= ( const Self & other ) = default;
182 
184  const KSpace& space() const
185  {
186  return myDigConv.space();
187  }
188 
190  const Domain& domain() const
191  {
192  return myDomain;
193  }
194 
196  static int radius()
197  { return K; }
198 
201  static Size size()
202  { return neigh_size; }
203 
205 
206  // -------------------- Neighborhood and convexity services -----------------------
207  public:
210 
221  template < typename PointPredicate >
222  void setCenter( Point c, const PointPredicate& X );
223 
225  Point center() const
226  {
227  return myCenter;
228  }
229 
232  {
233  return myCfgX;
234  }
235 
237  bool isCenterInX() const
238  {
239  return myCenterInX;
240  }
241 
244  {
245  if ( isCenterInX() )
246  return ( myNbInX >= 1 ) // ( ! myLocalX.empty() )
247  && isFullyConvex( true )
248  && isFullyConvex( false );
249  else
250  return ( size() - myNbInX >= 2 ) // ( ! myLocalCompX.empty() )
251  && isComplementaryFullyConvex( true )
252  && isComplementaryFullyConvex( false );
253  }
254 
257  {
258  if ( isCenterInX() )
259  return ( myNbInX >= 1 ) // ( ! myLocalX.empty() )
260  && ! isFullyConvex( true )
261  && isFullyConvex( false )
262  && isComplementaryFullyConvex( true );
263  else
264  return ( size() - myNbInX >= 2 ) // ( ! myLocalCompX.empty() )
265  && ! isComplementaryFullyConvex( true )
266  && isComplementaryFullyConvex( false )
267  && isFullyConvex( true );
268  }
269 
272  {
273  if ( isCenterInX() )
274  return ( myNbInX >= 1 ) // ( ! myLocalX.empty() )
275  && is0Convex( true )
276  && is0Convex( false );
277  else
278  return ( size() - myNbInX >= 2 ) // ( ! myLocalCompX.empty() )
279  && isComplementary0Convex( true )
280  && isComplementary0Convex( false );
281  }
282 
288  bool isFullyConvex( bool with_center )
289  {
290  int mask = with_center
292  if ( myComputations & mask ) return bool( myResults & mask );
293  bool ok;
294  // Check memoizer
295  if ( myMemoizer.isValid() )
296  {
297  auto cfg = makeConfiguration( myCfgX, false, with_center );
298  auto p = myMemoizer.get( cfg );
299  ok = p.first; // may not be correct
300  bool memoized = p.second;
301  if ( ! memoized )
302  {
303  // Need to compute full convexity property
304  ok = checkBasicConfigurationsFullConvexity( false, with_center );
305  if ( ok && false_positive )
306  { // need to do the true computation.
307  std::vector< Point > localX;
308  getLocalX( localX, with_center );
309  ok = myDigConv.isFullyConvex( localX );
310  }
311  myMemoizer.set( cfg, ok );
312  }
313  }
314  else
315  {
316  ok = checkBasicConfigurationsFullConvexity( false, with_center );
317  if ( ok && false_positive )
318  { // need to do the true computation.
319  std::vector< Point > localX;
320  getLocalX( localX, with_center );
321  ok = myDigConv.isFullyConvex( localX );
322  }
323  }
324  // auto cfg = makeConfiguration( myCfgX, false, with_center );
325  // // Check memoizer
326  // if ( myMemoizer.isValid() )
327  // {
328  // auto p = myMemoizer.get( cfg );
329  // ok = p.first; // may not be correct
330  // memoized = p.second;
331  // }
332  // if ( ! memoized )
333  // {
334  // // Need to compute full convexity property
335  // ok = checkBasicConfigurationsFullConvexity( false, with_center );
336  // if ( ok && false_positive )
337  // { // need to do the true computation.
338  // std::vector< Point > localX;
339  // getLocalX( localX, with_center );
340  // ok = myDigConv.isFullyConvex( localX );
341  // }
342  // if ( myMemoizer.isValid() )
343  // myMemoizer.set( cfg, ok );
344  // }
345  myComputations |= mask;
346  if ( ok ) myResults |= mask;
347  return ok;
348  }
349 
355  bool isComplementaryFullyConvex( bool with_center )
356  {
357  int mask = with_center
359  if ( myComputations & mask ) return bool( myResults & mask );
360  bool ok;
361  // Check memoizer
362  if ( myMemoizer.isValid() )
363  {
364  auto cfg = makeConfiguration( myCfgX, true, with_center );
365  auto p = myMemoizer.get( cfg );
366  ok = p.first; // may not be correct
367  bool memoized = p.second;
368  if ( ! memoized )
369  {
370  // Need to compute full convexity property
371  ok = checkBasicConfigurationsFullConvexity( true, with_center );
372  if ( ok && false_positive )
373  { // need to do the true computation.
374  std::vector< Point > localCompX;
375  getLocalCompX( localCompX, with_center );
376  ok = myDigConv.isFullyConvex( localCompX );
377  }
378  myMemoizer.set( cfg, ok );
379  }
380  }
381  else
382  {
383  // Need to compute full convexity property
384  ok = checkBasicConfigurationsFullConvexity( true, with_center );
385  if ( ok && false_positive )
386  { // need to do the true computation.
387  std::vector< Point > localCompX;
388  getLocalCompX( localCompX, with_center );
389  ok = myDigConv.isFullyConvex( localCompX );
390  }
391  }
392  // bool memoized = false;
393  // auto cfg = makeConfiguration( myCfgX, true, with_center );
394  // // Check memoizer
395  // if ( myMemoizer.isValid() )
396  // {
397  // auto p = myMemoizer.get( cfg );
398  // ok = p.first; // may not be correct
399  // memoized = p.second;
400  // }
401  // if ( ! memoized )
402  // {
403  // // Need to compute full convexity property
404  // ok = checkBasicConfigurationsFullConvexity( true, with_center );
405  // if ( ok && false_positive )
406  // { // need to do the true computation.
407  // std::vector< Point > localCompX;
408  // getLocalCompX( localCompX, with_center );
409  // ok = myDigConv.isFullyConvex( localCompX );
410  // }
411  // if ( myMemoizer.isValid() )
412  // myMemoizer.set( cfg, ok );
413  // }
414  myComputations |= mask;
415  if ( ok ) myResults |= mask;
416  return ok;
417  }
418 
424  bool is0Convex( bool with_center )
425  {
426  int mask = with_center
428  if ( myComputations & mask ) return bool( myResults & mask );
429  // Need to compute full convexity property
430  bool ok = checkBasicConfigurations0Convexity( false, with_center );
431  if ( ok && false_positive )
432  { // need to do the true computation.
433  std::vector< Point > localX;
434  getLocalX( localX, with_center );
435  ok = myDigConv.is0Convex( localX );
436  }
437  myComputations |= mask;
438  if ( ok ) myResults |= mask;
439  return ok;
440  }
441 
447  bool isComplementary0Convex( bool with_center )
448  {
449  int mask = with_center
451  if ( myComputations & mask ) return bool( myResults & mask );
452  // Need to compute full convexity property
453  bool ok = checkBasicConfigurations0Convexity( true, with_center );
454  if ( ok && false_positive )
455  { // need to do the true computation.
456  std::vector< Point > localCompX;
457  getLocalCompX( localCompX, with_center );
458  ok = myDigConv.is0Convex( localCompX );
459  }
460  myComputations |= mask;
461  if ( ok ) myResults |= mask;
462  return ok;
463  }
464 
474  bool complement, bool with_center )
475  {
476  if ( complement )
477  {
478  current.flip(); // current = ~current;
479  if ( ! with_center ) current.reset( middle );
480  else current.set( middle );
481  }
482  else
483  {
484  if ( with_center ) current.set( middle );
485  }
486  return current;
487  }
488 
493  void getLocalX( std::vector< Point >& localX, bool with_center ) const;
494 
499  void getLocalCompX( std::vector< Point >& localCompX, bool with_center ) const;
500 
502 
503  // ------------------------- Protected Datas ------------------------------
504  protected:
520  std::vector< BasicConfiguration > myBasicCfgX;
521 
523  std::bitset< 512 > myBasicFullConvexityTable;
525  std::bitset< 512 > myBasic0ConvexityTable;
526 
528  enum Computation {
537  };
542 
543  // ------------------------- Private Datas --------------------------------
544  private:
545 
546  // ------------------------- Internals ------------------------------------
547  private:
551 
560  ( bool compX, bool with_center ) const;
561 
570  ( bool compX, bool with_center ) const;
571 
580  ( Configuration cfg, std::vector< BasicConfiguration > & result ) const;
581 
592  ( Configuration cfg, Dimension i, Dimension j ) const;
593 
594 
595  }; // end of class NeighborhoodConvexityAnalyzer
596 
597 
598 } // namespace DGtal
599 
600 
602 // Includes inline functions.
603 #include "NeighborhoodConvexityAnalyzer.ih"
604 
605 // //
607 
608 #endif // !defined NeighborhoodConvexityAnalyzer_h
609 
610 #undef NeighborhoodConvexityAnalyzer_RECURSES
611 #endif // else defined(NeighborhoodConvexityAnalyzer_RECURSES)
Aim: This class encapsulates its parameter class to indicate that the given parameter is required to ...
Definition: Clone.h:267
bool isFullyConvex(const PointRange &X, bool convex0=false) const
bool is0Convex(const PointRange &X) const
const KSpace & space() const
TInteger Integer
Arithmetic ring induced by (+,-,*) and Integer numbers.
Aim: A class that models a neighborhood and that provides services to analyse the convexity properti...
Computation
Enum types indicating the possible type of local computations.
NeighborhoodConvexityAnalyzer(Clone< KSpace > aKSpace, Size memoizer_size=0)
BOOST_CONCEPT_ASSERT((concepts::CCellularGridSpaceND< TKSpace >))
static Configuration makeConfiguration(Configuration current, bool complement, bool with_center)
std::bitset< 512 > myBasicFullConvexityTable
Stores the full convexity property of the basic 3x3 neighborhood configurations.
NeighborhoodConvexityAnalyzer(Point lo, Point hi, Size memoizer_size=0)
int myComputations
Stores which properties have already been computed.
Self & operator=(const Self &other)=default
Domain myDomain
The bounded domain in which computations are carried out.
std::bitset< functions::const_pow(2 *K+1, dimension) > Configuration
void setCenter(Point c, const PointPredicate &X)
int myResults
Stores the properties boolean values.
bool checkBasicConfigurations0Convexity(bool compX, bool with_center) const
DigitalConvexity< KSpace > myDigConv
The digital convexity that is used for checking full convexity.
bool checkBasicConfigurationsFullConvexity(bool compX, bool with_center) const
bool myCenterInX
tells if the center belongs to X
void getLocalCompX(std::vector< Point > &localCompX, bool with_center) const
Size myNbInX
The number of points of the neighborhood that belongs to X (center omitted).
Configuration myCfgX
Stores the local configuration for X (without the center)
TimeStampMemoizer< Configuration, bool > myMemoizer
The memoizer.
std::bitset< 512 > myBasic0ConvexityTable
Stores the 0-convexity property of the basic 3x3 neighborhood configurations.
void getLocalX(std::vector< Point > &localX, bool with_center) const
bool isCenterInX() const
Tells if the current center belongs to the shape X.
Point myCenter
The current center of the neighborhood.
NeighborhoodConvexityAnalyzer< TKSpace, K > Self
void computeBasicConfigurations(Configuration cfg, std::vector< BasicConfiguration > &result) const
std::vector< BasicConfiguration > myBasicCfgX
Stores the basic local configurations associated to myCfgX, for speed-up.
BasicConfiguration computeCentralBasicConfiguration(Configuration cfg, Dimension i, Dimension j) const
NeighborhoodConvexityAnalyzer(const Self &other)=default
std::pair< Value, bool > get(const Key &key)
void set(const Key &key, const Value &value)
std::ostream & info()
constexpr T const_pow(T b, unsigned int e)
constexpr T const_middle(T K, unsigned int e)
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::uint32_t Dimension
Definition: Common.h:136
Trace trace
Definition: Common.h:153
Aim: This concept describes a cellular grid space in nD. In these spaces obtained by cartesian produc...
KSpace K