DGtal  1.1.0
MetricAdjacency.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file MetricAdjacency.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
21  *
22  * @date 2010/07/04
23  *
24  * Implementation of inline methods defined in MetricAdjacency.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 #include "DGtal/kernel/domains/HyperRectDomain.h"
33 #include <boost/math/special_functions/binomial.hpp>
34 //////////////////////////////////////////////////////////////////////////////
35 
36 ///////////////////////////////////////////////////////////////////////////////
37 // IMPLEMENTATION of inline methods.
38 ///////////////////////////////////////////////////////////////////////////////
39 #include "DGtal/topology/MetricAdjacency.h"
40 ///////////////////////////////////////////////////////////////////////////////
41 // ----------------------- Standard services ------------------------------
42 
43 /**
44  * Destructor.
45  */
46 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
47 inline
48 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::~MetricAdjacency()
49 {
50 }
51 
52 /**
53  * Constructor. Does nothing. Due to the symmetry and translation
54  * invariance of this digital topology, all methods are static.
55  */
56 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
57 inline
58 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::MetricAdjacency()
59 {
60 }
61 
62 ///////////////////////////////////////////////////////////////////////////////
63 // ----------------------- Adjacency services -----------------------------
64 
65 
66 /**
67  * @param p1 any point in this space.
68  * @param p2 any point in this space.
69  *
70  * @return 'true' iff p1 is adjacent to p2 according to this
71  * adjacency relation.
72  */
73 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::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 
83 /**
84  * @param p1 any point in this space.
85  * @param p2 any point in this space.
86  *
87  * @return 'true' iff p1 is adjacent to p2 according to this
88  * adjacency relation and p1 != p2.
89  */
90 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::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 
105 ///////////////////////////////////////////////////////////////////////////////
106 // ----------------------- Local graph services -----------------------------
107 
108 
109 
110 /**
111  * @return maximum number of neighbors for this adjacency
112  */
113 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::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 
122 /**
123  *
124  * @return the number of neighbors of this vertex
125  */
126 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
127 inline
128 typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
129 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::degree
130 ( const Vertex & /* v */ )
131 {
132  return bestCapacity();
133 }
134 
135 /**
136  * Writes the neighbors of a vertex using an output iterator
137  *
138  *
139  * @tparam OutputIterator the type of an output iterator writing
140  * in a container of vertices.
141  *
142  * @param it the output iterator
143  *
144  * @param v the vertex whose neighbors will be written
145  */
146 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
147 template <typename OutputIterator>
148 inline
149 void
150 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::writeNeighbors
151 ( OutputIterator &it, const Vertex & v )
152 {
153  Point p1( v );
154  for ( typename Point::Iterator iter = p1.begin(); iter != p1.end(); ++iter )
155  --(*iter);
156  Point p2( v );
157  for ( typename Point::Iterator iter = p2.begin(); iter != p2.end(); ++iter )
158  ++(*iter);
159  typedef HyperRectDomain<Space> LocalDomain;
160  LocalDomain domain( p1, p2 );
161  for ( typename LocalDomain::ConstIterator iter = domain.begin();
162  iter != domain.end();
163  ++iter )
164  {
165  Vector vect( v - *iter );
166  typename Vector::UnsignedComponent n1 = vect.norm1();
167  if ( ( n1 <= maxNorm1 ) && ( n1 != 0 ) )
168  *it++ = *iter;
169  }
170 }
171 
172 /**
173  * Writes the neighbors of a vertex which satisfy a predicate using an
174  * output iterator
175  *
176  *
177  * @tparam OutputIterator the type of an output iterator writing
178  * in a container of vertices.
179  *
180  * @tparam VertexPredicate the type of the predicate
181  *
182  * @param it the output iterator
183  *
184  * @param v the vertex whose neighbors will be written
185  *
186  * @param pred the predicate that must be satisfied
187  */
188 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
189 template <typename OutputIterator, typename VertexPredicate>
190 void
191 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::writeNeighbors
192 ( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
193 {
194  Point p1( v );
195  for ( typename Point::Iterator iter = p1.begin(); iter != p1.end(); ++iter )
196  --(*iter);
197  Point p2( v );
198  for ( typename Point::Iterator iter = p2.begin(); iter != p2.end(); ++iter )
199  ++(*iter);
200  typedef HyperRectDomain<Space> LocalDomain;
201  LocalDomain domain( p1, p2 );
202  for ( typename LocalDomain::ConstIterator iter = domain.begin();
203  iter != domain.end();
204  ++iter )
205  {
206  Vector vect( v - *iter );
207  typename Vector::UnsignedComponent n1 = vect.norm1();
208  if ( ( n1 <= maxNorm1 ) && ( n1 != 0 ) && (pred(*iter)) )
209  *it++ = *iter;
210  }
211 }
212 
213 ///////////////////////////////////////////////////////////////////////////////
214 // Interface - public :
215 
216 /**
217  * Writes/Displays the object on an output stream.
218  * @param out the output stream where the object is written.
219  */
220 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
221 inline
222 void
223 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::selfDisplay
224 ( std::ostream & out )
225 {
226  out << "[MetricAdjacency Z" << Space::dimension
227  << " n1<=" << maxNorm1 << " ]";
228 }
229 
230 /**
231  * Checks the validity/consistency of the object.
232  * @return 'true' if the object is valid, 'false' otherwise.
233  */
234 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
235 inline
236 bool
237 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::isValid()
238 {
239  return true;
240 }
241 
242 
243 
244 ///////////////////////////////////////////////////////////////////////////////
245 // Implementation of inline functions //
246 
247 template <typename TSpace, DGtal::Dimension maxNorm1>
248 inline
249 std::ostream&
250 DGtal::operator<< ( std::ostream & out,
251  const MetricAdjacency<TSpace,maxNorm1,
252  TSpace::dimension> & object )
253 {
254  object.selfDisplay( out );
255  return out;
256 }
257 
258 
259 ///////////////////////////////////////////////////////////////////////////////
260 // Implementation of hidden services //
261 template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
262 inline
263 typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
264 DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::computeCapacity()
265 {
266  DGtal::Dimension result = 0;
267  for( DGtal::Dimension m = dimension - 1; m > dimension - maxNorm1 - 1; m-- )
268  {
269  result += ( (dimension - m) << 1 ) * static_cast<DGtal::Dimension>( boost::math::binomial_coefficient<float>(dimension, m) );
270  }
271  return result;
272 }
273 
274 // //
275 ///////////////////////////////////////////////////////////////////////////////
276 
277 namespace DGtal {
278 
279  template <typename TSpace>
280  class MetricAdjacency<TSpace, 2, 2>
281  {
282  BOOST_CONCEPT_ASSERT(( concepts::CSpace<TSpace> ));
283  // ----------------------- public types ------------------------------
284  public:
285  // Required by CAdjacency
286  typedef TSpace Space;
287  typedef typename Space::Point Point;
288  typedef MetricAdjacency<Space, 2, 2> Adjacency;
289 
290  typedef typename Space::Integer Integer;
291  typedef typename Space::Vector Vector;
292 
293  // Required by CUndirectedSimpleLocalGraph
294  typedef Point Vertex;
295  typedef typename Space::Size Size;
296  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
297  template <typename Value> struct VertexMap {
298  typedef typename std::map<Vertex, Value> Type;
299  };
300 
301  // ----------------------- Standard services ------------------------------
302  public:
303 
304  MetricAdjacency() {}
305  ~MetricAdjacency() {}
306 
307  // ----------------------- Adjacency services -----------------------------
308  public:
309 
310  inline
311  static
312  bool isAdjacentTo( const Point & p1, const Point & p2 )
313  {
314  Vector v( p2 - p1 );
315  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 2 );
316  }
317 
318  inline
319  static
320  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
321  {
322  Vector v( p2 - p1 );
323  if ( v.normInfinity() <= 1 )
324  {
325  typename Vector::UnsignedComponent n1 = v.norm1();
326  return ( n1 <= 2 ) && ( n1 != 0 );
327  }
328  return false;
329  }
330 
331  // ---------------------- Local graph services ----------------------------
332  public:
333 
334  inline
335  static
336  Size bestCapacity()
337  {
338  return 8;
339  }
340 
341  inline
342  static
343  Size
344  degree( const Vertex & /* v */ )
345  {
346  return 8;
347  }
348 
349  template <typename OutputIterator>
350  inline
351  static
352  void writeNeighbors( OutputIterator &it, const Vertex & v )
353  {
354  Integer x = v[ 0 ];
355  Integer y = v[ 1 ];
356  *it++ = Vertex( x-1, y-1 );
357  *it++ = Vertex( x , y-1 );
358  *it++ = Vertex( x+1, y-1 );
359  *it++ = Vertex( x-1, y );
360  *it++ = Vertex( x+1, y );
361  *it++ = Vertex( x-1, y+1 );
362  *it++ = Vertex( x , y+1 );
363  *it++ = Vertex( x+1, y+1 );
364  }
365 
366  template <typename OutputIterator, typename VertexPredicate>
367  inline
368  static
369  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
370  {
371  Vertex q( v[ 0 ] - 1, v[ 1 ] - 1 );
372  if ( pred( q ) ) *it++ = q;
373  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
374  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
375  q[ 0 ] -= 2; ++q[ 1 ];
376  if ( pred( q ) ) *it++ = q;
377  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q;
378  q[ 0 ] -= 2; ++q[ 1 ];
379  if ( pred( q ) ) *it++ = q;
380  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
381  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
382  }
383 
384  // ----------------------- Interface --------------------------------------
385  public:
386 
387  static
388  void selfDisplay ( std::ostream & out )
389  {
390  out << "[MetricAdjacency Z2*"
391  << " n1<=2*" << " ]";
392  }
393 
394  static
395  bool isValid() { return true; }
396 
397  private:
398  MetricAdjacency ( const MetricAdjacency & other );
399  MetricAdjacency & operator= ( const MetricAdjacency & other );
400 
401  // ------------------------- Internals ------------------------------------
402  private:
403 
404  }; // end of class MetricAdjacency
405 
406 
407  template <typename TSpace>
408  class MetricAdjacency<TSpace, 1, 2>
409  {
410  BOOST_CONCEPT_ASSERT(( concepts::CSpace<TSpace> ));
411  // ----------------------- public types ------------------------------
412  public:
413  // Required by CAdjacency
414  typedef TSpace Space;
415  typedef typename Space::Point Point;
416  typedef MetricAdjacency<Space, 1, 2> Adjacency;
417 
418  typedef typename Space::Integer Integer;
419  typedef typename Space::Vector Vector;
420 
421  // Required by CUndirectedSimpleLocalGraph
422  typedef Point Vertex;
423  typedef typename Space::Size Size;
424  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
425  template <typename Value> struct VertexMap {
426  typedef typename std::map<Vertex, Value> Type;
427  };
428 
429  // ----------------------- Standard services ------------------------------
430  public:
431 
432  MetricAdjacency() {}
433  ~MetricAdjacency() {}
434 
435  // ----------------------- Adjacency services -----------------------------
436  public:
437 
438  inline
439  static
440  bool isAdjacentTo( const Point & p1, const Point & p2 )
441  {
442  Vector v( p2 - p1 );
443  return ( v.norm1() <= 1 );
444  }
445 
446  inline
447  static
448  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
449  {
450  Vector v( p2 - p1 );
451  return v.norm1() == 1;
452  }
453 
454  // ---------------------- Local graph services ----------------------------
455 
456  inline
457  static
458  Size bestCapacity()
459  {
460  return 4;
461  }
462 
463  inline
464  static
465  Size
466  degree( const Vertex & /* v */ )
467  {
468  return 4;
469  }
470 
471  template <typename OutputIterator>
472  inline
473  static
474  void writeNeighbors( OutputIterator &it, const Vertex & v )
475  {
476  Integer x = v[ 0 ];
477  Integer y = v[ 1 ];
478  *it++ = Vertex( x , y-1 );
479  *it++ = Vertex( x-1, y );
480  *it++ = Vertex( x+1, y );
481  *it++ = Vertex( x , y+1 );
482  }
483 
484  template <typename OutputIterator, typename VertexPredicate>
485  inline
486  static
487  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
488  {
489  Vertex q( v[ 0 ], v[ 1 ] - 1 );
490  if ( pred( q ) ) *it++ = q;
491  --q[ 0 ]; ++q[ 1 ];
492  if ( pred( q ) ) *it++ = q;
493  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q;
494  --q[ 0 ]; ++q[ 1 ];
495  if ( pred( q ) ) *it++ = q;
496  }
497 
498  // ----------------------- Interface --------------------------------------
499  public:
500 
501  static
502  void selfDisplay ( std::ostream & out )
503  {
504  out << "[MetricAdjacency Z2*"
505  << " n1<=2*" << " ]";
506  }
507 
508  static
509  bool isValid() { return true; }
510 
511  private:
512  MetricAdjacency ( const MetricAdjacency & other );
513  MetricAdjacency & operator= ( const MetricAdjacency & other );
514 
515  // ------------------------- Internals ------------------------------------
516  private:
517 
518 
519  }; // end of class MetricAdjacency
520 
521  /** Specialize 26-adjacency. */
522  template <typename TSpace>
523  class MetricAdjacency<TSpace, 3, 3>
524  {
525  BOOST_CONCEPT_ASSERT(( concepts::CSpace<TSpace> ));
526  // ----------------------- public types ------------------------------
527  public:
528  // Required by CAdjacency
529  typedef TSpace Space;
530  typedef typename Space::Point Point;
531  typedef MetricAdjacency<Space, 3, 3> Adjacency;
532 
533  typedef typename Space::Integer Integer;
534  typedef typename Space::Vector Vector;
535 
536  // Required by CUndirectedSimpleLocalGraph
537  typedef Point Vertex;
538  typedef typename Space::Size Size;
539  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
540  template <typename Value> struct VertexMap {
541  typedef typename std::map<Vertex, Value> Type;
542  };
543 
544  // ----------------------- Standard services ------------------------------
545  public:
546 
547  MetricAdjacency() {}
548  ~MetricAdjacency() {}
549 
550  // ----------------------- Adjacency services -----------------------------
551  public:
552 
553  inline
554  static
555  bool isAdjacentTo( const Point & p1, const Point & p2 )
556  {
557  Vector v( p2 - p1 );
558  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 3 );
559  }
560 
561  inline
562  static
563  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
564  {
565  Vector v( p2 - p1 );
566  if ( v.normInfinity() <= 1 )
567  {
568  typename Vector::UnsignedComponent n1 = v.norm1();
569  return ( n1 <= 3 ) && ( n1 != 0 );
570  }
571  return false;
572  }
573 
574  // ---------------------- Local graph services ----------------------------
575  public:
576 
577  inline
578  static
579  Size bestCapacity()
580  {
581  return 26;
582  }
583 
584  inline
585  static
586  Size
587  degree( const Vertex & /* v */ )
588  {
589  return 26;
590  }
591 
592  template <typename OutputIterator>
593  inline
594  static
595  void writeNeighbors( OutputIterator &it, const Vertex & v )
596  {
597  Integer x = v[ 0 ];
598  Integer y = v[ 1 ];
599  Integer z = v[ 2 ];
600 
601  *it++ = Vertex( x-1, y-1, z-1 );
602  *it++ = Vertex( x , y-1, z-1 );
603  *it++ = Vertex( x+1, y-1, z-1 );
604  *it++ = Vertex( x-1, y-1, z );
605  *it++ = Vertex( x , y-1, z );
606  *it++ = Vertex( x+1, y-1, z );
607  *it++ = Vertex( x-1, y-1, z+1 );
608  *it++ = Vertex( x , y-1, z+1 );
609  *it++ = Vertex( x+1, y-1, z+1 );
610  *it++ = Vertex( x-1, y , z-1 );
611  *it++ = Vertex( x , y , z-1 );
612  *it++ = Vertex( x+1, y , z-1 );
613  *it++ = Vertex( x-1, y , z );
614  //*it++ = Vertex( x , y , z );
615  *it++ = Vertex( x+1, y , z );
616  *it++ = Vertex( x-1, y , z+1 );
617  *it++ = Vertex( x , y , z+1 );
618  *it++ = Vertex( x+1, y , z+1 );
619  *it++ = Vertex( x-1, y+1, z-1 );
620  *it++ = Vertex( x , y+1, z-1 );
621  *it++ = Vertex( x+1, y+1, z-1 );
622  *it++ = Vertex( x-1, y+1, z );
623  *it++ = Vertex( x , y+1, z );
624  *it++ = Vertex( x+1, y+1, z );
625  *it++ = Vertex( x-1, y+1, z+1 );
626  *it++ = Vertex( x , y+1, z+1 );
627  *it++ = Vertex( x+1, y+1, z+1 );
628  }
629 
630  template <typename OutputIterator, typename VertexPredicate>
631  inline
632  static
633  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
634  {
635  Vertex q( v[ 0 ] - 1, v[ 1 ] - 1, v[ 2 ] - 1 );
636  // z-1
637  if ( pred( q ) ) *it++ = q;
638  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
639  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
640  q[ 0 ] -= 2; ++q[ 1 ];
641  if ( pred( q ) ) *it++ = q;
642  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
643  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
644  q[ 0 ] -= 2; ++q[ 1 ];
645  if ( pred( q ) ) *it++ = q;
646  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
647  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
648  // z
649  q[ 0 ] -= 2; q[ 1 ] -= 2; ++q[ 2 ];
650  if ( pred( q ) ) *it++ = q;
651  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
652  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
653  q[ 0 ] -= 2; ++q[ 1 ];
654  if ( pred( q ) ) *it++ = q;
655  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q; // skip (x,y,z)
656  q[ 0 ] -= 2; ++q[ 1 ];
657  if ( pred( q ) ) *it++ = q;
658  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
659  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
660  // z+1
661  q[ 0 ] -= 2; q[ 1 ] -= 2; ++q[ 2 ];
662  if ( pred( q ) ) *it++ = q;
663  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
664  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
665  q[ 0 ] -= 2; ++q[ 1 ];
666  if ( pred( q ) ) *it++ = q;
667  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
668  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
669  q[ 0 ] -= 2; ++q[ 1 ];
670  if ( pred( q ) ) *it++ = q;
671  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
672  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
673  }
674 
675  // ----------------------- Interface --------------------------------------
676  public:
677 
678  static
679  void selfDisplay ( std::ostream & out )
680  {
681  out << "[MetricAdjacency Z3*"
682  << " n1<=3*" << " ]";
683  }
684 
685  static
686  bool isValid() { return true; }
687 
688  private:
689  MetricAdjacency ( const MetricAdjacency & other );
690  MetricAdjacency & operator= ( const MetricAdjacency & other );
691 
692  // ------------------------- Internals ------------------------------------
693  private:
694 
695  }; // end of class MetricAdjacency
696 
697 
698  /** Specialize 18-adjacency. */
699  template <typename TSpace>
700  class MetricAdjacency<TSpace, 2, 3>
701  {
702  BOOST_CONCEPT_ASSERT(( concepts::CSpace<TSpace> ));
703  // ----------------------- public types ------------------------------
704  public:
705  // Required by CAdjacency
706  typedef TSpace Space;
707  typedef typename Space::Point Point;
708  typedef MetricAdjacency<Space, 2, 3> Adjacency;
709 
710  typedef typename Space::Integer Integer;
711  typedef typename Space::Vector Vector;
712 
713  // Required by CUndirectedSimpleLocalGraph
714  typedef Point Vertex;
715  typedef typename Space::Size Size;
716  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
717  template <typename Value> struct VertexMap {
718  typedef typename std::map<Vertex, Value> Type;
719  };
720 
721  // ----------------------- Standard services ------------------------------
722  public:
723 
724  MetricAdjacency() {}
725  ~MetricAdjacency() {}
726 
727  // ----------------------- Adjacency services -----------------------------
728  public:
729 
730  inline
731  static
732  bool isAdjacentTo( const Point & p1, const Point & p2 )
733  {
734  Vector v( p2 - p1 );
735  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 2 );
736  }
737 
738  inline
739  static
740  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
741  {
742  Vector v( p2 - p1 );
743  if ( v.normInfinity() <= 1 )
744  {
745  typename Vector::UnsignedComponent n1 = v.norm1();
746  return ( n1 <= 2 ) && ( n1 != 0 );
747  }
748  return false;
749  }
750 
751  // ---------------------- Local graph services ----------------------------
752  public:
753 
754  inline
755  static
756  Size bestCapacity()
757  {
758  return 18;
759  }
760 
761  inline
762  static
763  Size
764  degree( const Vertex & /* v */ )
765  {
766  return 18;
767  }
768 
769  template <typename OutputIterator>
770  inline
771  static
772  void writeNeighbors( OutputIterator &it, const Vertex & v )
773  {
774  Integer x = v[ 0 ];
775  Integer y = v[ 1 ];
776  Integer z = v[ 2 ];
777 
778  *it++ = Vertex( x , y-1, z-1 );
779  *it++ = Vertex( x-1, y-1, z );
780  *it++ = Vertex( x , y-1, z );
781  *it++ = Vertex( x+1, y-1, z );
782  *it++ = Vertex( x , y-1, z+1 );
783  *it++ = Vertex( x-1, y , z-1 );
784  *it++ = Vertex( x , y , z-1 );
785  *it++ = Vertex( x+1, y , z-1 );
786  *it++ = Vertex( x-1, y , z );
787  //*it++ = Vertex( x , y , z );
788  *it++ = Vertex( x+1, y , z );
789  *it++ = Vertex( x-1, y , z+1 );
790  *it++ = Vertex( x , y , z+1 );
791  *it++ = Vertex( x+1, y , z+1 );
792  *it++ = Vertex( x , y+1, z-1 );
793  *it++ = Vertex( x-1, y+1, z );
794  *it++ = Vertex( x , y+1, z );
795  *it++ = Vertex( x+1, y+1, z );
796  *it++ = Vertex( x , y+1, z+1 );
797  }
798 
799  template <typename OutputIterator, typename VertexPredicate>
800  inline
801  static
802  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
803  {
804  Vertex q( v[ 0 ], v[ 1 ] - 1, v[ 2 ] - 1 );
805  // z-1
806  if ( pred( q ) ) *it++ = q; // x , y-1, z-1
807  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x-1, y , z-1
808  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x , y , z-1
809  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x+1, y , z-1
810  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x , y+1, z-1
811  // z
812  --q[ 0 ], q[ 1 ] -= 2, ++q[ 2 ];
813  if ( pred( q ) ) *it++ = q;
814  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
815  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
816  q[ 0 ] -= 2; ++q[ 1 ];
817  if ( pred( q ) ) *it++ = q;
818  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q; // skip (x,y,z)
819  q[ 0 ] -= 2; ++q[ 1 ];
820  if ( pred( q ) ) *it++ = q;
821  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
822  ++q[ 0 ]; if ( pred( q ) ) *it++ = q;
823  // z+1
824  --q[ 0 ], q[ 1 ] -= 2; ++q[ 2 ];
825  if ( pred( q ) ) *it++ = q; // x , y-1, z+1
826  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x-1, y , z+1
827  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x , y , z+1
828  ++q[ 0 ]; if ( pred( q ) ) *it++ = q; // x+1, y , z+1
829  --q[ 0 ], ++q[ 1 ]; if ( pred( q ) ) *it++ = q; // x , y+1, z+1
830  }
831 
832  // ----------------------- Interface --------------------------------------
833  public:
834 
835  static
836  void selfDisplay ( std::ostream & out )
837  {
838  out << "[MetricAdjacency Z3*"
839  << " n1<=2*" << " ]";
840  }
841 
842  static
843  bool isValid() { return true; }
844 
845  private:
846  MetricAdjacency ( const MetricAdjacency & other );
847  MetricAdjacency & operator= ( const MetricAdjacency & other );
848 
849  // ------------------------- Internals ------------------------------------
850  private:
851 
852  }; // end of class MetricAdjacency
853 
854 
855  /** Specialize 6-adjacency. */
856  template <typename TSpace>
857  class MetricAdjacency<TSpace, 1, 3>
858  {
859  BOOST_CONCEPT_ASSERT(( concepts::CSpace<TSpace> ));
860  // ----------------------- public types ------------------------------
861  public:
862  // Required by CAdjacency
863  typedef TSpace Space;
864  typedef typename Space::Point Point;
865  typedef MetricAdjacency<Space, 1, 3> Adjacency;
866 
867  typedef typename Space::Integer Integer;
868  typedef typename Space::Vector Vector;
869 
870  // Required by CUndirectedSimpleLocalGraph
871  typedef Point Vertex;
872  typedef typename Space::Size Size;
873  typedef std::set<Vertex> VertexSet; // DigitalSet doesn't seem to fit (MetricAdjacency has no domain)
874  template <typename Value> struct VertexMap {
875  typedef typename std::map<Vertex, Value> Type;
876  };
877 
878  // ----------------------- Standard services ------------------------------
879  public:
880 
881  MetricAdjacency() {}
882  ~MetricAdjacency() {}
883 
884  // ----------------------- Adjacency services -----------------------------
885  public:
886 
887  inline
888  static
889  bool isAdjacentTo( const Point & p1, const Point & p2 )
890  {
891  Vector v( p2 - p1 );
892  return ( v.normInfinity() <= 1 ) && ( v.norm1() <= 1 );
893  }
894 
895  inline
896  static
897  bool isProperlyAdjacentTo( const Point & p1, const Point & p2 )
898  {
899  Vector v( p2 - p1 );
900  if ( v.normInfinity() <= 1 )
901  {
902  typename Vector::UnsignedComponent n1 = v.norm1();
903  return ( n1 == 1 );
904  }
905  return false;
906  }
907 
908  // ---------------------- Local graph services ----------------------------
909  public:
910 
911  inline
912  static
913  Size bestCapacity()
914  {
915  return 6;
916  }
917 
918  inline
919  static
920  Size
921  degree( const Vertex & /* v */ )
922  {
923  return 6;
924  }
925 
926  template <typename OutputIterator>
927  inline
928  static
929  void writeNeighbors( OutputIterator &it, const Vertex & v )
930  {
931  Integer x = v[ 0 ];
932  Integer y = v[ 1 ];
933  Integer z = v[ 2 ];
934 
935  *it++ = Vertex( x , y-1, z );
936  *it++ = Vertex( x , y , z-1 );
937  *it++ = Vertex( x-1, y , z );
938  //*it++ = Vertex( x , y , z );
939  *it++ = Vertex( x+1, y , z );
940  *it++ = Vertex( x , y , z+1 );
941  *it++ = Vertex( x , y+1, z );
942  }
943 
944  template <typename OutputIterator, typename VertexPredicate>
945  inline
946  static
947  void writeNeighbors( OutputIterator &it, const Vertex & v, const VertexPredicate & pred)
948  {
949  Vertex q( v[ 0 ], v[ 1 ], v[ 2 ] - 1 );
950  if ( pred( q ) ) *it++ = q; // x , y , z-1
951  q[ 2 ] += 2; if ( pred( q ) ) *it++ = q; // x , y , z+1
952  --q[ 0 ], --q[ 2 ]; if ( pred( q ) ) *it++ = q; // x-1, y , z
953  q[ 0 ] += 2; if ( pred( q ) ) *it++ = q; // x+1, y , z
954  --q[ 0 ], --q[ 1 ]; if ( pred( q ) ) *it++ = q; // x , y-1, z
955  q[ 1 ] += 2; if ( pred( q ) ) *it++ = q; // x , y+1, z
956  }
957 
958  // ----------------------- Interface --------------------------------------
959  public:
960 
961  static
962  void selfDisplay ( std::ostream & out )
963  {
964  out << "[MetricAdjacency Z3*"
965  << " n1<=1*" << " ]";
966  }
967 
968  static
969  bool isValid() { return true; }
970 
971  private:
972  MetricAdjacency ( const MetricAdjacency & other );
973  MetricAdjacency & operator= ( const MetricAdjacency & other );
974 
975  // ------------------------- Internals ------------------------------------
976  private:
977 
978  }; // end of class MetricAdjacency
979 
980 
981 
982 
983 }
984