DGtal 1.4.0
Loading...
Searching...
No Matches
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
47namespace DGtal
48{
49
51// Categories
52 struct ForwardSegmentComputer{};
53 struct BidirectionalSegmentComputer{};
54 struct DynamicSegmentComputer{};
55 struct DynamicBidirectionalSegmentComputer{};
56
57
59
69//default
70template <typename SC>
71struct 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
86template<typename IC>
87IC 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
99template<typename IC>
100IC 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
121template<typename IC>
122IC 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}
150template<typename IC>
151IC getMiddleIterator(const IC& itb, const IC& ite) {
152 typedef typename IteratorCirculatorTraits<IC>::Category Category;
153 return getMiddleIterator(itb, ite, Category() );
154}
155
158
159
163template <typename SC>
164void 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
173template <typename SC>
174void 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}
187template <typename SC>
188void 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
197template <typename SC>
198void 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
208template <typename SC>
209void 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
224template <typename SC>
225void 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
235template <typename SC>
236bool 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
269template <typename SC>
270bool 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
304template <typename SC>
305bool 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
322template <typename SC>
323void 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
340template <typename SC>
341void 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
358template <typename SC>
359void 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
373template <typename SC>
374void 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
390template <typename SC>
391void 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
411template <typename SC>
412void 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
448template <typename SC>
449void 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
470template <typename SC>
471void 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
489template <typename SC>
490void 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
507template <typename SC>
508void 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,
514typename DGtal::SegmentComputerTraits<SC>::Category() );
515}
516
519
528template <typename SC>
529void 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
586template <typename SC>
587void 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
622template <typename SC>
623void 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
641template <typename SC>
642void 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
659template <typename SC>
660void 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,
666typename DGtal::SegmentComputerTraits<SC>::Category() );
667}
668
671
680template <typename SC>
681void 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
716template <typename SC>
717void 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
738template <typename SC>
739void 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
757template <typename SC>
758void 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
775template <typename SC>
776void 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,
782typename DGtal::SegmentComputerTraits<SC>::Category() );
783}
784
787
796template <typename SC>
797void nextMaximalSegment(SC& s,
798 const typename SC::ConstIterator& end,
799 DGtal::ForwardSegmentComputer )
800{
801 firstMaximalSegment(s, s.end(), s.begin(), end, ForwardSegmentComputer() );
802}
803
812template <typename SC>
813void 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
827template <typename SC>
828void 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
860template <typename SC>
861void nextMaximalSegment(SC& s,
862 const typename SC::ConstIterator& end,
863 DGtal::DynamicBidirectionalSegmentComputer)
864{
865 nextMaximalSegment(s, end, DGtal::DynamicSegmentComputer() );
866}
867
875template <typename SC>
876void nextMaximalSegment(SC& s,
877 const typename SC::ConstIterator& end )
878{
879 nextMaximalSegment<SC>(s, end,
880typename DGtal::SegmentComputerTraits<SC>::Category() );
881}
882
885
894template <typename SC>
895void 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
911template <typename SC>
912void 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
927template <typename SC>
928void 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
962template <typename SC>
963void previousMaximalSegment(SC& s,
964 const typename SC::ConstIterator& end,
965 DGtal::DynamicBidirectionalSegmentComputer)
966{
967 previousMaximalSegment(s, end, DGtal::DynamicSegmentComputer() );
968}
969
977template <typename SC>
978void previousMaximalSegment(SC& s,
979 const typename SC::ConstIterator& begin )
980{
981 previousMaximalSegment(s, begin,
982typename 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< typenameboost::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