DGtal 1.3.0
Loading...
Searching...
No Matches
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 */
46template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
47inline
48DGtal::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 */
56template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
57inline
58DGtal::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 */
73template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
74inline
75bool
76DGtal::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 */
90template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
91inline
92bool
93DGtal::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 */
113template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
114inline
115typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
116DGtal::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 */
126template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
127inline
128typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
129DGtal::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 */
146template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
147template <typename OutputIterator>
148inline
149void
150DGtal::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 */
188template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
189template <typename OutputIterator, typename VertexPredicate>
190void
191DGtal::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 */
220template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
221inline
222void
223DGtal::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 */
234template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
235inline
236bool
237DGtal::MetricAdjacency<TSpace,maxNorm1,dimension>::isValid()
238{
239 return true;
240}
241
242
243
244///////////////////////////////////////////////////////////////////////////////
245// Implementation of inline functions //
246
247template <typename TSpace, DGtal::Dimension maxNorm1>
248inline
249std::ostream&
250DGtal::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 //
261template <typename TSpace, DGtal::Dimension maxNorm1, DGtal::Dimension dimension>
262inline
263typename DGtal::MetricAdjacency<TSpace, maxNorm1, dimension>::Size
264DGtal::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
277namespace 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
Generated on Sun Nov 27 2022 15:15:52 for DGtal by doxygen 1.9.5