DGtal  1.5.beta
StabbingCircleComputer.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 StabbingCircleComputer.ih
19  * @author Tristan Roussillon (\c tristan.roussillon@liris.cnrs.fr )
20  * Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France
21  *
22  * @date 2011/09/26
23  *
24  * Implementation of inline methods defined in StabbingCircleComputer.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 //////////////////////////////////////////////////////////////////////////////
33 
34 ///////////////////////////////////////////////////////////////////////////////
35 // IMPLEMENTATION of inline methods.
36 ///////////////////////////////////////////////////////////////////////////////
37 
38 ///////////////////////////////////////////////////////////////////////////////
39 // ----------------------- Standard services ------------------------------
40 
41 template <typename TConstIterator>
42 inline
43 DGtal::StabbingCircleComputer<TConstIterator>::StabbingCircleComputer()
44  :myBegin(), myEnd(), mySegPtr(new StabbingLineComputer<ConstIterator>()),
45  myCircle(), myFlagIsInit(false)
46 {
47 }
48 
49 template <typename TConstIterator>
50 inline
51 DGtal::StabbingCircleComputer<TConstIterator>::StabbingCircleComputer( const Self& other )
52  :myBegin(other.myBegin), myEnd(other.myEnd), mySegPtr(other.mySegPtr),
53  myCircle(other.myCircle), myFlagIsInit(other.myFlagIsInit)
54 {
55 }
56 
57 template <typename TConstIterator>
58 inline
59 typename DGtal::StabbingCircleComputer<TConstIterator>::Self&
60 DGtal::StabbingCircleComputer<TConstIterator>::operator= ( const Self& other )
61 {
62  if ( this != &other )
63  {
64  myBegin = other.myBegin;
65  myEnd = other.myEnd;
66  mySegPtr = other.mySegPtr;
67  myCircle = other.myCircle;
68  myFlagIsInit = other.myFlagIsInit;
69  }
70  return *this;
71 }
72 
73 template <typename TConstIterator>
74 inline
75 DGtal::StabbingCircleComputer<TConstIterator>::~StabbingCircleComputer()
76 {
77 }
78 
79 template <typename TConstIterator>
80 inline
81 bool
82 DGtal::StabbingCircleComputer<TConstIterator>::operator==( const Self& other ) const
83 {
84  if (isValid()&&other.isValid())
85  {
86  bool flag1 = true;
87  {
88  ConstIterator first1 (myBegin);
89  ConstIterator first2 (other.myBegin);
90  while ( ( ( first1 != myEnd )
91  ||( first2 != other.myEnd ) )
92  && (flag1) )
93  {
94  Pair pair1( *first1 );
95  Pair pair2( *first2 );
96  if ( (pair1.first != pair2.first)||(pair1.second != pair2.second) ) flag1 = false;
97  ++first1; ++first2;
98  }
99  if ( (first1 != myEnd) || (first2 != other.myEnd) ) flag1 = false;
100  }
101  bool flag2 = true;
102  {
103  std::reverse_iterator<ConstIterator> rfirst1(myEnd);
104  ConstIterator first2 = other.myBegin;
105  while ( ( ( rfirst1 != std::reverse_iterator<ConstIterator>(myBegin) )
106  ||( first2 != other.myEnd ) )
107  && (flag2) )
108  {
109  Pair pair1( *rfirst1 );
110  Pair pair2( *first2 );
111  if ( (pair1.first != pair2.first)||(pair1.second != pair2.second) ) flag2 = false;
112  ++rfirst1; ++first2;
113  }
114  if ( (rfirst1 != std::reverse_iterator<ConstIterator>(myBegin))
115  || (first2 != other.myEnd) ) flag2 = false;
116  }
117 
118  return ( flag1 || flag2 );
119  }
120  else
121  {
122  return ( (!isValid()) && (!other.isValid()) );
123  }
124 }
125 
126 template <typename TConstIterator>
127 inline
128 bool
129 DGtal::StabbingCircleComputer<TConstIterator>::operator!=( const Self& other ) const
130 {
131  return !(*this == other);
132 }
133 
134 template <typename TConstIterator>
135 inline
136 typename DGtal::StabbingCircleComputer<TConstIterator>::Reverse
137 DGtal::StabbingCircleComputer<TConstIterator>::getReverse() const
138 {
139  return Reverse();
140 }
141 
142 
143 template <typename TConstIterator>
144 inline
145 typename DGtal::StabbingCircleComputer<TConstIterator>::Self
146 DGtal::StabbingCircleComputer<TConstIterator>::getSelf() const
147 {
148  return Self();
149 }
150 
151 
152 
153 ///////////////////////////////////////////////////////////////////////////////
154 // Interface - public :
155 
156 template <typename TConstIterator>
157 inline
158 bool
159 DGtal::StabbingCircleComputer<TConstIterator>::isValid() const
160 {
161  if ( mySegPtr.get() != 0 )
162  {
163  return mySegPtr->isValid();
164  }
165  else
166  {
167  return false;
168  }
169 }
170 
171 template <typename TConstIterator>
172 inline
173 typename DGtal::StabbingCircleComputer<TConstIterator>::ConstIterator
174 DGtal::StabbingCircleComputer<TConstIterator>::begin() const
175 {
176  return myBegin;
177 }
178 
179 template <typename TConstIterator>
180 inline
181 typename DGtal::StabbingCircleComputer<TConstIterator>::ConstIterator
182 DGtal::StabbingCircleComputer<TConstIterator>::end() const
183 {
184  return myEnd;
185 }
186 
187 template <typename TConstIterator>
188 inline
189 bool
190 DGtal::StabbingCircleComputer<TConstIterator>::isStraight() const
191 {
192  return !myFlagIsInit;
193 }
194 
195 template <typename TConstIterator>
196 inline
197 typename DGtal::StabbingCircleComputer<TConstIterator>::StabbingLineComputerPtr
198 DGtal::StabbingCircleComputer<TConstIterator>::getStabbingLineComputerPtr() const
199 {
200  return mySegPtr;
201 }
202 
203 template <typename TConstIterator>
204 inline
205 typename DGtal::StabbingCircleComputer<TConstIterator>::Circle
206 DGtal::StabbingCircleComputer<TConstIterator>::getSeparatingCircle() const
207 {
208  return myCircle;
209 }
210 
211 ///////////////////////////////////////////////////////////////////////////////
212 // Growth operations //
213 
214 template <typename TConstIterator>
215 template <typename TIterator>
216 inline
217 bool
218 DGtal::StabbingCircleComputer<TConstIterator>::isCircularlySeparable(
219  const TIterator& itb, const TIterator& ite,
220  const Point& aPole,
221  Point& Pf, Point& Pl, Point& Qf, Point& Ql)
222 {
223  ASSERT( itb != ite );
224  TIterator it( itb );
225  Pair currentPair( *it );
226 
227  //preimage of circles passing through aPole
228  CircleFrom2Points<Point> aCircle( aPole );
229  Preimage2D<CircleFrom2Points<Point> >
230  thePreimage( currentPair.first, currentPair.second, aCircle );
231 
232  bool isOK = true;
233  ++it;
234  if (it != ite)
235  { //if more than one pair
236  currentPair = *it;
237  if ( thePreimage.addFront(currentPair.first, currentPair.second) )
238  { //if CW oriented
239  isOK = true;
240  while ( (it != ite)&&(isOK) )
241  {
242  currentPair = *it;
243  isOK = thePreimage.addFront(currentPair.first, currentPair.second);
244  ++it;
245  }
246  }
247  else if ( thePreimage.addBack(currentPair.first, currentPair.second) )
248  { // if CCW oriented
249  isOK = true;
250  while ( (it != ite)&&(isOK) )
251  {
252  currentPair = *it;
253  isOK = thePreimage.addBack(currentPair.first, currentPair.second);
254  ++it;
255  }
256  } else isOK = false;
257 
258  } //if only one pair => circularly separable
259 
260  if (isOK)
261  {//points of support
262  Pf = thePreimage.Uf();
263  Pl = thePreimage.Ul();
264  Qf = thePreimage.Lf();
265  Ql = thePreimage.Ll();
266  return true;
267  } else return false;
268 }
269 
270 template <typename TConstIterator>
271 inline
272 void
273 DGtal::StabbingCircleComputer<TConstIterator>::init(const ConstIterator& anIt)
274 {
275  myFlagIsInit = false;
276 
277  //initialize the iterators
278  myBegin = anIt;
279  myEnd = anIt;
280  ++myEnd;
281 
282  //...the geometrical DSS
283  mySegPtr->init( anIt );
284 
285  //...the circle as degenerated
286  Pair aPair( *anIt);
287  myCircle = Circle(aPair.first, aPair.first, aPair.first);
288 }
289 
290 template <typename TConstIterator>
291 inline
292 bool
293 DGtal::StabbingCircleComputer<TConstIterator>::isExtendableFront()
294 {
295  ASSERT( mySegPtr.get() != 0 );
296  Pair aPair( *myEnd );
297  Point aP( aPair.first );
298  Point aQ( aPair.second );
299  bool isOK = false;
300 
301  if (myFlagIsInit)
302  { //initialized
303 
304  //predicates
305  PInCirclePred p1( myCircle );
306  QInCirclePred p2( myCircle );
307 
308  if ( p1(aP)&&p2(aQ) )
309  isOK = true;
310  else
311  { //checks if the separating circle can be updated
312  if (!p1(aP))
313  {
314  Point Pf, Pl, Qf, Ql;
315  if (isCircularlySeparable(myBegin,myEnd,aP,Pf,Pl,Qf,Ql))
316  isOK = true;
317  }
318  else if (!p2(aQ))
319  {
320  Point Pf, Pl, Qf, Ql;
321  if (isCircularlySeparable(myBegin,myEnd,aQ,Pf,Pl,Qf,Ql))
322  isOK = true;
323  }
324  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::isExtendableFront(): impossible case") );
325  }
326 
327  } else
328  { //not initialized yet
329 
330  if ( mySegPtr->extendFront() ) isOK = true;
331  else
332  {
333  Point Pf, Pl, Qf, Ql;
334  if (mySegPtr->isConvex())
335  { //convex part
336  if (isCircularlySeparable(myBegin,myEnd,aQ,Pf,Pl,Qf,Ql))
337  isOK = true;
338  }
339  else if (mySegPtr->isConcave())
340  { //concave part
341  if (isCircularlySeparable(myBegin,myEnd,aP,Pf,Pl,Qf,Ql))
342  isOK = true;
343  }
344  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::isExtendableFront(): impossible case") );
345  }
346  }
347 
348  return isOK;
349 }
350 
351 template <typename TConstIterator>
352 inline
353 bool
354 DGtal::StabbingCircleComputer<TConstIterator>::extendFront()
355 {
356  ASSERT( mySegPtr.get() != 0 );
357  Pair aPair( *myEnd );
358  Point aP( aPair.first );
359  Point aQ( aPair.second );
360  bool isOK = false;
361 
362  if (myFlagIsInit)
363  { //initialized
364 
365  //predicates
366  PInCirclePred p1( myCircle );
367  QInCirclePred p2( myCircle );
368 
369  if ( p1(aP)&&p2(aQ) )
370  isOK = true;
371  else
372  { //update separating circle
373  if (!p1(aP))
374  {
375  Point Pf, Pl, Qf, Ql;
376  if (isCircularlySeparable(myBegin,myEnd,aP,Pf,Pl,Qf,Ql))
377  {
378  myCircle.init(Pf,Ql,aP);
379  isOK = true;
380  }
381  }
382  else if (!p2(aQ))
383  {
384  Point Pf, Pl, Qf, Ql;
385  if (isCircularlySeparable(myBegin,myEnd,aQ,Pf,Pl,Qf,Ql))
386  {
387  myCircle.init(Qf,Pl,aQ);
388  isOK = true;
389  }
390  }
391  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::extendFront(): impossible case") );
392  }
393 
394  } else
395  { //not initialized yet
396 
397  if ( mySegPtr->extendFront() ) isOK = true;
398  else
399  {
400  Point Pf, Pl, Qf, Ql;
401  if (mySegPtr->isConvex())
402  { //convex part
403 
404  if (isCircularlySeparable(myBegin,myEnd,aQ,Pf,Pl,Qf,Ql))
405  {
406  myCircle.init(Qf,Pl,aQ);
407  myFlagIsInit = true;
408  isOK = true;
409  }
410  }
411  else if (mySegPtr->isConcave())
412  { //concave part
413 
414  if (isCircularlySeparable(myBegin,myEnd,aP,Pf,Pl,Qf,Ql))
415  {
416  myCircle.init(Pf,Ql,aP);
417  myFlagIsInit = true;
418  isOK = true;
419  }
420  }
421  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::extendFront(): impossible case") );
422  }
423  }
424 
425  if (isOK)
426  {
427  ++myEnd;
428  return true;
429  } else return false;
430 }
431 
432 template <typename TConstIterator>
433 inline
434 bool
435 DGtal::StabbingCircleComputer<TConstIterator>::isExtendableBack()
436 {
437  ASSERT( mySegPtr.get() != 0 );
438  ConstIterator it( myBegin );
439  --it;
440  Pair aPair( *it );
441  Point aP( aPair.first );
442  Point aQ( aPair.second );
443  bool isOK = false;
444 
445  if (myFlagIsInit)
446  { //initialized
447 
448  //predicates
449  PInCirclePred p1( myCircle );
450  QInCirclePred p2( myCircle );
451 
452  if ( p1(aP)&&p2(aQ) )
453  isOK = true;
454  else
455  { //update separating circle
456  if (!p1(aP))
457  {
458  Point Pf, Pl, Qf, Ql;
459  std::reverse_iterator<ConstIterator> ritb(myEnd);
460  std::reverse_iterator<ConstIterator> rite(myBegin);
461  if (isCircularlySeparable(ritb,rite,aP,Pf,Pl,Qf,Ql))
462  isOK = true;
463  }
464  else if (!p2(aQ))
465  {
466  Point Pf, Pl, Qf, Ql;
467  std::reverse_iterator<ConstIterator> ritb(myEnd);
468  std::reverse_iterator<ConstIterator> rite(myBegin);
469  if (isCircularlySeparable(ritb,rite,aQ,Pf,Pl,Qf,Ql))
470  isOK = true;
471  }
472  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::extendBack(): impossible case") );
473  }
474 
475  } else
476  { //not initialized yet
477 
478  if ( mySegPtr->extendBack() ) isOK = true;
479  else
480  {
481  Point Pf, Pl, Qf, Ql;
482  std::reverse_iterator<ConstIterator> ritb(myEnd);
483  std::reverse_iterator<ConstIterator> rite(myBegin);
484  if (mySegPtr->isOppositeEndConvex())
485  { //convex part
486  if (isCircularlySeparable(ritb,rite,aQ,Pf,Pl,Qf,Ql))
487  isOK = true;
488  }
489  else if (mySegPtr->isOppositeEndConcave())
490  { //concave part
491  if (isCircularlySeparable(ritb,rite,aP,Pf,Pl,Qf,Ql))
492  isOK = true;
493  }
494  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::extendBack(): impossible case") );
495  }
496  }
497 
498  return isOK;
499 }
500 
501 template <typename TConstIterator>
502 inline
503 bool
504 DGtal::StabbingCircleComputer<TConstIterator>::extendBack()
505 {
506  ASSERT( mySegPtr.get() != 0 );
507  ConstIterator it( myBegin );
508  --it;
509  Pair aPair( *it );
510  Point aP( aPair.first );
511  Point aQ( aPair.second );
512  bool isOK = false;
513 
514  if (myFlagIsInit)
515  { //initialized
516 
517  //predicates
518  PInCirclePred p1( myCircle );
519  QInCirclePred p2( myCircle );
520 
521  if ( p1(aP)&&p2(aQ) )
522  isOK = true;
523  else
524  { //update separating circle
525  if (!p1(aP))
526  {
527  Point Pf, Pl, Qf, Ql;
528  std::reverse_iterator<ConstIterator> ritb(myEnd);
529  std::reverse_iterator<ConstIterator> rite(myBegin);
530  if (isCircularlySeparable(ritb,rite,aP,Pf,Pl,Qf,Ql))
531  {
532  myCircle.init(aP,Pf,Ql);
533  isOK = true;
534  }
535  }
536  else if (!p2(aQ))
537  {
538  Point Pf, Pl, Qf, Ql;
539  std::reverse_iterator<ConstIterator> ritb(myEnd);
540  std::reverse_iterator<ConstIterator> rite(myBegin);
541  if (isCircularlySeparable(ritb,rite,aQ,Pf,Pl,Qf,Ql))
542  {
543  myCircle.init(aQ,Qf,Pl);
544  isOK = true;
545  }
546  }
547  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::extendBack(): impossible case") );
548  }
549 
550  } else
551  { //not initialized yet
552 
553  if ( mySegPtr->extendBack() ) isOK = true;
554  else
555  {
556  Point Pf, Pl, Qf, Ql;
557  std::reverse_iterator<ConstIterator> ritb(myEnd);
558  std::reverse_iterator<ConstIterator> rite(myBegin);
559  if (mySegPtr->isOppositeEndConvex())
560  { //convex part
561 
562  if (isCircularlySeparable(ritb,rite,aQ,Pf,Pl,Qf,Ql))
563  {
564  myCircle.init(aQ,Qf,Pl);
565  myFlagIsInit = true;
566  isOK = true;
567  }
568  }
569  else if (mySegPtr->isOppositeEndConcave())
570  { //concave part
571 
572  if (isCircularlySeparable(ritb,rite,aP,Pf,Pl,Qf,Ql))
573  {
574  myCircle.init(aP,Pf,Ql);
575  myFlagIsInit = true;
576  isOK = true;
577  }
578  }
579  else ASSERT( false && ("DGtal::StabbingCircleComputer<TConstIterator>::extendBack(): impossible case") );
580  }
581  }
582 
583  if (isOK)
584  {
585  myBegin = it;
586  return true;
587  } else return false;
588 }
589 
590 ///////////////////////////////////////////////////////////////////////////////
591 // Display :
592 
593 template <typename TConstIterator>
594 inline
595 void
596 DGtal::StabbingCircleComputer<TConstIterator>::selfDisplay ( std::ostream & out ) const
597 {
598  out << std::endl;
599  out << "[StabbingCircleComputer]" << std::endl;
600  if (isValid())
601  {
602  Pair firstPair( *myBegin );
603  out << "\t From " << firstPair.first << firstPair.second << std::endl;
604  ConstIterator it (myEnd);
605  --it;
606  Pair lastPair( *it );
607  out << "\t To " << lastPair.first << lastPair.second << std::endl;
608  if (myFlagIsInit)
609  out << myCircle << std::endl;
610  else
611  out << "infinite radius" << std::endl;
612  }
613  else
614  {
615  out << "\t not valid" << std::endl;
616  }
617  out << "[end of StabbingCircleComputer]" << std::endl;
618 }
619 
620 template <typename TConstIterator>
621 inline
622 std::string
623 DGtal::StabbingCircleComputer<TConstIterator>::className() const
624 {
625  return "StabbingCircleComputer";
626 }
627 
628 
629 ///////////////////////////////////////////////////////////////////////////////
630 // Implementation of inline functions //
631 
632 template <typename TConstIterator>
633 inline
634 std::ostream&
635 DGtal::operator<< ( std::ostream & out,
636  const StabbingCircleComputer<TConstIterator> & object )
637 {
638  object.selfDisplay( out );
639  return out;
640 }
641 
642 // //
643 ///////////////////////////////////////////////////////////////////////////////
644 
645