DGtal  1.2.0
SegmentComputerUtils.h
1 
17 #pragma once
18 
34 #if defined(SegmentComputerUtils_RECURSES)
35 #error Recursive header files inclusion detected in SegmentComputerUtils.h
36 #else // defined(SegmentComputerUtils_RECURSES)
38 #define SegmentComputerUtils_RECURSES
39 
40 #if !defined SegmentComputerUtils_h
42 #define SegmentComputerUtils_h
43 
44 
45 #include "DGtal/base/Circulator.h"
46 
47 namespace DGtal
48 {
49 
51 // Categories
52  struct ForwardSegmentComputer{};
53  struct BidirectionalSegmentComputer{};
54  struct DynamicSegmentComputer{};
55  struct DynamicBidirectionalSegmentComputer{};
56 
57 
59 
69 //default
70 template <typename SC>
71 struct SegmentComputerTraits {
72  typedef ForwardSegmentComputer Category;
73 // typedef DynamicBidirectionalSegmentComputer Category;
74 // typedef BidirectionalSegmentComputer Category;
75 };
76 
77 
78 
80 // Useful functions for segment computers
81 
82 
86 template<typename IC>
87 IC getMiddleIterator(const IC& itb, const IC& ite, RandomAccessCategory)
88 {
89 //how to compute this with circulators ?
90 //return itb + ((ite-itb)/2);
91 //does not work
92  return getMiddleIterator(itb, ite, BidirectionalCategory() );
93 }
94 
99 template<typename IC>
100 IC getMiddleIterator(const IC& itb, const IC& ite, BidirectionalCategory)
101 {
102  IC b( itb );
103  IC f( ite );
104  bool flag = true;
105  while (b != f) {
106  if (flag) {
107  --f;
108  flag = false;
109  } else {
110  ++b;
111  flag = true;
112  }
113  }
114  return b;
115 }
116 
121 template<typename IC>
122 IC getMiddleIterator(const IC& itb, const IC& ite, ForwardCategory)
123 {
124  IC i( itb );
125 
126  unsigned int c = 0;
127  while (i != ite) {
128  ++i;
129  ++c;
130  }
131  unsigned int k = c/2;
132 
133  c = 0;
134  i = itb;
135  while (c != k) {
136  ++i;
137  ++c;
138  }
139 
140  return i;
141 }
150 template<typename IC>
151 IC getMiddleIterator(const IC& itb, const IC& ite) {
152  typedef typename IteratorCirculatorTraits<IC>::Category Category;
153  return getMiddleIterator(itb, ite, Category() );
154 }
155 
158 
159 
163 template <typename SC>
164 void maximalExtension(SC& s, const typename SC::ConstIterator& end, IteratorType ) {
165  //stop if s.end() == end
166  while ( (s.end() != end)
167  && (s.extendFront()) ) {}
168 }
169 
173 template <typename SC>
174 void maximalExtension(SC& s, const typename SC::ConstIterator& /*end*/, CirculatorType )
175 {
176  //stop if the segment is the whole range
177  const typename SC::ConstIterator newEnd( s.begin() );
178  while ( (s.extendFront())
179  && (s.end() != newEnd) ) {}
180 }
187 template <typename SC>
188 void maximalExtension(SC& s, const typename SC::ConstIterator& end) {
189  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type;
190  maximalExtension( s, end, Type() );
191 }
192 
193 
197 template <typename SC>
198 void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin, IteratorType ) {
199  //extend one more time if s.begin() == begin
200  while ( (s.begin() != begin)
201  && (s.extendBack()) ) {}
202  if (s.begin() == begin) s.extendBack();
203 }
204 
208 template <typename SC>
209 void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin, CirculatorType )
210 {
211  boost::ignore_unused_variable_warning( begin );
212  //stop if the segment is the whole range
213  const typename SC::ConstIterator newBegin( s.end() );
214  while ( (s.extendBack())
215  && (s.begin() != newBegin) ) {}
216 }
217 
224 template <typename SC>
225 void oppositeEndMaximalExtension(SC& s, const typename SC::ConstIterator& begin) {
226  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type;
227  oppositeEndMaximalExtension( s, begin, Type() );
228 }
229 
230 
231 
235 template <typename SC>
236 bool maximalSymmetricExtension(SC& s,
237  const typename SC::ConstIterator& begin,
238  const typename SC::ConstIterator& end,
239  IteratorType ) {
240 
241  bool flagOk = true;
242  bool flagForward = true;
243  //while the extension is possible
244  //at the front and (then) at the back
245  while (flagOk) {
246  if (flagForward) {
247  flagForward = false;
248  if ( s.end() != end ) flagOk = s.extendFront();
249  else flagOk = false;
250  } else {
251  flagForward = true;
252  if ( s.begin() != begin ) flagOk = s.extendBack();
253  else flagOk = false;
254  }
255  }
256  //extend one more time if s.begin() == begin
257  if (s.begin() != begin ) {
258  if (s.extendBack()) return !s.extendFront();
259  else return false;
260  } else {
261  return !flagForward;
262  }
263 
264 }
265 
269 template <typename SC>
270 bool maximalSymmetricExtension(SC& s,
271  const typename SC::ConstIterator& begin,
272  const typename SC::ConstIterator& end,
273  CirculatorType )
274 {
275  boost::ignore_unused_variable_warning( begin );
276  boost::ignore_unused_variable_warning( end );
277 
278  bool flagOk = true;
279  bool flagForward = true;
280  //while the extensions are possible and
281  //the segment does not correspond to the whole range
282  while ( (flagOk) && ( s.end() != s.begin() ) ) {
283  if (flagForward) {
284  flagForward = false;
285  flagOk = s.extendFront();
286  } else {
287  flagForward = true;
288  flagOk = s.extendBack();
289  }
290  }
291  return !flagForward;
292 }
293 
304 template <typename SC>
305 bool maximalSymmetricExtension(SC& s,
306  const typename SC::ConstIterator& begin,
307  const typename SC::ConstIterator& end) {
308 
309  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type;
310  return maximalSymmetricExtension( s, begin, end, Type() );
311 
312 }
313 
314 
322 template <typename SC>
323 void maximalRetraction(SC& s, const typename SC::ConstIterator& end)
324 {
325  if ( isNotEmpty<typename SC::ConstIterator>(s.end(),end) ) {
326  while ( (! s.isExtendableFront() )
327  &&(s.retractBack() ) ) {}
328  } else {
329  while ( s.retractBack() ) {}
330  }
331 }
332 
340 template <typename SC>
341 void oppositeEndMaximalRetraction(SC& s, const typename SC::ConstIterator& begin)
342 {
343  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) ) {
344  while ( (! s.isExtendableBack() )
345  &&(s.retractFront() ) ) {}
346  } else {
347  while ( s.retractFront() ) {}
348  }
349 }
350 
353 
354 
358 template <typename SC>
359 void longestSegment(SC& s,
360  const typename SC::ConstIterator& i,
361  const typename SC::ConstIterator& end,
362  IteratorType )
363  {
364  if (i != end) {
365  s.init(i);
366  maximalExtension(s, end, IteratorType() );
367  }
368 }
369 
373 template <typename SC>
374 void longestSegment(SC& s,
375  const typename SC::ConstIterator& i,
376  const typename SC::ConstIterator& end,
377  CirculatorType )
378 {
379  s.init(i);
380  maximalExtension(s, end, CirculatorType() );
381 }
382 
390 template <typename SC>
391 void longestSegment(SC& s,
392  const typename SC::ConstIterator& i,
393  const typename SC::ConstIterator& end)
394 {
395  typedef typename IteratorCirculatorTraits<typename SC::ConstIterator>::Type Type;
396  longestSegment( s, i, end, Type() );
397 }
398 
399 
402 
411 template <typename SC>
412 void firstMaximalSegment(SC& s,
413  const typename SC::ConstIterator& i,
414  const typename SC::ConstIterator& begin,
415  const typename SC::ConstIterator& end,
416  DGtal::ForwardSegmentComputer )
417 {
418 
419  typedef typename SC::ConstIterator ConstIterator;
420  typedef typename SC::Reverse ReverseSegmentComputer;
421  typedef typename ReverseSegmentComputer::ConstIterator ConstReverseIterator;
422 
423  if ( isNotEmpty<ConstIterator>(i,end) ) {
424 
425  //backward extension
426  ConstIterator it( i ); ++it;
427  ConstReverseIterator rit( it );
428  ConstReverseIterator rend( begin );
429  ReverseSegmentComputer r( s.getReverse() );
430  longestSegment(r, rit, rend);
431 
432  //forward extension
433  ConstIterator it2( r.end().base() );
434  longestSegment(s, it2, end);
435 
436  }
437 
438 }
439 
448 template <typename SC>
449 void firstMaximalSegment(SC& s,
450  const typename SC::ConstIterator& i,
451  const typename SC::ConstIterator& begin,
452  const typename SC::ConstIterator& end,
453  DGtal::BidirectionalSegmentComputer)
454 {
455  s.init(i);
456 
457  oppositeEndMaximalExtension(s, begin);
458  maximalExtension(s, end);
459 }
460 
470 template <typename SC>
471 void firstMaximalSegment(SC& s,
472  const typename SC::ConstIterator& i,
473  const typename SC::ConstIterator& begin,
474  const typename SC::ConstIterator& end,
475  DGtal::DynamicSegmentComputer)
476 {
477  firstMaximalSegment(s,i,begin,end,DGtal::ForwardSegmentComputer() );
478 }
479 
489 template <typename SC>
490 void firstMaximalSegment(SC& s,
491  const typename SC::ConstIterator& i,
492  const typename SC::ConstIterator& begin,
493  const typename SC::ConstIterator& end,
494  DGtal::DynamicBidirectionalSegmentComputer)
495 {
496  firstMaximalSegment(s,i,begin,end,DGtal::BidirectionalSegmentComputer() );
497 }
498 
507 template <typename SC>
508 void firstMaximalSegment(SC& s,
509  const typename SC::ConstIterator& i,
510  const typename SC::ConstIterator& begin,
511  const typename SC::ConstIterator& end )
512 {
513  firstMaximalSegment<SC>(s, i, begin, end,
514 typename DGtal::SegmentComputerTraits<SC>::Category() );
515 }
516 
519 
528 template <typename SC>
529 void mostCenteredMaximalSegment(SC& s,
530  const typename SC::ConstIterator& i,
531  const typename SC::ConstIterator& begin,
532  const typename SC::ConstIterator& end,
533  DGtal::ForwardSegmentComputer )
534 {
535 
536  typedef typename SC::ConstIterator ConstIterator;
537  typedef typename SC::Reverse ReverseSegmentComputer;
538  typedef typename ReverseSegmentComputer::ConstIterator ConstReverseIterator;
539 
540  //get the first maximal segment passing through i
541 
542  firstMaximalSegment( s, i, begin, end, DGtal::ForwardSegmentComputer() );
543 
544  //get the next maximal segment while i is not at the middle of
545  //the current maximal segment.
546 
547  ConstIterator k( s.begin() );
548  while ( k != i ) {
549 
550  if ( isNotEmpty<ConstIterator>(s.end(),end) ) {
551 
552  //backward extension
553  ConstIterator it( s.end() ); ++it;
554  ConstReverseIterator rit( it );
555  ConstReverseIterator rend( s.begin() );
556  ReverseSegmentComputer r( s.getReverse() );
557  longestSegment(r, rit, rend);
558  ConstIterator newBegin = r.end().base();
559  ASSERT( newBegin != s.begin() );
560 
561  while ( ( k != getMiddleIterator(newBegin, s.end() ) )
562  &&( k != i ) ) {
563  ++k;
564  }
565  if ( k != i ) {
566 
567  //get the next maximal segment
568  longestSegment(s, newBegin, end);
569 
570  }
571 
572  } else {
573  k = i;
574  }
575  }
576 }
577 
586 template <typename SC>
587 void mostCenteredMaximalSegment(SC& s,
588  const typename SC::ConstIterator& i,
589  const typename SC::ConstIterator& begin,
590  const typename SC::ConstIterator& end,
591  DGtal::BidirectionalSegmentComputer)
592 {
593 
594  if ( (isNotEmpty(i,end)) || (isNotEmpty(i,begin)) ) {
595 
596  s.init(i);
597 
598  //symmetric extension
599  if ( (isNotEmpty(i,end)) && (isNotEmpty(i,begin)) ) {
600  maximalSymmetricExtension(s, begin, end);
601  }
602 
603  //forward extension
604  maximalExtension(s, end);
605 
606  //backward extension
607  oppositeEndMaximalExtension(s, begin);
608 
609  }
610 
611 }
612 
622 template <typename SC>
623 void mostCenteredMaximalSegment(SC& s,
624  const typename SC::ConstIterator& i,
625  const typename SC::ConstIterator& begin,
626  const typename SC::ConstIterator& end,
627  DGtal::DynamicSegmentComputer)
628 {
629  mostCenteredMaximalSegment(s,i,begin,end,DGtal::ForwardSegmentComputer() );
630 }
631 
641 template <typename SC>
642 void mostCenteredMaximalSegment(SC& s,
643  const typename SC::ConstIterator& i,
644  const typename SC::ConstIterator& begin,
645  const typename SC::ConstIterator& end,
646  DGtal::DynamicBidirectionalSegmentComputer)
647 {
648  mostCenteredMaximalSegment(s,i,begin,end,DGtal::BidirectionalSegmentComputer() );
649 }
650 
659 template <typename SC>
660 void mostCenteredMaximalSegment(SC& s,
661  const typename SC::ConstIterator& i,
662  const typename SC::ConstIterator& begin,
663  const typename SC::ConstIterator& end )
664 {
665  mostCenteredMaximalSegment<SC>(s, i, begin, end,
666 typename DGtal::SegmentComputerTraits<SC>::Category() );
667 }
668 
671 
680 template <typename SC>
681 void lastMaximalSegment(SC& s,
682  const typename SC::ConstIterator& i,
683  const typename SC::ConstIterator& begin,
684  const typename SC::ConstIterator& end,
685  DGtal::ForwardSegmentComputer )
686 {
687 
688  typedef typename SC::ConstIterator ConstIterator;
689  typedef typename SC::Reverse ReverseSegmentComputer;
690  typedef typename ReverseSegmentComputer::ConstIterator ConstReverseIterator;
691 
692  //forward extension
693  ConstIterator j( i );
694  longestSegment(s, j, end);
695 
696  //backward extension
697  ConstIterator it( s.end() );
698  ConstReverseIterator rit( it );
699  ConstReverseIterator rend( begin );
700  ReverseSegmentComputer r( s.getReverse() );
701  longestSegment(r, rit, rend);
702 
703  //forward extension
704  ConstIterator it2( r.end().base() );
705  longestSegment(s, it2, end);
706 }
707 
716 template <typename SC>
717 void lastMaximalSegment(SC& s,
718  const typename SC::ConstIterator& i,
719  const typename SC::ConstIterator& begin,
720  const typename SC::ConstIterator& end,
721  BidirectionalSegmentComputer)
722 {
723  s.init(i);
724 
725  maximalExtension(s, end);
726  oppositeEndMaximalExtension(s, begin);
727 }
728 
738 template <typename SC>
739 void lastMaximalSegment(SC& s,
740  const typename SC::ConstIterator& i,
741  const typename SC::ConstIterator& begin,
742  const typename SC::ConstIterator& end,
743  DGtal::DynamicSegmentComputer)
744 {
745  lastMaximalSegment(s,i,begin,end,DGtal::ForwardSegmentComputer() );
746 }
747 
757 template <typename SC>
758 void lastMaximalSegment(SC& s,
759  const typename SC::ConstIterator& i,
760  const typename SC::ConstIterator& begin,
761  const typename SC::ConstIterator& end,
762  DGtal::DynamicBidirectionalSegmentComputer)
763 {
764  lastMaximalSegment(s,i,begin,end,DGtal::BidirectionalSegmentComputer() );
765 }
766 
775 template <typename SC>
776 void lastMaximalSegment(SC& s,
777  const typename SC::ConstIterator& i,
778  const typename SC::ConstIterator& begin,
779  const typename SC::ConstIterator& end )
780 {
781  lastMaximalSegment<SC>(s, i, begin, end,
782 typename DGtal::SegmentComputerTraits<SC>::Category() );
783 }
784 
787 
796 template <typename SC>
797 void nextMaximalSegment(SC& s,
798  const typename SC::ConstIterator& end,
799  DGtal::ForwardSegmentComputer )
800 {
801  firstMaximalSegment(s, s.end(), s.begin(), end, ForwardSegmentComputer() );
802 }
803 
812 template <typename SC>
813 void nextMaximalSegment(SC& s,
814  const typename SC::ConstIterator& end,
815  DGtal::BidirectionalSegmentComputer)
816 {
817  firstMaximalSegment(s, s.end(), s.begin(), end, DGtal::BidirectionalSegmentComputer() );
818 }
819 
827 template <typename SC>
828 void nextMaximalSegment(SC& s,
829  const typename SC::ConstIterator& end,
830  DGtal::DynamicSegmentComputer)
831 {
832  typedef typename SC::ConstIterator ConstIterator;
833 
834  //rectract
835  maximalRetraction(s, end);
836 
837  //intersection test
838  ConstIterator i( s.begin() ); ++i;
839  //if the intersection between the two
840  // consecutive maximal segments is empty
841  if ( i == s.end() ) {
842  if ( isNotEmpty<ConstIterator>(i, end) ) {
843  ++i;
844  s.init(i);
845  }
846  }
847 
848  //extend
849  maximalExtension(s, end);
850 }
851 
860 template <typename SC>
861 void nextMaximalSegment(SC& s,
862  const typename SC::ConstIterator& end,
863  DGtal::DynamicBidirectionalSegmentComputer)
864 {
865  nextMaximalSegment(s, end, DGtal::DynamicSegmentComputer() );
866 }
867 
875 template <typename SC>
876 void nextMaximalSegment(SC& s,
877  const typename SC::ConstIterator& end )
878 {
879  nextMaximalSegment<SC>(s, end,
880 typename DGtal::SegmentComputerTraits<SC>::Category() );
881 }
882 
885 
894 template <typename SC>
895 void previousMaximalSegment(SC& s,
896  const typename SC::ConstIterator& begin,
897  DGtal::ForwardSegmentComputer )
898 {
899  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) )
900  lastMaximalSegment(s, --s.begin(), begin, s.end(), DGtal::ForwardSegmentComputer() );
901 }
902 
911 template <typename SC>
912 void previousMaximalSegment(SC& s,
913  const typename SC::ConstIterator& begin,
914  DGtal::BidirectionalSegmentComputer)
915 {
916  if ( isNotEmpty<typename SC::ConstIterator>(s.begin(),begin) )
917  lastMaximalSegment(s, --s.begin(), begin, s.end(), DGtal::BidirectionalSegmentComputer() );
918 }
919 
927 template <typename SC>
928 void previousMaximalSegment(SC& s,
929  const typename SC::ConstIterator& begin,
930  DGtal::DynamicSegmentComputer)
931 {
932 
933  typedef typename SC::ConstIterator ConstIterator;
934 
935  //rectract
936  oppositeEndMaximalRetraction(s, begin);
937 
938  //intersection test
939  ConstIterator i( s.end() ); --i;
940  //if the intersection between the two
941  // consecutive maximal segments is empty
942  if ( i == s.begin() ) {
943  if ( isNotEmpty<ConstIterator>(i, begin) ) {
944  --i;
945  s.init(i);
946  }
947  }
948 
949  //extend
950  oppositeEndMaximalExtension(s, begin);
951 
952 }
953 
962 template <typename SC>
963 void previousMaximalSegment(SC& s,
964  const typename SC::ConstIterator& end,
965  DGtal::DynamicBidirectionalSegmentComputer)
966 {
967  previousMaximalSegment(s, end, DGtal::DynamicSegmentComputer() );
968 }
969 
977 template <typename SC>
978 void previousMaximalSegment(SC& s,
979  const typename SC::ConstIterator& begin )
980 {
981  previousMaximalSegment(s, begin,
982 typename DGtal::SegmentComputerTraits<SC>::Category() );
983 }
984 
985 } // namespace DGtal
986 
987 
988 
989 // //
991 
992 #endif // !defined SegmentComputerUtils_h
993 
994 #undef SegmentComputerUtils_RECURSES
995 #endif // else defined(SegmentComputerUtils_RECURSES)
ConstIterator
MyDigitalSurface::ConstIterator ConstIterator
Definition: greedy-plane-segmentation-ex2.cpp:93
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition: ClosedIntegerHalfPlane.h:49
DGtal::oppositeEndMaximalRetraction
void oppositeEndMaximalRetraction(SC &s, const typename SC::ConstIterator &begin)
Definition: SegmentComputerUtils.h:341
DGtal::lastMaximalSegment
void lastMaximalSegment(SC &s, const typename SC::ConstIterator &i, const typename SC::ConstIterator &begin, const typename SC::ConstIterator &end, DGtal::ForwardSegmentComputer)
Definition: SegmentComputerUtils.h:681
DGtal::mostCenteredMaximalSegment
void mostCenteredMaximalSegment(SC &s, const typename SC::ConstIterator &i, const typename SC::ConstIterator &begin, const typename SC::ConstIterator &end, DGtal::ForwardSegmentComputer)
Definition: SegmentComputerUtils.h:529
DGtal::longestSegment
void longestSegment(SC &s, const typename SC::ConstIterator &i, const typename SC::ConstIterator &end, IteratorType)
Definition: SegmentComputerUtils.h:359
DGtal::oppositeEndMaximalExtension
void oppositeEndMaximalExtension(SC &s, const typename SC::ConstIterator &begin, IteratorType)
Definition: SegmentComputerUtils.h:198
DGtal::maximalExtension
void maximalExtension(SC &s, const typename SC::ConstIterator &end, IteratorType)
Definition: SegmentComputerUtils.h:164
DGtal::isNotEmpty
bool isNotEmpty(const IC &itb, const IC &ite)
DGtal::getMiddleIterator
IC getMiddleIterator(const IC &itb, const IC &ite, RandomAccessCategory)
Definition: SegmentComputerUtils.h:87
DGtal::nextMaximalSegment
void nextMaximalSegment(SC &s, const typename SC::ConstIterator &end, DGtal::ForwardSegmentComputer)
Definition: SegmentComputerUtils.h:797
DGtal::maximalRetraction
void maximalRetraction(SC &s, const typename SC::ConstIterator &end)
Definition: SegmentComputerUtils.h:323
DGtal::maximalSymmetricExtension
bool maximalSymmetricExtension(SC &s, const typename SC::ConstIterator &begin, const typename SC::ConstIterator &end, IteratorType)
Definition: SegmentComputerUtils.h:236
DGtal::previousMaximalSegment
void previousMaximalSegment(SC &s, const typename SC::ConstIterator &begin, DGtal::ForwardSegmentComputer)
Definition: SegmentComputerUtils.h:895
DGtal::firstMaximalSegment
void firstMaximalSegment(SC &s, const typename SC::ConstIterator &i, const typename SC::ConstIterator &begin, const typename SC::ConstIterator &end, DGtal::ForwardSegmentComputer)
Definition: SegmentComputerUtils.h:412
DGtal::IteratorCirculatorTraits::Category
ToDGtalCategory< typename boost::iterator_category< IC >::type >::Category Category
Definition: IteratorCirculatorTraits.h:301
DGtal::SegmentComputerTraits
Aim: Provides the category of the segment computer {ForwardSegmentComputer,BidirectionalSegmentComp...
Definition: SegmentComputerUtils.h:71
DGtal::SegmentComputerTraits::Category
ForwardSegmentComputer Category
Definition: SegmentComputerUtils.h:72
Generated on Tue Jun 1 2021 17:05:39 for DGtal by doxygen 1.9.1