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