DGtal  1.4.beta
Object.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 Object.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  * @author Pablo Hernandez-Cerdan. Institute of Fundamental Sciences.
23  * Massey University. Palmerston North, New Zealand
24  *
25  * @date 2016/02/01
26  *
27  * Implementation of inline methods defined in Object.h
28  *
29  * This file is part of the DGtal library.
30  */
31 
32 
33 //////////////////////////////////////////////////////////////////////////////
34 #include <cstdlib>
35 #include "DGtal/kernel/sets/DigitalSetDomain.h"
36 #include "DGtal/topology/DigitalTopology.h"
37 #include "DGtal/topology/MetricAdjacency.h"
38 #include "DGtal/topology/DigitalTopologyTraits.h"
39 #include "DGtal/graph/BreadthFirstVisitor.h"
40 #include "DGtal/graph/Expander.h"
41 #include "DGtal/topology/NeighborhoodConfigurations.h"
42 #include "DGtal/topology/helpers/NeighborhoodConfigurationsHelper.h"
43 
44 //////////////////////////////////////////////////////////////////////////////
45 
46 ///////////////////////////////////////////////////////////////////////////////
47 // IMPLEMENTATION of inline methods.
48 ///////////////////////////////////////////////////////////////////////////////
49 
50 ///////////////////////////////////////////////////////////////////////////////
51 // ----------------------- Standard services ------------------------------
52 
53 /**
54  * Constructor.
55  *
56  */
57 template <typename TDigitalTopology, typename TDigitalSet>
58 inline
59 DGtal::Object<TDigitalTopology, TDigitalSet>::Object()
60  : myTopo( nullptr ),
61  myPointSet( nullptr ),
62  myConnectedness( UNKNOWN ),
63  myTable( nullptr ),
64  myNeighborConfigurationMap( nullptr ),
65  myTableIsLoaded( false )
66 {
67 }
68 
69 /**
70  * Constructor.
71  *
72  * @param aTopology the digital topology chosen for this set, a copy of
73  * which is stored in the object.
74  *
75  * @param aPointSet the set of points of the object. It is copied
76  * in the object.
77  */
78 template <typename TDigitalTopology, typename TDigitalSet>
79 inline
80 DGtal::Object<TDigitalTopology, TDigitalSet>::Object
81 ( Clone<DigitalTopology> aTopology,
82  Clone<DigitalSet> aPointSet,
83  Connectedness cxn )
84  : myTopo( aTopology ),
85  myPointSet( aPointSet ),
86  myConnectedness( cxn ),
87  myTable( nullptr ),
88  myNeighborConfigurationMap( nullptr ),
89  myTableIsLoaded(false)
90 {
91 }
92 
93 /**
94  * Copy constructor.
95  * @param other the object to clone.
96  *
97  * The copy is smart in the sense that the digital set is
98  * referenced, and will be copied only if the set is changed.
99  */
100 template <typename TDigitalTopology, typename TDigitalSet>
101 inline
102 DGtal::Object<TDigitalTopology, TDigitalSet>::Object
103 ( const Object & other )
104  : myTopo( other.myTopo ),
105  myPointSet( other.myPointSet ),
106  myConnectedness( other.myConnectedness ),
107  myTable( other.myTable ),
108  myNeighborConfigurationMap( other.myNeighborConfigurationMap ),
109  myTableIsLoaded(other.myTableIsLoaded)
110 {
111 }
112 
113 /**
114  * Constructor of an empty object by providing a domain.
115  *
116  * @param aTopology the digital topology chosen for this set, a copy of
117  * which is stored in the object.
118  *
119  * @param aDomain any domain related to the given topology.
120  */
121 template <typename TDigitalTopology, typename TDigitalSet>
122 inline
123 DGtal::Object<TDigitalTopology, TDigitalSet>::Object
124 ( Clone<DigitalTopology> aTopology,
125  Clone<Domain> aDomain )
126  : myTopo( new DigitalTopology( aTopology ) ),
127  myPointSet( new DigitalSet( aDomain ) ),
128  myConnectedness( CONNECTED ),
129  myTable( nullptr ),
130  myNeighborConfigurationMap( nullptr ),
131  myTableIsLoaded(false)
132 {
133 }
134 
135 
136 /**
137  * Destructor.
138  */
139 template <typename TDigitalTopology, typename TDigitalSet>
140 inline
141 DGtal::Object<TDigitalTopology, TDigitalSet>::~Object()
142 {
143 }
144 
145 /**
146  * Assignment.
147  * @param other the object to copy.
148  * @return a reference on 'this'.
149  */
150 template <typename TDigitalTopology, typename TDigitalSet>
151 inline
152 DGtal::Object<TDigitalTopology, TDigitalSet> &
153 DGtal::Object<TDigitalTopology, TDigitalSet>::operator=
154 ( const Object & other )
155 {
156  if ( this != &other )
157  {
158  myTopo = other.myTopo;
159  myPointSet = other.myPointSet;
160  myConnectedness = other.myConnectedness;
161  myTable = other.myTable;
162  myNeighborConfigurationMap = other.myNeighborConfigurationMap;
163  myTableIsLoaded = other.myTableIsLoaded;
164  }
165  return *this;
166 }
167 
168 /**
169  * @return the number of elements in the set.
170  */
171 template <typename TDigitalTopology, typename TDigitalSet>
172 inline
173 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
174 DGtal::Object<TDigitalTopology, TDigitalSet>::size() const
175 {
176  return myPointSet->size();
177 }
178 
179 
180 template <typename TDigitalTopology, typename TDigitalSet>
181 inline
182 void
183 DGtal::Object<TDigitalTopology, TDigitalSet>::setTable( Alias<boost::dynamic_bitset<> > input_table)
184 {
185  myTable = input_table;
186  myNeighborConfigurationMap = DGtal::functions::mapZeroPointNeighborhoodToConfigurationMask<Point>();
187  myTableIsLoaded = true;
188 }
189 
190 template <typename TDigitalTopology, typename TDigitalSet>
191 inline
192 DGtal::NeighborhoodConfiguration
193 DGtal::Object<TDigitalTopology, TDigitalSet>::
194 getNeighborhoodConfigurationOccupancy(const Point & center,
195  const std::unordered_map< Point,
196  NeighborhoodConfiguration> & mapZeroNeighborhoodToMask) const
197 {
198  using DomainConstIterator = typename Domain::ConstIterator;
199  Point p1 = Point::diagonal( -1 );
200  Point p2 = Point::diagonal( 1 );
201  Point c = Point::diagonal( 0 );
202  Domain cube_domain( p1, p2 );
203  const auto & not_found( this->pointSet().end() );
204  NeighborhoodConfiguration cfg{0};
205  for ( DomainConstIterator it = cube_domain.begin(); it != cube_domain.end(); ++it ) {
206  if( *it != c &&
207  this->pointSet().find( center + *it ) != not_found )
208  cfg |= mapZeroNeighborhoodToMask.at(*it) ;
209  }
210  return cfg;
211 
212 }
213 /**
214  * A const reference to the embedding domain.
215  */
216 template <typename TDigitalTopology, typename TDigitalSet>
217 inline
218 const typename DGtal::Object<TDigitalTopology, TDigitalSet>::Domain &
219 DGtal::Object<TDigitalTopology, TDigitalSet>::domain() const
220 {
221  return myPointSet->domain();
222 }
223 
224 template <typename TDigitalTopology, typename TDigitalSet>
225 inline
226 DGtal::CowPtr<typename DGtal::Object<TDigitalTopology, TDigitalSet>::Domain>
227 DGtal::Object<TDigitalTopology, TDigitalSet>::domainPointer() const
228 {
229  return myPointSet->domainPointer();
230 }
231 
232 
233 /**
234  * A const reference on the point set defining the points of the
235  * digital object.
236  */
237 template <typename TDigitalTopology, typename TDigitalSet>
238 inline
239 const TDigitalSet &
240 DGtal::Object<TDigitalTopology, TDigitalSet>::pointSet() const
241 {
242  return *myPointSet;
243 }
244 
245 /**
246  * A reference on the point set defining the points of the
247  * digital object (may duplicate the set).
248  */
249 template <typename TDigitalTopology, typename TDigitalSet>
250 inline
251 TDigitalSet &
252 DGtal::Object<TDigitalTopology, TDigitalSet>::pointSet()
253 {
254  myConnectedness = UNKNOWN;
255  return *myPointSet;
256 }
257 
258 /**
259  * @return a const reference to the topology of this object.
260  */
261 template <typename TDigitalTopology, typename TDigitalSet>
262 inline
263 const TDigitalTopology &
264 DGtal::Object<TDigitalTopology, TDigitalSet>::topology() const
265 {
266  return *myTopo;
267 }
268 
269 /**
270  * @return a const reference to the adjacency of this object.
271  */
272 template <typename TDigitalTopology, typename TDigitalSet>
273 inline
274 const typename TDigitalTopology::ForegroundAdjacency &
275 DGtal::Object<TDigitalTopology, TDigitalSet>::adjacency() const
276 {
277  return myTopo->kappa();
278 }
279 
280 
281 ///////////////////////////////////////////////////////////////////////////////
282 // ----------------------- Object services --------------------------------
283 
284 /**
285  * Let A be this object with foreground adjacency k and N_k(p) the
286  * k-neighborhood of p. Returns the set A intersected with N_k(p).
287  *
288  * @param p any point (in the domain of the digital object, not
289  * necessarily in the object).
290  *
291  * @return the kappa-neighborhood of [p] in this object.
292  */
293 template <typename TDigitalTopology, typename TDigitalSet>
294 inline
295 typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallObject
296 DGtal::Object<TDigitalTopology, TDigitalSet>::neighborhood
297 ( const Point & p ) const
298 {
299  typedef std::vector<Vertex> Container;
300  typedef typename Container::const_iterator ContainerConstIterator;
301  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
302 
303  // Intermediate container that is fast writable.
304  Container tmp_local_points;
305  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
306  adjacency().writeNeighbors( back_ins_it, p );
307  tmp_local_points.push_back( p );
308 
309  // A neighborhood is small, so is defined the digital object.
310  SmallObject neighA( myTopo, pointSet().domainPointer() );
311  const ContainerConstIterator it_end( tmp_local_points.end() );
312  const DigitalSetConstIterator not_found( pointSet().end() );
313  SmallSet & neighASet = neighA.pointSet();
314  for ( ContainerConstIterator it = tmp_local_points.begin();
315  it != it_end;
316  ++it )
317  if ( pointSet().find( *it ) != not_found )
318  neighASet.insertNew( *it ); // insertNew is guaranteed by construction.
319  return neighA;
320 }
321 
322 /**
323  * @param p any point (in the domain of the digital object, not
324  * necessarily in the object).
325  *
326  * @return the cardinal of the kappa-neighborhood of [p] in this object.
327  *
328  * @see neighborhood
329  *
330  * NB: faster than computing the neighborhood then computing its cardinal.
331  */
332 template <typename TDigitalTopology, typename TDigitalSet>
333 inline
334 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
335 DGtal::Object<TDigitalTopology, TDigitalSet>
336 ::neighborhoodSize( const Point & p ) const
337 {
338  typedef std::vector<Vertex> Container;
339  typedef typename Container::const_iterator ContainerConstIterator;
340  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
341 
342  // Intermediate container that is fast writable.
343  Container tmp_local_points;
344  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
345  adjacency().writeNeighbors( back_ins_it, p );
346  tmp_local_points.push_back( p );
347 
348  // A neighborhood is small, so is defined the digital object.
349  const ContainerConstIterator it_end( tmp_local_points.end() );
350  const DigitalSetConstIterator not_found( pointSet().end() );
351  Size nb = 0;
352  for ( ContainerConstIterator it = tmp_local_points.begin();
353  it != it_end;
354  ++it )
355  if ( pointSet().find( *it ) != not_found )
356  ++nb;
357  return nb;
358 }
359 
360 
361 /**
362  * Let A be this object with foreground adjacency k and N*_k(p)
363  * the proper k-neighborhood of p. Returns the set A intersected
364  * with N*_k(p).
365  *
366  * @param p any point (in the domain of the digital object, not
367  * necessarily in the object).
368  *
369  * @return the kappa-neighborhood of [p] in this object, without p.
370  */
371 template <typename TDigitalTopology, typename TDigitalSet>
372 inline
373 typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallObject
374 DGtal::Object<TDigitalTopology, TDigitalSet>::properNeighborhood
375 ( const Point & p ) const
376 {
377  typedef std::vector<Vertex> Container;
378  typedef typename Container::const_iterator ContainerConstIterator;
379  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
380 
381  // Intermediate container that is fast writable.
382  Container tmp_local_points;
383  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
384  adjacency().writeNeighbors( back_ins_it, p );
385 
386  // A neighborhood is small, so is defined the digital object.
387  SmallObject neighA( myTopo, pointSet().domainPointer() );
388  const ContainerConstIterator it_end( tmp_local_points.end() );
389  const DigitalSetConstIterator not_found( pointSet().end() );
390  SmallSet & neighASet = neighA.pointSet();
391  for ( ContainerConstIterator it = tmp_local_points.begin();
392  it != it_end;
393  ++it )
394  if ( pointSet().find( *it ) != not_found )
395  neighASet.insertNew( *it ); // insertNew is guaranteed by construction.
396  return neighA;
397 }
398 
399 /**
400  * @param p any point (in the domain of the digital object, not
401  * necessarily in the object).
402  *
403  * @return the cardinal of the kappa-neighborhood of [p] in this object.
404  *
405  * @see properNeighborhood
406  *
407  * NB: faster than computing the proper neighborhood then
408  * computing its cardinal.
409  */
410 template <typename TDigitalTopology, typename TDigitalSet>
411 inline
412 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
413 DGtal::Object<TDigitalTopology, TDigitalSet>
414 ::properNeighborhoodSize( const Point & p ) const
415 {
416  typedef std::vector<Vertex> Container;
417  typedef typename Container::const_iterator ContainerConstIterator;
418  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
419 
420  // Intermediate container that is fast writable.
421  Container tmp_local_points;
422 
423  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
424  adjacency().writeNeighbors( back_ins_it, p );
425 
426  // A neighborhood is small, so is defined the digital object.
427  const ContainerConstIterator it_end( tmp_local_points.end() );
428  const DigitalSetConstIterator not_found( pointSet().end() );
429  Size nb = 0;
430  for ( ContainerConstIterator it = tmp_local_points.begin();
431  it != it_end;
432  ++it )
433  if ( pointSet().find( *it ) != not_found )
434  ++nb;
435  return nb;
436 }
437 
438 
439 
440 /**
441  * @return the border of this object (the set of points of this
442  * which is lambda()-adjacent with some point of the background).
443  */
444 template <typename TDigitalTopology, typename TDigitalSet>
445 inline
446 DGtal::Object<TDigitalTopology, TDigitalSet>
447 DGtal::Object<TDigitalTopology, TDigitalSet>::border() const
448 {
449  typedef std::vector<Vertex> Container;
450  typedef typename Container::const_iterator ContainerConstIterator;
451  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
452  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
453  //typedef typename Domain::Predicate Predicate;
454 
455  // Intermediate container that is fast writable.
456  const DigitalSet & mySet = pointSet();
457  Object<DigitalTopology, DigitalSet> output( topology(),
458  mySet.domainPointer() );
459  DigitalSet & outputSet = output.pointSet();
460 
461  // Loop on all points of the set.
462  Container tmp_local_points;
463  const DigitalSetConstIterator it_end = mySet.end();
464  for ( DigitalSetConstIterator it = mySet.begin();
465  it != it_end;
466  ++it )
467  {
468  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
469  // Computing neighborhood within domain.
470  topology().lambda().writeNeighbors
471  ( back_ins_it, *it, domain().predicate() );
472  // Checks if any point is not in the object.
473  const ContainerConstIterator itc_end( tmp_local_points.end() );
474  for ( ContainerConstIterator itc = tmp_local_points.begin();
475  itc != itc_end;
476  ++itc )
477  if ( pointSet().find( *itc ) == it_end )
478  {
479  outputSet.insertNew( *it );
480  break;
481  }
482  tmp_local_points.clear();
483  }
484  return output;
485 }
486 
487 /**
488  * Computes the connected components of the object and writes
489  * them on the output iterator [it].
490  *
491  * @tparam OutputObjectIterator the type of an output iterator in
492  * a container of Object s.
493  *
494  * @param it the output iterator. *it is an Object.
495  */
496 template <typename TDigitalTopology, typename TDigitalSet>
497 template <typename OutputObjectIterator>
498 inline
499 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
500 DGtal::Object<TDigitalTopology, TDigitalSet>
501 ::writeComponents( OutputObjectIterator & it ) const
502 {
503  Size nb_components = 0;
504  if ( pointSet().empty() )
505  {
506  myConnectedness = CONNECTED;
507  return nb_components;
508  }
509  else
510  if ( connectedness() == CONNECTED )
511  {
512  *it++ = *this;
513  return 1;
514  }
515  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
516  DigitalSetConstIterator it_object = pointSet().begin();
517  Point p( *it_object++ );
518 
519  // first component.
520  BreadthFirstVisitor< Object, std::set<Vertex> > visitor( *this, p );
521  while ( ! visitor.finished() ) visitor.expand();
522  DigitalSet visited( domainPointer() );
523  visited.insertNew( visitor.markedVertices().begin(),
524  visitor.markedVertices().end() );
525  *it++ = Object( myTopo, visited, CONNECTED );
526  ++nb_components;
527  while ( it_object != pointSet().end() )
528  {
529  p = *it_object++;
530  if ( visited.find( p ) == visited.end() )
531  {
532  BreadthFirstVisitor< Object, std::set<Vertex> > visitor2( *this, p );
533  while ( ! visitor2.finished() ) visitor2.expand();
534  DigitalSet visited2( domainPointer() );
535  visited2.insertNew( visitor2.markedVertices().begin(),
536  visitor2.markedVertices().end() );
537  *it++ = Object( myTopo, visited2, CONNECTED );
538  ++nb_components;
539  visited += visited2;
540  }
541  }
542  // Expander<Object> expander( *this, p );
543  // while ( expander.nextLayer() )
544  // ;
545  // Object component( myTopo, expander.core(), CONNECTED );
546  // *it++ = component;
547  // ++nb_components;
548  // DigitalSet visited( expander.core() );
549  // while ( it_object != pointSet().end() )
550  // {
551  // p = *it_object++;
552  // if ( visited.find( p ) == visited.end() )
553  // {
554  // Expander<Object> expander2( *this, p );
555  // while ( expander2.nextLayer() )
556  // ;
557  // Object component2( myTopo, expander2.core(), CONNECTED );
558  // *it++ = component2;
559  // ++nb_components;
560  // visited += expander2.core();
561  // }
562  // }
563  myConnectedness = nb_components == 1 ? CONNECTED : DISCONNECTED;
564  return nb_components;
565 }
566 
567 /**
568  * @return the connectedness of this object. Either CONNECTED,
569  * DISCONNECTED, or UNKNOWN.
570  *
571  * @see computeConnectedness
572  */
573 template <typename TDigitalTopology, typename TDigitalSet>
574 DGtal::Connectedness
575 DGtal::Object<TDigitalTopology, TDigitalSet>::connectedness() const
576 {
577  return myConnectedness;
578 }
579 
580 /**
581  * If 'connectedness() == UNKNOWN', computes the connectedness of
582  * this object. After that, the connectedness of 'this' is either
583  * CONNECTED or DISCONNECTED.
584  *
585  * @return the connectedness of this object. Either CONNECTED or
586  * DISCONNECTED.
587  *
588  * @see connectedness
589  */
590 template <typename TDigitalTopology, typename TDigitalSet>
591 DGtal::Connectedness
592 DGtal::Object<TDigitalTopology, TDigitalSet>::computeConnectedness() const
593 {
594  if ( myConnectedness == UNKNOWN )
595  {
596  if ( pointSet().empty() )
597  myConnectedness = CONNECTED;
598  else
599  {
600  // Take first point
601  Vertex p = *( pointSet().begin() );
602  BreadthFirstVisitor< Object, std::set<Vertex> > visitor( *this, p );
603  while ( ! visitor.finished() )
604  {
605  visitor.expand();
606  }
607  myConnectedness = ( visitor.visitedVertices().size() == pointSet().size() )
608  ? CONNECTED : DISCONNECTED;
609  // JOL: 2012/11/16 There is apparently now a bug in expander !
610  // Very weird considering this was working in 2012/05. Perhaps
611  // this is related to some manipulations in predicates.
612  //
613  // Expander<Object> expander( *this, p );
614  // // and expand.
615  // while ( expander.nextLayer() )
616  // ;
617  // myConnectedness = ( expander.core().size() == pointSet().size() )
618  // ? CONNECTED : DISCONNECTED;
619  }
620  }
621  return myConnectedness;
622 }
623 
624 ///////////////////////////////////////////////////////////////////////////////
625 // ----------------------- Graph services ------------------------------
626 
627 template <typename TDigitalTopology, typename TDigitalSet>
628 inline
629 typename DGtal::Object<TDigitalTopology, TDigitalSet>::ConstIterator
630 DGtal::Object<TDigitalTopology, TDigitalSet>::begin() const
631 {
632  return myPointSet->begin();
633 }
634 
635 template <typename TDigitalTopology, typename TDigitalSet>
636 inline
637 typename DGtal::Object<TDigitalTopology, TDigitalSet>::ConstIterator
638 DGtal::Object<TDigitalTopology, TDigitalSet>::end() const
639 {
640  return myPointSet->end();
641 }
642 
643 /**
644  * @param v any vertex of the object
645  *
646  * @return the number of neighbors of this vertex
647  */
648 template <typename TDigitalTopology, typename TDigitalSet>
649 inline
650 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
651 DGtal::Object<TDigitalTopology, TDigitalSet>::degree
652 ( const Vertex & v ) const
653 {
654  return properNeighborhoodSize( v );
655 }
656 
657 /**
658  * @return the maximum number of neighbors for a vertex of this object
659  */
660 template <typename TDigitalTopology, typename TDigitalSet>
661 inline
662 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
663 DGtal::Object<TDigitalTopology, TDigitalSet>::bestCapacity() const
664 {
665  return myTopo->kappa().bestCapacity();
666 }
667 
668 /**
669  * Writes the neighbors of a vertex using an output iterator
670  *
671  *
672  * @tparam OutputIterator the type of an output iterator writing
673  * in a container of vertices.
674  *
675  * @param it the output iterator
676  *
677  * @param v the vertex whose neighbors will be writeNeighbors
678  */
679 template <typename TDigitalTopology, typename TDigitalSet>
680 template <typename OutputIterator>
681 inline
682 void
683 DGtal::Object<TDigitalTopology, TDigitalSet>::
684 writeNeighbors( OutputIterator & it,
685  const Vertex & v ) const
686 {
687  typedef std::vector<Vertex> Container;
688  typedef typename Container::const_iterator ContainerConstIterator;
689  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
690 
691  // Intermediate container that is fast writable.
692  Container tmp_local_points;
693  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
694  adjacency().writeNeighbors( back_ins_it, v );
695 
696  // A neighborhood is small, so is defined the digital object.
697  const ContainerConstIterator it_end( tmp_local_points.end() );
698  const DigitalSetConstIterator not_found( pointSet().end() );
699  for ( ContainerConstIterator cit = tmp_local_points.begin();
700  cit != it_end;
701  ++cit )
702  if ( pointSet().find( *cit ) != not_found )
703  *it++ = *cit;
704 }
705 
706 /**
707  * Writes the neighbors of a vertex which satisfy a predicate using an
708  * output iterator
709  *
710  *
711  * @tparam OutputIterator the type of an output iterator writing
712  * in a container of vertices.
713  *
714  * @tparam VertexPredicate the type of the predicate
715  *
716  * @param it the output iterator
717  *
718  * @param v the vertex whose neighbors will be written
719  *
720  * @param pred the predicate that must be satisfied
721  */
722 template <typename TDigitalTopology, typename TDigitalSet>
723 template <typename OutputIterator, typename VertexPredicate>
724 inline
725 void
726 DGtal::Object<TDigitalTopology, TDigitalSet>::
727 writeNeighbors( OutputIterator & it,
728  const Vertex & v,
729  const VertexPredicate & pred ) const
730 {
731  typedef std::vector<Vertex> Container;
732  typedef typename Container::const_iterator ContainerConstIterator;
733  typedef typename DigitalSet::ConstIterator DigitalSetConstIterator;
734 
735  // Intermediate container that is fast writable.
736  Container tmp_local_points;
737  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
738  adjacency().writeNeighbors( back_ins_it, v );
739 
740  // A neighborhood is small, so is defined the digital object.
741  const ContainerConstIterator it_end( tmp_local_points.end() );
742  const DigitalSetConstIterator not_found( pointSet().end() );
743  for ( ContainerConstIterator cit = tmp_local_points.begin();
744  cit != it_end;
745  ++cit )
746  if ( ( pointSet().find( *cit ) != not_found ) && pred(*cit) )
747  *it++ = *cit;
748 }
749 
750 /**
751  * @note For this to work with graph algorithms, the source of the edge must be the input vertex, even on undirected graphs.
752  */
753 template <typename TDigitalTopology, typename TDigitalSet>
754 inline
755 typename DGtal::Object<TDigitalTopology, TDigitalSet>::EdgeRange
756 DGtal::Object<TDigitalTopology, TDigitalSet>::
757 outEdges( const Vertex & v) const
758 {
759  typedef std::vector<Vertex> Container;
760 
761  Container tmp_local_points;
762  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
763 
764  EdgeRange out_edges;
765  this->writeNeighbors(back_ins_it, v);
766  for ( auto && cit = tmp_local_points.begin();
767  cit != tmp_local_points.end(); ++cit )
768  out_edges.emplace_back(Edge(v, *cit, true));
769 
770  return out_edges;
771 }
772 
773 template <typename TDigitalTopology, typename TDigitalSet>
774 inline
775 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Vertex
776 DGtal::Object<TDigitalTopology, TDigitalSet>::
777 head( const Edge & e ) const
778 {
779  return e.vertices[1];
780 }
781 //-----------------------------------------------------------------------------
782 template <typename TDigitalTopology, typename TDigitalSet>
783 inline
784 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Vertex
785 DGtal::Object<TDigitalTopology, TDigitalSet>::
786 tail( const Edge & e ) const
787 {
788  return e.vertices[0];
789 }
790 //-----------------------------------------------------------------------------
791 template <typename TDigitalTopology, typename TDigitalSet>
792 inline
793 typename DGtal::Object<TDigitalTopology, TDigitalSet>::Edge
794 DGtal::Object<TDigitalTopology, TDigitalSet>::
795 opposite( const Edge & v) const
796 {
797  // boolean constructor to force order of vertices.
798  return Edge(v.vertices[1],v.vertices[0], true);
799 }
800 ///////////////////////////////////////////////////////////////////////////////
801 // ----------------------- Simple points -------------------------------
802 
803 /**
804  * Geodesic neighborhood of point [p] and order [k] in the object
805  * for the given metric adjacency.
806  */
807 template <typename TDigitalTopology, typename TDigitalSet>
808 template <typename TAdjacency>
809 inline
810 typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallObject
811 DGtal::Object<TDigitalTopology, TDigitalSet>
812 ::geodesicNeighborhood
813 ( const TAdjacency & adj, const Point & p, unsigned int k ) const
814 {
815  // Local types.
816  typedef std::vector<Vertex> Container;
817  typedef MetricAdjacency<Space, Space::dimension> AlphaAdjacency;
818  typedef MetricAdjacency<Space, 1> OmegaAdjacency;
819  typedef DGtal::DigitalTopology<TAdjacency, OmegaAdjacency> LocalTopology;
820  typedef Object<LocalTopology, SmallSet> LocalObject;
821  typedef HyperRectDomain<Space> LocalDomain;
822 
823  AlphaAdjacency alpha;
824  OmegaAdjacency omega;
825  // Intermediate container that is fast writable.
826  Container tmp_local_points;
827  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
828  alpha.writeNeighbors( back_ins_it, p, *myPointSet ); // p is not a neighbor itself.
829 
830  // Construct local domain.
831  Point p1 = p - Point::diagonal(1);
832  Point p2 = p + Point::diagonal(1);
833  CowPtr<LocalDomain> aDomain( new LocalDomain( p1, p2 ) );
834 
835  // Construct local X.
836  LocalTopology aTopology( adj, omega );
837  LocalObject X( aTopology, aDomain );
838  X.pointSet().insertNew( tmp_local_points.begin(), tmp_local_points.end() );
839 
840  // A neighborhood is small, so is defined the digital object.
841  typename LocalObject::SmallObject neighAdj = X.properNeighborhood( p );
842 
843  BreadthFirstVisitor<LocalObject, std::set<Vertex> > visitor
844  ( X, neighAdj.pointSet().begin(),
845  neighAdj.pointSet().end() );
846  while ( ! visitor.finished() )
847  {
848  typename LocalObject::Size d = visitor.current().second;
849  if ( d < k ) visitor.expand(); // we need to go further
850  else if ( d == k ) visitor.ignore(); // no need to go further
851  else break; // to far away, we exit
852  }
853  visitor.terminate();
854  SmallObject geodesicN( this->topology(), aDomain );
855  geodesicN.pointSet().insertNew( visitor.markedVertices().begin(),
856  visitor.markedVertices().end() );
857 
858  // JOL: 2012/11/16 There is apparently now a bug in expander !
859  // Very weird considering this was working in 2012/05. Perhaps
860  // this is related to some manipulations in predicates.
861  // Expander<LocalObject> expander( X,
862  // neighAdj.pointSet().begin(),
863  // neighAdj.pointSet().end() );
864  // for ( unsigned int i = 1; ( i < k ) && ( ! expander.finished() ); ++i )
865  // expander.nextLayer();
866  // SmallObject geodesicN( this->topology(), expander.core() );
867  return geodesicN;
868 
869 }
870 
871 /**
872  * Geodesic neighborhood of point [p] and order [k] in the
873  * complemented object for the given metric adjacency.
874  */
875 template <typename TDigitalTopology, typename TDigitalSet>
876 template <typename TAdjacency>
877 inline
878 typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallComplementObject
879 DGtal::Object<TDigitalTopology, TDigitalSet>
880 ::geodesicNeighborhoodInComplement
881 ( const TAdjacency & adj, const Point & p, unsigned int k ) const
882 {
883  // Local types.
884  typedef std::vector<Vertex> Container;
885  typedef MetricAdjacency<Space, Space::dimension> AlphaAdjacency;
886  typedef MetricAdjacency<Space, 1> OmegaAdjacency;
887  typedef DGtal::DigitalTopology<TAdjacency, OmegaAdjacency> LocalTopology;
888  typedef Object<LocalTopology, SmallSet> LocalObject;
889  typedef HyperRectDomain<Space> LocalDomain;
890  // DigitalSetDomain<DigitalSet> limitedX( *myPointSet );
891  AlphaAdjacency alpha;
892  OmegaAdjacency omega;
893  // Intermediate container that is fast writable.
894  Container tmp_local_points;
895  std::back_insert_iterator< Container > back_ins_it( tmp_local_points );
896  functors::NotPointPredicate<DigitalSet> not_pred_is_in_X( *myPointSet );
897  alpha.writeNeighbors( back_ins_it, p, not_pred_is_in_X );
898 
899  // Construct local domain.
900  Point p1 = p - Point::diagonal(1);
901  Point p2 = p + Point::diagonal(1);
902  CowPtr<LocalDomain> aDomain( new LocalDomain( p1, p2 ) );
903 
904  // Construct local Xcomp.
905  LocalTopology aTopology( adj, omega );
906  LocalObject Xcomp( aTopology, aDomain );
907  Xcomp.pointSet().insertNew( tmp_local_points.begin(), tmp_local_points.end() );
908 
909  // A neighborhood is small, so is defined the digital object.
910  typename LocalObject::SmallObject neighAdj = Xcomp.properNeighborhood( p );
911 
912  BreadthFirstVisitor<LocalObject, std::set<Vertex> > visitor
913  ( Xcomp, neighAdj.pointSet().begin(),
914  neighAdj.pointSet().end() );
915  while ( ! visitor.finished() )
916  {
917  typename LocalObject::Size d = visitor.current().second;
918  if ( d < k ) visitor.expand(); // we need to go further
919  else if ( d == k ) visitor.ignore(); // no need to go further
920  else break; // to far away, we exit
921  }
922  visitor.terminate();
923 
924  SmallComplementObject geodesicN( this->topology().reverseTopology(),
925  aDomain );
926  geodesicN.pointSet().insertNew( visitor.markedVertices().begin(),
927  visitor.markedVertices().end() );
928 
929  // JOL: 2012/11/16 There is apparently now a bug in expander !
930  // Very weird considering this was working in 2012/05. Perhaps
931  // this is related to some manipulations in predicates.
932  // Expander<LocalObject> expander( Xcomp,
933  // neighAdj.pointSet().begin(),
934  // neighAdj.pointSet().end() );
935  // for ( unsigned int i = 1; ( i < k ) && ( ! expander.finished() ); ++i )
936  // expander.nextLayer();
937  // SmallComplementObject geodesicN( this->topology().reverseTopology(),
938  // expander.core() );
939  return geodesicN;
940 }
941 
942 template <typename TDigitalTopology, typename TDigitalSet>
943 inline
944 bool
945 DGtal::Object<TDigitalTopology, TDigitalSet>
946 ::isSimpleFromTable(
947  const Point & center,
948  const boost::dynamic_bitset<> & input_table,
949  const std::unordered_map< Point,
950  NeighborhoodConfiguration> & mapZeroNeighborhoodToMask) const
951 {
952  return input_table[this->getNeighborhoodConfigurationOccupancy(center, mapZeroNeighborhoodToMask)];
953 }
954 /**
955  * [Bertrand, 1994] A voxel v is simple for a set X if #C6 [G6 (v,
956  * X)] = #C18[G18(v, X^c)] = 1, where #Ck [Y] denotes the number
957  * of k-connected components of a set Y.
958  *
959  * We adapt this definition to (kappa,lambda) connectednesses. Be
960  * careful, such a definition is valid only for Jordan couples in
961  * dimension 2 and 3.
962  *
963  * @return 'true' if this point is simple.
964  */
965 template <typename TDigitalTopology, typename TDigitalSet>
966 inline
967 bool
968 DGtal::Object<TDigitalTopology, TDigitalSet>
969 ::isSimple( const Point & v ) const
970 {
971  if(myTableIsLoaded == true)
972  return isSimpleFromTable(v, *myTable, *myNeighborConfigurationMap);
973 
974  static const int kappa_n =
975  DigitalTopologyTraits< ForegroundAdjacency, BackgroundAdjacency, Space::dimension >::GEODESIC_NEIGHBORHOOD_SIZE;
976  static const int lambda_n =
977  DigitalTopologyTraits< BackgroundAdjacency, ForegroundAdjacency, Space::dimension >::GEODESIC_NEIGHBORHOOD_SIZE;
978 
979  SmallObject Gkappa_X
980  = geodesicNeighborhood( topology().kappa(),
981  v, kappa_n ); // Space::dimension );
982  if ( Gkappa_X.computeConnectedness() == CONNECTED )
983  {
984  if ( Gkappa_X.pointSet().empty() )
985  return false;
986  SmallComplementObject Glambda_compX
987  = geodesicNeighborhoodInComplement( topology().lambda(),
988  v, lambda_n ); // Space::dimension );
989  return ( Glambda_compX.computeConnectedness()
990  == CONNECTED )
991  && ( ! Glambda_compX.pointSet().empty() );
992  }
993  return false;
994 }
995 
996 
997 ///////////////////////////////////////////////////////////////////////////////
998 // Interface - public :
999 
1000 /**
1001  * Writes/Displays the object on an output stream.
1002  * @param out the output stream where the object is written.
1003  */
1004 template <typename TDigitalTopology, typename TDigitalSet>
1005 inline
1006 void
1007 DGtal::Object<TDigitalTopology, TDigitalSet>
1008 ::selfDisplay ( std::ostream & out ) const
1009 {
1010  out << "[Object"
1011  << " topology=" << myTopo
1012  << " counts=" << myPointSet.count()
1013  << " set=" << *myPointSet
1014  << " cxn=" << myConnectedness
1015  << "]";
1016 }
1017 
1018 /**
1019  * Checks the validity/consistency of the object.
1020  * @return 'true' if the object is valid, 'false' otherwise.
1021  */
1022 template <typename TDigitalTopology, typename TDigitalSet>
1023 inline
1024 bool
1025 DGtal::Object<TDigitalTopology, TDigitalSet>::isValid() const
1026 {
1027  return ( *myPointSet != 0 ) && (*myTopo != 0 );
1028 }
1029 
1030 /**
1031  * Default drawing style object.
1032  * @return the dyn. alloc. default style for this object.
1033  */
1034 
1035 
1036 /**
1037  * @return the style name used for drawing this object.
1038  */
1039 template <typename TDigitalTopology, typename TDigitalSet>
1040 inline
1041 std::string
1042 DGtal::Object<TDigitalTopology, TDigitalSet>::className() const
1043 {
1044  return "Object";
1045 }
1046 
1047 
1048 
1049 ///////////////////////////////////////////////////////////////////////////////
1050 // Implementation of inline functions //
1051 
1052 template <typename TDigitalTopology, typename TDigitalSet>
1053 inline
1054 std::ostream&
1055 DGtal::operator<< ( std::ostream & out,
1056  const Object<TDigitalTopology, TDigitalSet> & object )
1057 {
1058  object.selfDisplay( out );
1059  return out;
1060 }
1061 
1062 // //
1063 ///////////////////////////////////////////////////////////////////////////////
1064 
1065