DGtal  0.6.devel
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
MetricAdjacency.ih
1 
30 
31 #include <cstdlib>
32 #include "DGtal/kernel/domains/HyperRectDomain.h"
33 #include <boost/math/special_functions/binomial.hpp>
35 
37 // IMPLEMENTATION of inline methods.
39 #include "DGtal/topology/MetricAdjacency.h"
41 // ----------------------- Standard services ------------------------------
42 
46 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
47 inline
48 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::~MetricAdjacency()
49 {
50 }
51 
56 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
57 inline
58 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::MetricAdjacency()
59 {
60 }
61 
63 // ----------------------- Adjacency services -----------------------------
64 
65 
73 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
74 inline
75 bool
76 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::isAdjacentTo
77 ( const Point & p1, const Point & p2 )
78 {
79  Vector v( p2 - p1 );
80  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= maxNorm1 );
81 }
82 
90 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
91 inline
92 bool
93 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::isProperlyAdjacentTo
94 ( const Point & p1, const Point & p2 )
95 {
96  Vector v( p2 - p1 );
97  if ( v.normInfinity() <= 1 )
98  {
99  typename Vector::UnsignedComponent n1 = v.norm1();
100  return ( n1 <= maxNorm1 ) && ( n1 != 0 );
101  }
102  return false;
103 }
104 
106 // ----------------------- Local graph services -----------------------------
107 
108 
109 
113 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
114 inline
115 typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
116 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::bestCapacity()
117 {
118  static Size myCapacity = computeCapacity();
119  return myCapacity;
120 }
121 
127 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
128 inline
129 typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
130 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::degree
131 ( const Vertex & /* v */ )
132 {
133  return bestCapacity();
134 }
135 
147 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
148 template <typename OutputIterator>
149 inline
150 void
151 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::writeNeighbors
152 ( OutputIterator &it, const Vertex & v )
153 {
154  Point p1( v );
155  for ( typename Point::Iterator iter = p1.begin(); iter != p1.end(); ++iter )
156  --(*iter);
157  Point p2( v );
158  for ( typename Point::Iterator iter = p2.begin(); iter != p2.end(); ++iter )
159  ++(*iter);
160  typedef HyperRectDomain<Space> LocalDomain;
161  LocalDomain domain( p1, p2 );
162  for ( typename LocalDomain::ConstIterator iter = domain.begin();
163  iter != domain.end();
164  ++iter )
165  {
166  Vector vect( v - *iter );
167  typename Vector::UnsignedComponent n1 = vect.norm1();
168  if ( ( n1 <= maxNorm1 ) && ( n1 != 0 ) )
169  *it++ = *iter;
170  }
171 }
172 
189 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
190 template <typename OutputIterator, typename VertexPredicate>
191 void
192 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::writeNeighbors
193 ( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
194 {
195  Point p1( v );
196  for ( typename Point::Iterator iter = p1.begin(); iter != p1.end(); ++iter )
197  --(*iter);
198  Point p2( v );
199  for ( typename Point::Iterator iter = p2.begin(); iter != p2.end(); ++iter )
200  ++(*iter);
201  typedef HyperRectDomain<Space> LocalDomain;
202  LocalDomain domain( p1, p2 );
203  for ( typename LocalDomain::ConstIterator iter = domain.begin();
204  iter != domain.end();
205  ++iter )
206  {
207  Vector vect( v - *iter );
208  typename Vector::UnsignedComponent n1 = vect.norm1();
209  if ( ( n1 <= maxNorm1 ) && ( n1 != 0 ) && (pred(*iter)) )
210  *it++ = *iter;
211  }
212 }
213 
215 // Interface - public :
216 
221 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
222 inline
223 void
224 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::selfDisplay
225 ( std::ostream & out )
226 {
227  out << "[MetricAdjacency Z" << Space::dimension
228  << " n1<=" << maxNorm1 << " ]";
229 }
230 
235 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
236 inline
237 bool
238 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::isValid()
239 {
240  return true;
241 }
242 
243 
244 
246 // Implementation of inline functions //
247 
248 template <typename TSpace, Dimension maxNorm1>
249 inline
250 std::ostream&
251 DGtal::operator<< ( std::ostream & out,
252  const MetricAdjacency<TSpace,maxNorm1,
253  TSpace::dimension> & object )
254 {
255  object.selfDisplay( out );
256  return out;
257 }
258 
259 
261 // Implementation of hidden services //
262 template <typename TSpace, Dimension maxNorm1, Dimension dimension>
263 inline
264 typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
265 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::computeCapacity()
266 {
267  Dimension result = 0;
268  for( Dimension m = dimension - 1; m > dimension - maxNorm1 - 1; m-- )
269  {
270  result += ( (dimension - m) << 1 ) * static_cast<Dimension>( boost::math::binomial_coefficient<float>(dimension, m) );
271  }
272  return result;
273 }
274 
275 // //
277 
278 namespace DGtal {
279 
280  template <typename TSpace>
281  class MetricAdjacency<TSpace, 2, 2>
282  {
283  BOOST_CONCEPT_ASSERT(( CSpace<TSpace> ));
284  // ----------------------- public types ------------------------------
285  public:
286  // Required by CAdjacency
287  typedef TSpace Space;
288  typedef typename Space::Point Point;
289  typedef MetricAdjacency<Space, 2, 2> Adjacency;
290 
291  typedef typename Space::Integer Integer;
292  typedef typename Space::Vector Vector;
293 
294  // Required by CUndirectedSimpleLocalGraph
295  typedef Point Vertex;
296  typedef typename Space::Size Size;
297  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
298  template <typename Value> struct VertexMap {
299  typedef typename std::map<Vertex, Value> Type;
300  };
301 
302  // ----------------------- Standard services ------------------------------
303  public:
304 
305  MetricAdjacency() {}
306  ~MetricAdjacency() {}
307 
308  // ----------------------- Adjacency services -----------------------------
309  public:
310 
311  inline
312  static
313  bool isAdjacentTo( const Point & p1, const Point & p2 )
314  {
315  Vector v( p2 - p1 );
316  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 2 );
317  }
318 
319  inline
320  static
321  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
322  {
323  Vector v( p2 - p1 );
324  if ( v.normInfinity() <= 1 )
325  {
326  typename Vector::UnsignedComponent n1 = v.norm1();
327  return ( n1 <= 2 ) && ( n1 != 0 );
328  }
329  return false;
330  }
331 
332  // ---------------------- Local graph services ----------------------------
333  public:
334 
335  inline
336  static
337  Size bestCapacity()
338  {
339  return 8;
340  }
341 
342  inline
343  static
344  Size
345  degree( const Vertex & /* v */ )
346  {
347  return 8;
348  }
349 
350  template <typename OutputIterator>
351  inline
352  static
353  void writeNeighbors( OutputIterator &it, const Vertex & v )
354  {
355  Integer x = v[ 0 ];
356  Integer y = v[ 1 ];
357  *it++ = Vertex( x-1, y-1 );
358  *it++ = Vertex( x , y-1 );
359  *it++ = Vertex( x+1, y-1 );
360  *it++ = Vertex( x-1, y );
361  *it++ = Vertex( x+1, y );
362  *it++ = Vertex( x-1, y+1 );
363  *it++ = Vertex( x , y+1 );
364  *it++ = Vertex( x+1, y+1 );
365  }
366 
367  template <typename OutputIterator, typename VertexPredicate>
368  inline
369  static
370  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
371  {
372  Vertex q( v[ 0 ] - 1, v[ 1 ] - 1 );
373  if ( pred( q ) ) *it++ = q;
374  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
375  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
376  q[ 0 ] -= 2; ++q[ 1 ];
377  if ( pred( q ) ) *it++ = q;
378  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q;
379  q[ 0 ] -= 2; ++q[ 1 ];
380  if ( pred( q ) ) *it++ = q;
381  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
382  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
383  }
384 
385  // ----------------------- Interface --------------------------------------
386  public:
387 
388  static
389  void selfDisplay ( std::ostream & out )
390  {
391  out << "[MetricAdjacency Z2*"
392  << " n1<=2*" << " ]";
393  }
394 
395  static
396  bool isValid() { return true; }
397 
398  private:
399  MetricAdjacency ( const MetricAdjacency & other );
400  MetricAdjacency & operator= ( const MetricAdjacency & other );
401 
402  // ------------------------- Internals ------------------------------------
403  private:
404 
405  }; // end of class MetricAdjacency
406 
407 
408  template <typename TSpace>
409  class MetricAdjacency<TSpace, 1, 2>
410  {
411  BOOST_CONCEPT_ASSERT(( CSpace<TSpace> ));
412  // ----------------------- public types ------------------------------
413  public:
414  // Required by CAdjacency
415  typedef TSpace Space;
416  typedef typename Space::Point Point;
417  typedef MetricAdjacency<Space, 1, 2> Adjacency;
418 
419  typedef typename Space::Integer Integer;
420  typedef typename Space::Vector Vector;
421 
422  // Required by CUndirectedSimpleLocalGraph
423  typedef Point Vertex;
424  typedef typename Space::Size Size;
425  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
426  template <typename Value> struct VertexMap {
427  typedef typename std::map<Vertex, Value> Type;
428  };
429 
430  // ----------------------- Standard services ------------------------------
431  public:
432 
433  MetricAdjacency() {}
434  ~MetricAdjacency() {}
435 
436  // ----------------------- Adjacency services -----------------------------
437  public:
438 
439  inline
440  static
441  bool isAdjacentTo( const Point & p1, const Point & p2 )
442  {
443  Vector v( p2 - p1 );
444  return ( v.norm1() <= 1 );
445  }
446 
447  inline
448  static
449  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
450  {
451  Vector v( p2 - p1 );
452  return v.norm1() == 1;
453  }
454 
455  // ---------------------- Local graph services ----------------------------
456 
457  inline
458  static
459  Size bestCapacity()
460  {
461  return 4;
462  }
463 
464  inline
465  static
466  Size
467  degree( const Vertex & /* v */ )
468  {
469  return 4;
470  }
471 
472  template <typename OutputIterator>
473  inline
474  static
475  void writeNeighbors( OutputIterator &it, const Vertex & v )
476  {
477  Integer x = v[ 0 ];
478  Integer y = v[ 1 ];
479  *it++ = Vertex( x , y-1 );
480  *it++ = Vertex( x-1, y );
481  *it++ = Vertex( x+1, y );
482  *it++ = Vertex( x , y+1 );
483  }
484 
485  template <typename OutputIterator, typename VertexPredicate>
486  inline
487  static
488  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
489  {
490  Vertex q( v[ 0 ], v[ 1 ] - 1 );
491  if ( pred( q ) ) *it++ = q;
492  --q[ 0 ]; ++q[ 1 ];
493  if ( pred( q ) ) *it++ = q;
494  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q;
495  --q[ 0 ]; ++q[ 1 ];
496  if ( pred( q ) ) *it++ = q;
497  }
498 
499  // ----------------------- Interface --------------------------------------
500  public:
501 
502  static
503  void selfDisplay ( std::ostream & out )
504  {
505  out << "[MetricAdjacency Z2*"
506  << " n1<=2*" << " ]";
507  }
508 
509  static
510  bool isValid() { return true; }
511 
512  private:
513  MetricAdjacency ( const MetricAdjacency & other );
514  MetricAdjacency & operator= ( const MetricAdjacency & other );
515 
516  // ------------------------- Internals ------------------------------------
517  private:
518 
519 
520  }; // end of class MetricAdjacency
521 
523  template <typename TSpace>
524  class MetricAdjacency<TSpace, 3, 3>
525  {
526  BOOST_CONCEPT_ASSERT(( CSpace<TSpace> ));
527  // ----------------------- public types ------------------------------
528  public:
529  // Required by CAdjacency
530  typedef TSpace Space;
531  typedef typename Space::Point Point;
532  typedef MetricAdjacency<Space, 3, 3> Adjacency;
533 
534  typedef typename Space::Integer Integer;
535  typedef typename Space::Vector Vector;
536 
537  // Required by CUndirectedSimpleLocalGraph
538  typedef Point Vertex;
539  typedef typename Space::Size Size;
540  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
541  template <typename Value> struct VertexMap {
542  typedef typename std::map<Vertex, Value> Type;
543  };
544 
545  // ----------------------- Standard services ------------------------------
546  public:
547 
548  MetricAdjacency() {}
549  ~MetricAdjacency() {}
550 
551  // ----------------------- Adjacency services -----------------------------
552  public:
553 
554  inline
555  static
556  bool isAdjacentTo( const Point & p1, const Point & p2 )
557  {
558  Vector v( p2 - p1 );
559  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 3 );
560  }
561 
562  inline
563  static
564  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
565  {
566  Vector v( p2 - p1 );
567  if ( v.normInfinity() <= 1 )
568  {
569  typename Vector::UnsignedComponent n1 = v.norm1();
570  return ( n1 <= 3 ) && ( n1 != 0 );
571  }
572  return false;
573  }
574 
575  // ---------------------- Local graph services ----------------------------
576  public:
577 
578  inline
579  static
580  Size bestCapacity()
581  {
582  return 26;
583  }
584 
585  inline
586  static
587  Size
588  degree( const Vertex & /* v */ )
589  {
590  return 26;
591  }
592 
593  template <typename OutputIterator>
594  inline
595  static
596  void writeNeighbors( OutputIterator &it, const Vertex & v )
597  {
598  Integer x = v[ 0 ];
599  Integer y = v[ 1 ];
600  Integer z = v[ 2 ];
601 
602  *it++ = Vertex( x-1, y-1, z-1 );
603  *it++ = Vertex( x , y-1, z-1 );
604  *it++ = Vertex( x+1, y-1, z-1 );
605  *it++ = Vertex( x-1, y-1, z );
606  *it++ = Vertex( x , y-1, z );
607  *it++ = Vertex( x+1, y-1, z );
608  *it++ = Vertex( x-1, y-1, z+1 );
609  *it++ = Vertex( x , y-1, z+1 );
610  *it++ = Vertex( x+1, y-1, z+1 );
611  *it++ = Vertex( x-1, y , z-1 );
612  *it++ = Vertex( x , y , z-1 );
613  *it++ = Vertex( x+1, y , z-1 );
614  *it++ = Vertex( x-1, y , z );
615  //*it++ = Vertex( x , y , z );
616  *it++ = Vertex( x+1, y , z );
617  *it++ = Vertex( x-1, y , z+1 );
618  *it++ = Vertex( x , y , z+1 );
619  *it++ = Vertex( x+1, y , z+1 );
620  *it++ = Vertex( x-1, y+1, z-1 );
621  *it++ = Vertex( x , y+1, z-1 );
622  *it++ = Vertex( x+1, y+1, z-1 );
623  *it++ = Vertex( x-1, y+1, z );
624  *it++ = Vertex( x , y+1, z );
625  *it++ = Vertex( x+1, y+1, z );
626  *it++ = Vertex( x-1, y+1, z+1 );
627  *it++ = Vertex( x , y+1, z+1 );
628  *it++ = Vertex( x+1, y+1, z+1 );
629  }
630 
631  template <typename OutputIterator, typename VertexPredicate>
632  inline
633  static
634  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
635  {
636  Vertex q( v[ 0 ] - 1, v[ 1 ] - 1, v[ 2 ] - 1 );
637  // z-1
638  if ( pred( q ) ) *it++ = q;
639  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
640  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
641  q[ 0 ] -= 2; ++q[ 1 ];
642  if ( pred( q ) ) *it++ = q;
643  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
644  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
645  q[ 0 ] -= 2; ++q[ 1 ];
646  if ( pred( q ) ) *it++ = q;
647  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
648  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
649  // z
650  q[ 0 ] -= 2; q[ 1 ] -= 2; ++q[ 2 ];
651  if ( pred( q ) ) *it++ = q;
652  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
653  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
654  q[ 0 ] -= 2; ++q[ 1 ];
655  if ( pred( q ) ) *it++ = q;
656  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q; // skip (x,y,z)
657  q[ 0 ] -= 2; ++q[ 1 ];
658  if ( pred( q ) ) *it++ = q;
659  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
660  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
661  // z+1
662  q[ 0 ] -= 2; q[ 1 ] -= 2; ++q[ 2 ];
663  if ( pred( q ) ) *it++ = q;
664  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
665  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
666  q[ 0 ] -= 2; ++q[ 1 ];
667  if ( pred( q ) ) *it++ = q;
668  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
669  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
670  q[ 0 ] -= 2; ++q[ 1 ];
671  if ( pred( q ) ) *it++ = q;
672  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
673  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
674  }
675 
676  // ----------------------- Interface --------------------------------------
677  public:
678 
679  static
680  void selfDisplay ( std::ostream & out )
681  {
682  out << "[MetricAdjacency Z3*"
683  << " n1<=3*" << " ]";
684  }
685 
686  static
687  bool isValid() { return true; }
688 
689  private:
690  MetricAdjacency ( const MetricAdjacency & other );
691  MetricAdjacency & operator= ( const MetricAdjacency & other );
692 
693  // ------------------------- Internals ------------------------------------
694  private:
695 
696  }; // end of class MetricAdjacency
697 
698 
700  template <typename TSpace>
701  class MetricAdjacency<TSpace, 2, 3>
702  {
703  BOOST_CONCEPT_ASSERT(( CSpace<TSpace> ));
704  // ----------------------- public types ------------------------------
705  public:
706  // Required by CAdjacency
707  typedef TSpace Space;
708  typedef typename Space::Point Point;
709  typedef MetricAdjacency<Space, 2, 3> Adjacency;
710 
711  typedef typename Space::Integer Integer;
712  typedef typename Space::Vector Vector;
713 
714  // Required by CUndirectedSimpleLocalGraph
715  typedef Point Vertex;
716  typedef typename Space::Size Size;
717  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
718  template <typename Value> struct VertexMap {
719  typedef typename std::map<Vertex, Value> Type;
720  };
721 
722  // ----------------------- Standard services ------------------------------
723  public:
724 
725  MetricAdjacency() {}
726  ~MetricAdjacency() {}
727 
728  // ----------------------- Adjacency services -----------------------------
729  public:
730 
731  inline
732  static
733  bool isAdjacentTo( const Point & p1, const Point & p2 )
734  {
735  Vector v( p2 - p1 );
736  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 2 );
737  }
738 
739  inline
740  static
741  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
742  {
743  Vector v( p2 - p1 );
744  if ( v.normInfinity() <= 1 )
745  {
746  typename Vector::UnsignedComponent n1 = v.norm1();
747  return ( n1 <= 2 ) && ( n1 != 0 );
748  }
749  return false;
750  }
751 
752  // ---------------------- Local graph services ----------------------------
753  public:
754 
755  inline
756  static
757  Size bestCapacity()
758  {
759  return 18;
760  }
761 
762  inline
763  static
764  Size
765  degree( const Vertex & /* v */ )
766  {
767  return 18;
768  }
769 
770  template <typename OutputIterator>
771  inline
772  static
773  void writeNeighbors( OutputIterator &it, const Vertex & v )
774  {
775  Integer x = v[ 0 ];
776  Integer y = v[ 1 ];
777  Integer z = v[ 2 ];
778 
779  *it++ = Vertex( x , y-1, z-1 );
780  *it++ = Vertex( x-1, y-1, z );
781  *it++ = Vertex( x , y-1, z );
782  *it++ = Vertex( x+1, y-1, z );
783  *it++ = Vertex( x , y-1, z+1 );
784  *it++ = Vertex( x-1, y , z-1 );
785  *it++ = Vertex( x , y , z-1 );
786  *it++ = Vertex( x+1, y , z-1 );
787  *it++ = Vertex( x-1, y , z );
788  //*it++ = Vertex( x , y , z );
789  *it++ = Vertex( x+1, y , z );
790  *it++ = Vertex( x-1, y , z+1 );
791  *it++ = Vertex( x , y , z+1 );
792  *it++ = Vertex( x+1, y , z+1 );
793  *it++ = Vertex( x , y+1, z-1 );
794  *it++ = Vertex( x-1, y+1, z );
795  *it++ = Vertex( x , y+1, z );
796  *it++ = Vertex( x+1, y+1, z );
797  *it++ = Vertex( x , y+1, z+1 );
798  }
799 
800  template <typename OutputIterator, typename VertexPredicate>
801  inline
802  static
803  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
804  {
805  Vertex q( v[ 0 ], v[ 1 ] - 1, v[ 2 ] - 1 );
806  // z-1
807  if ( pred( q ) ) *it++ = q; // x , y-1, z-1
808  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x-1, y , z-1
809  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x , y , z-1
810  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x+1, y , z-1
811  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x , y+1, z-1
812  // z
813  --q[ 0 ], q[ 1 ] -= 2, ++q[ 2 ];
814  if ( pred( q ) ) *it++ = q;
815  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
816  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
817  q[ 0 ] -= 2; ++q[ 1 ];
818  if ( pred( q ) ) *it++ = q;
819  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q; // skip (x,y,z)
820  q[ 0 ] -= 2; ++q[ 1 ];
821  if ( pred( q ) ) *it++ = q;
822  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
823  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
824  // z+1
825  --q[ 0 ], q[ 1 ] -= 2; ++q[ 2 ];
826  if ( pred( q ) ) *it++ = q; // x , y-1, z+1
827  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x-1, y , z+1
828  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x , y , z+1
829  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x+1, y , z+1
830  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x , y+1, z+1
831  }
832 
833  // ----------------------- Interface --------------------------------------
834  public:
835 
836  static
837  void selfDisplay ( std::ostream & out )
838  {
839  out << "[MetricAdjacency Z3*"
840  << " n1<=2*" << " ]";
841  }
842 
843  static
844  bool isValid() { return true; }
845 
846  private:
847  MetricAdjacency ( const MetricAdjacency & other );
848  MetricAdjacency & operator= ( const MetricAdjacency & other );
849 
850  // ------------------------- Internals ------------------------------------
851  private:
852 
853  }; // end of class MetricAdjacency
854 
855 
857  template <typename TSpace>
858  class MetricAdjacency<TSpace, 1, 3>
859  {
860  BOOST_CONCEPT_ASSERT(( CSpace<TSpace> ));
861  // ----------------------- public types ------------------------------
862  public:
863  // Required by CAdjacency
864  typedef TSpace Space;
865  typedef typename Space::Point Point;
866  typedef MetricAdjacency<Space, 1, 3> Adjacency;
867 
868  typedef typename Space::Integer Integer;
869  typedef typename Space::Vector Vector;
870 
871  // Required by CUndirectedSimpleLocalGraph
872  typedef Point Vertex;
873  typedef typename Space::Size Size;
874  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
875  template <typename Value> struct VertexMap {
876  typedef typename std::map<Vertex, Value> Type;
877  };
878 
879  // ----------------------- Standard services ------------------------------
880  public:
881 
882  MetricAdjacency() {}
883  ~MetricAdjacency() {}
884 
885  // ----------------------- Adjacency services -----------------------------
886  public:
887 
888  inline
889  static
890  bool isAdjacentTo( const Point & p1, const Point & p2 )
891  {
892  Vector v( p2 - p1 );
893  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 1 );
894  }
895 
896  inline
897  static
898  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
899  {
900  Vector v( p2 - p1 );
901  if ( v.normInfinity() <= 1 )
902  {
903  typename Vector::UnsignedComponent n1 = v.norm1();
904  return ( n1 == 1 );
905  }
906  return false;
907  }
908 
909  // ---------------------- Local graph services ----------------------------
910  public:
911 
912  inline
913  static
914  Size bestCapacity()
915  {
916  return 6;
917  }
918 
919  inline
920  static
921  Size
922  degree( const Vertex & /* v */ )
923  {
924  return 6;
925  }
926 
927  template <typename OutputIterator>
928  inline
929  static
930  void writeNeighbors( OutputIterator &it, const Vertex & v )
931  {
932  Integer x = v[ 0 ];
933  Integer y = v[ 1 ];
934  Integer z = v[ 2 ];
935 
936  *it++ = Vertex( x , y-1, z );
937  *it++ = Vertex( x , y , z-1 );
938  *it++ = Vertex( x-1, y , z );
939  //*it++ = Vertex( x , y , z );
940  *it++ = Vertex( x+1, y , z );
941  *it++ = Vertex( x , y , z+1 );
942  *it++ = Vertex( x , y+1, z );
943  }
944 
945  template <typename OutputIterator, typename VertexPredicate>
946  inline
947  static
948  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
949  {
950  Vertex q( v[ 0 ], v[ 1 ], v[ 2 ] - 1 );
951  if ( pred( q ) ) *it++ = q; // x , y , z-1
952  q[ 2 ] += 2; if ( pred( q ) ) *it++ = q; // x , y , z+1
953  --q[ 0 ], --q[ 2 ]; if ( pred( q ) ) *it++ = q; // x-1, y , z
954  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q; // x+1, y , z
955  --q[ 0 ], --q[ 1 ]; if ( pred( q ) ) *it++ = q; // x , y-1, z
956  q[ 1 ] += 2; if ( pred( q ) ) *it++ = q; // x , y+1, z
957  }
958 
959  // ----------------------- Interface --------------------------------------
960  public:
961 
962  static
963  void selfDisplay ( std::ostream & out )
964  {
965  out << "[MetricAdjacency Z3*"
966  << " n1<=1*" << " ]";
967  }
968 
969  static
970  bool isValid() { return true; }
971 
972  private:
973  MetricAdjacency ( const MetricAdjacency & other );
974  MetricAdjacency & operator= ( const MetricAdjacency & other );
975 
976  // ------------------------- Internals ------------------------------------
977  private:
978 
979  }; // end of class MetricAdjacency
980 
981 
982 
983 
984 }
985 
Generated on Wed Dec 19 2012 19:10:31 for DGtal by   doxygen 1.8.1.1