DGtal 1.4.0
Loading...
Searching...
No Matches
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 */
57template <typename TDigitalTopology, typename TDigitalSet>
58inline
59DGtal::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 */
78template <typename TDigitalTopology, typename TDigitalSet>
79inline
80DGtal::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 */
100template <typename TDigitalTopology, typename TDigitalSet>
101inline
102DGtal::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 */
121template <typename TDigitalTopology, typename TDigitalSet>
122inline
123DGtal::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 */
139template <typename TDigitalTopology, typename TDigitalSet>
140inline
141DGtal::Object<TDigitalTopology, TDigitalSet>::~Object()
142{
143}
144
145/**
146 * Assignment.
147 * @param other the object to copy.
148 * @return a reference on 'this'.
149 */
150template <typename TDigitalTopology, typename TDigitalSet>
151inline
152DGtal::Object<TDigitalTopology, TDigitalSet> &
153DGtal::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 */
171template <typename TDigitalTopology, typename TDigitalSet>
172inline
173typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
174DGtal::Object<TDigitalTopology, TDigitalSet>::size() const
175{
176 return myPointSet->size();
177}
178
179
180template <typename TDigitalTopology, typename TDigitalSet>
181inline
182void
183DGtal::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
190template <typename TDigitalTopology, typename TDigitalSet>
191inline
192DGtal::NeighborhoodConfiguration
193DGtal::Object<TDigitalTopology, TDigitalSet>::
194getNeighborhoodConfigurationOccupancy(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 */
216template <typename TDigitalTopology, typename TDigitalSet>
217inline
218const typename DGtal::Object<TDigitalTopology, TDigitalSet>::Domain &
219DGtal::Object<TDigitalTopology, TDigitalSet>::domain() const
220{
221 return myPointSet->domain();
222}
223
224template <typename TDigitalTopology, typename TDigitalSet>
225inline
226DGtal::CowPtr<typename DGtal::Object<TDigitalTopology, TDigitalSet>::Domain>
227DGtal::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 */
237template <typename TDigitalTopology, typename TDigitalSet>
238inline
239const TDigitalSet &
240DGtal::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 */
249template <typename TDigitalTopology, typename TDigitalSet>
250inline
251TDigitalSet &
252DGtal::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 */
261template <typename TDigitalTopology, typename TDigitalSet>
262inline
263const TDigitalTopology &
264DGtal::Object<TDigitalTopology, TDigitalSet>::topology() const
265{
266 return *myTopo;
267}
268
269/**
270 * @return a const reference to the adjacency of this object.
271 */
272template <typename TDigitalTopology, typename TDigitalSet>
273inline
274const typename TDigitalTopology::ForegroundAdjacency &
275DGtal::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 */
293template <typename TDigitalTopology, typename TDigitalSet>
294inline
295typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallObject
296DGtal::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 */
332template <typename TDigitalTopology, typename TDigitalSet>
333inline
334typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
335DGtal::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 */
371template <typename TDigitalTopology, typename TDigitalSet>
372inline
373typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallObject
374DGtal::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 */
410template <typename TDigitalTopology, typename TDigitalSet>
411inline
412typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
413DGtal::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 */
444template <typename TDigitalTopology, typename TDigitalSet>
445inline
446DGtal::Object<TDigitalTopology, TDigitalSet>
447DGtal::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 */
496template <typename TDigitalTopology, typename TDigitalSet>
497template <typename OutputObjectIterator>
498inline
499typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
500DGtal::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 */
573template <typename TDigitalTopology, typename TDigitalSet>
574DGtal::Connectedness
575DGtal::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 */
590template <typename TDigitalTopology, typename TDigitalSet>
591DGtal::Connectedness
592DGtal::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
627template <typename TDigitalTopology, typename TDigitalSet>
628inline
629typename DGtal::Object<TDigitalTopology, TDigitalSet>::ConstIterator
630DGtal::Object<TDigitalTopology, TDigitalSet>::begin() const
631{
632 return myPointSet->begin();
633}
634
635template <typename TDigitalTopology, typename TDigitalSet>
636inline
637typename DGtal::Object<TDigitalTopology, TDigitalSet>::ConstIterator
638DGtal::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 */
648template <typename TDigitalTopology, typename TDigitalSet>
649inline
650typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
651DGtal::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 */
660template <typename TDigitalTopology, typename TDigitalSet>
661inline
662typename DGtal::Object<TDigitalTopology, TDigitalSet>::Size
663DGtal::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 */
679template <typename TDigitalTopology, typename TDigitalSet>
680template <typename OutputIterator>
681inline
682void
683DGtal::Object<TDigitalTopology, TDigitalSet>::
684writeNeighbors( 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 */
722template <typename TDigitalTopology, typename TDigitalSet>
723template <typename OutputIterator, typename VertexPredicate>
724inline
725void
726DGtal::Object<TDigitalTopology, TDigitalSet>::
727writeNeighbors( 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 */
753template <typename TDigitalTopology, typename TDigitalSet>
754inline
755typename DGtal::Object<TDigitalTopology, TDigitalSet>::EdgeRange
756DGtal::Object<TDigitalTopology, TDigitalSet>::
757outEdges( 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
773template <typename TDigitalTopology, typename TDigitalSet>
774inline
775typename DGtal::Object<TDigitalTopology, TDigitalSet>::Vertex
776DGtal::Object<TDigitalTopology, TDigitalSet>::
777head( const Edge & e ) const
778{
779 return e.vertices[1];
780}
781//-----------------------------------------------------------------------------
782template <typename TDigitalTopology, typename TDigitalSet>
783inline
784typename DGtal::Object<TDigitalTopology, TDigitalSet>::Vertex
785DGtal::Object<TDigitalTopology, TDigitalSet>::
786tail( const Edge & e ) const
787{
788 return e.vertices[0];
789}
790//-----------------------------------------------------------------------------
791template <typename TDigitalTopology, typename TDigitalSet>
792inline
793typename DGtal::Object<TDigitalTopology, TDigitalSet>::Edge
794DGtal::Object<TDigitalTopology, TDigitalSet>::
795opposite( 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 */
807template <typename TDigitalTopology, typename TDigitalSet>
808template <typename TAdjacency>
809inline
810typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallObject
811DGtal::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 */
875template <typename TDigitalTopology, typename TDigitalSet>
876template <typename TAdjacency>
877inline
878typename DGtal::Object<TDigitalTopology, TDigitalSet>::SmallComplementObject
879DGtal::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
942template <typename TDigitalTopology, typename TDigitalSet>
943inline
944bool
945DGtal::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 */
965template <typename TDigitalTopology, typename TDigitalSet>
966inline
967bool
968DGtal::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 */
1004template <typename TDigitalTopology, typename TDigitalSet>
1005inline
1006void
1007DGtal::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 */
1022template <typename TDigitalTopology, typename TDigitalSet>
1023inline
1024bool
1025DGtal::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 */
1039template <typename TDigitalTopology, typename TDigitalSet>
1040inline
1041std::string
1042DGtal::Object<TDigitalTopology, TDigitalSet>::className() const
1043{
1044 return "Object";
1045}
1046
1047
1048
1049///////////////////////////////////////////////////////////////////////////////
1050// Implementation of inline functions //
1051
1052template <typename TDigitalTopology, typename TDigitalSet>
1053inline
1054std::ostream&
1055DGtal::operator<< ( std::ostream & out,
1056 const Object<TDigitalTopology, TDigitalSet> & object )
1057{
1058 object.selfDisplay( out );
1059 return out;
1060}
1061
1062// //
1063///////////////////////////////////////////////////////////////////////////////
1064
1065