DGtal  1.5.beta
Preimage2D.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 Preimage2D.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 2010/10/26
23  *
24  * @brief Implementation of inline methods defined in Preimage2D.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 
42 template <typename Shape>
43 inline
44 DGtal::Preimage2D<Shape>::Preimage2D(
45  const Point & firstPoint,
46  const Point & secondPoint,
47  const Shape & aShape ): myShape(aShape)
48 {
49  myPHull.push_front(firstPoint);
50  myQHull.push_front(secondPoint);
51 }
52 
53 
54 
55 template <typename Shape>
56 inline
57 DGtal::Preimage2D<Shape>::~Preimage2D()
58 {
59 }
60 
61 template <typename Shape>
62 inline
63 DGtal::Preimage2D<Shape>::Preimage2D( const Preimage2D & other ): myShape(other.myShape)
64 {
65  myPHull = other.myPHull;
66  myQHull = other.myQHull;
67 }
68 
69 template <typename Shape>
70 inline
71 DGtal::Preimage2D<Shape>&
72 DGtal::Preimage2D<Shape>::operator=( const Preimage2D & other )
73 {
74  if ( this != &other )
75  {
76  myShape = other.myShape;
77  myPHull = other.myPHull;
78  myQHull = other.myQHull;
79  }
80  return *this;
81 }
82 
83 template <typename Shape>
84 inline
85 bool
86 DGtal::Preimage2D<Shape>::operator==( const Preimage2D & other ) const
87 {
88  if ( (std::equal(myPHull.begin(),myPHull.end(),other.myPHull.begin())
89  &&std::equal(myQHull.begin(),myQHull.end(),other.myQHull.begin()))
90  || (std::equal(myPHull.begin(),myPHull.end(),other.myPHull.rbegin())
91  &&std::equal(myQHull.begin(),myQHull.end(),other.myQHull.rbegin()))
92  )
93  return true;
94  else
95  return false;
96 }
97 
98 template <typename Shape>
99 inline
100 bool
101 DGtal::Preimage2D<Shape>::operator!=( const Preimage2D & other ) const
102 {
103  return !(*this == other);
104 }
105 
106 template <typename Shape>
107 inline
108 bool
109 DGtal::Preimage2D<Shape>::isLeftExteriorAtTheFront(
110  const Point & aP,
111  const Point & /*aQ*/)
112 {
113  //critical points
114  BackwardIterator PHullBack = myPHull.rbegin();
115  ForwardIterator QHullFront = myQHull.begin();
116 
117  //predicates definition from critical shapes
118  myShape.init(*PHullBack, *QHullFront);
119  PHullBackQHullFrontPred p1( myShape );
120 
121  return (!p1(aP));
122 }
123 
124 template <typename Shape>
125 inline
126 bool
127 DGtal::Preimage2D<Shape>::isLeftExteriorAtTheBack(
128  const Point & /*aP*/,
129  const Point & aQ)
130 {
131  //critical points
132  ForwardIterator QHullFront = myQHull.begin();
133  BackwardIterator PHullBack = myPHull.rbegin();
134 
135  //predicates definition from critical shapes
136  myShape.init(*QHullFront, *PHullBack);
137  QHullFrontPHullBackPred p2( myShape );
138 
139  return (!p2(aQ));
140 }
141 
142 template <typename Shape>
143 inline
144 bool
145 DGtal::Preimage2D<Shape>::isRightExteriorAtTheFront(
146  const Point & /*aP*/,
147  const Point & aQ)
148 {
149  //critical points
150  BackwardIterator QHullBack = myQHull.rbegin();
151  ForwardIterator PHullFront = myPHull.begin();
152 
153  //predicates definition from critical shapes
154  myShape.init(*QHullBack, *PHullFront);
155  QHullBackPHullFrontPred p2( myShape );
156 
157  return (!p2(aQ));
158 }
159 
160 template <typename Shape>
161 inline
162 bool
163 DGtal::Preimage2D<Shape>::isRightExteriorAtTheBack(
164  const Point & aP,
165  const Point & /*aQ*/)
166 {
167  //critical points
168  ForwardIterator PHullFront = myPHull.begin();
169  BackwardIterator QHullBack = myQHull.rbegin();
170 
171  //predicates definition from critical shapes
172  myShape.init(*PHullFront, *QHullBack);
173  PHullFrontQHullBackPred p1( myShape );
174 
175  return (!p1(aP));
176 }
177 
178 template <typename Shape>
179 inline
180 bool
181 DGtal::Preimage2D<Shape>::canBeAddedAtTheFront(
182  const Point & aP,
183  const Point & aQ)
184 {
185  //critical points
186  BackwardIterator PHullBack = myPHull.rbegin();
187  ForwardIterator QHullFront = myQHull.begin();
188  BackwardIterator QHullBack = myQHull.rbegin();
189  ForwardIterator PHullFront = myPHull.begin();
190 
191  //predicates definition from critical shapes
192  myShape.init(*PHullBack, *QHullFront);
193  PHullBackQHullFrontPred p1( myShape );
194  myShape.init(*QHullBack, *PHullFront);
195  QHullBackPHullFrontPred p2( myShape );
196 
197  return ( p1(aP) && p2(aQ) );
198 }
199 
200 template <typename Shape>
201 inline
202 bool
203 DGtal::Preimage2D<Shape>::canBeAddedAtTheBack(
204  const Point & aP,
205  const Point & aQ)
206 {
207 
208  //critical points
209  ForwardIterator PHullFront = myPHull.begin();
210  BackwardIterator QHullBack = myQHull.rbegin();
211  ForwardIterator QHullFront = myQHull.begin();
212  BackwardIterator PHullBack = myPHull.rbegin();
213 
214  //predicates definition from critical shapes
215  myShape.init(*PHullFront, *QHullBack);
216  PHullFrontQHullBackPred p1( myShape );
217  myShape.init(*QHullFront, *PHullBack);
218  QHullFrontPHullBackPred p2( myShape );
219 
220  return ( p1(aP) && p2(aQ) );
221 
222 }
223 
224 template <typename Shape>
225 inline
226 bool
227 DGtal::Preimage2D<Shape>::addFront(
228  const Point & aP,
229  const Point & aQ)
230 {
231 
232  bool isEmpty = false;
233 
234  //critical points
235  BackwardIterator PHullBack = myPHull.rbegin();
236  ForwardIterator QHullFront = myQHull.begin();
237  BackwardIterator QHullBack = myQHull.rbegin();
238  ForwardIterator PHullFront = myPHull.begin();
239 
240  //predicates definition from critical shapes
241  myShape.init(*PHullBack, *QHullFront);
242  PHullBackQHullFrontPred p1( myShape );
243  myShape.init(*QHullBack, *PHullFront);
244  QHullBackPHullFrontPred p2( myShape );
245 
246  if ( p1(aP) && p2(aQ) ) {
247  if ( p2(aP) ) { //constraint involved by aP
248 
249  //update myPHull
250  update<ForwardIterator,FrontPHullUpdatePred>
251  (aP, myPHull, PHullFront, myPHull.end());
252 
253  //add aP to myPHull
254  if (aP != *myPHull.begin()) myPHull.push_front(aP);
255 
256  //update myQHull
257  update<BackwardIterator,FrontQHullUpdatePred>
258  (aP, myQHull, QHullBack, myQHull.rend());
259 
260  } //else nothing to do
261 
262  if ( p1(aQ) ) { //constraint involved by aQ
263 
264  //update myQHull
265  update<ForwardIterator,FrontQHullUpdatePred>
266  (aQ, myQHull, QHullFront, myQHull.end());
267 
268  //add aQ to myQHull
269  if (aQ != *myQHull.begin()) myQHull.push_front(aQ);
270 
271  //update myPHull
272  update<BackwardIterator,FrontPHullUpdatePred>
273  (aQ, myPHull, PHullBack, myPHull.rend());
274 
275  } //else nothing to do
276 
277  } else isEmpty = true;
278 
279  return (!isEmpty);
280 }
281 
282 template <typename Shape>
283 inline
284 bool
285 DGtal::Preimage2D<Shape>::addBack(
286  const Point & aP,
287  const Point & aQ)
288 {
289 
290  bool isEmpty = false;
291 
292  //critical points
293  ForwardIterator PHullFront = myPHull.begin();
294  BackwardIterator QHullBack = myQHull.rbegin();
295  ForwardIterator QHullFront = myQHull.begin();
296  BackwardIterator PHullBack = myPHull.rbegin();
297 
298  //predicates definition from critical shapes
299  myShape.init(*PHullFront, *QHullBack);
300  PHullFrontQHullBackPred p1( myShape );
301  myShape.init(*QHullFront, *PHullBack);
302  QHullFrontPHullBackPred p2( myShape );
303 
304  if ( p1(aP) && p2(aQ) ) {
305  if ( p2(aP) ) { //constraint involved by aP
306 
307  //update myPHull
308  update<BackwardIterator,BackPHullUpdatePred>
309  (aP, myPHull, PHullBack, myPHull.rend());
310 
311  //add aP to myPHull
312  if (aP != *myPHull.rbegin()) myPHull.push_back(aP);
313 
314  //update myQHull
315  update<ForwardIterator,BackQHullUpdatePred>
316  (aP, myQHull, QHullFront, myQHull.end());
317 
318 
319  } //else nothing to do
320 
321  if ( p1(aQ) ) { //constraint involved by aQ
322 
323  //update myQHull
324  update<BackwardIterator,BackQHullUpdatePred>
325  (aQ, myQHull, QHullBack, myQHull.rend());
326 
327  //add aQ to myQHull
328  if (aQ != *myQHull.rbegin()) myQHull.push_back(aQ);
329 
330  //update myPHull
331  update<ForwardIterator,BackPHullUpdatePred>
332  (aQ, myPHull, PHullFront, myPHull.end());
333 
334  } //else nothing to do
335 
336  } else isEmpty = true;
337 
338  return (!isEmpty);
339 }
340 
341 
342 template <typename Shape>
343 template <typename Iterator, typename Predicate>
344 inline
345 void
346 DGtal::Preimage2D<Shape>::update(
347  const Point & aPoint,
348  Container & aContainer,
349  Iterator & anIterator,
350  const Iterator & anEndIterator)
351 {
352 
353  Point p, q;
354  q = *anIterator;
355  anIterator++;
356  if (anIterator != anEndIterator) {
357  p = *anIterator;
358  myShape.init(p,q);
359  Predicate pred( myShape );
360 
361  while ( (anIterator != anEndIterator) &&
362  (pred(aPoint)) ) {
363 
364  //deletion
365  anIterator--;
366 
367  anIterator =
368  DGtal::OpInSTLContainers<Container,Iterator>
369  ::erase(aContainer, anIterator);
370 
371  //update of pred
372  q = p;
373  anIterator++;
374  if (anIterator != anEndIterator) {
375  p = *anIterator;
376  myShape.init(p,q);
377  pred = Predicate( myShape );
378  }
379  }
380  }
381 
382 }
383 ///////////////////////////////////////////////////////////////////////////////
384 // Interface - public :
385 
386 template <typename Shape>
387 inline
388 std::string
389 DGtal::Preimage2D<Shape>::className() const
390 {
391  return "Preimage2D";
392 }
393 
394 template <typename Shape>
395 inline
396 void
397 DGtal::Preimage2D<Shape>::selfDisplay ( std::ostream & out ) const
398 {
399  out << "[Preimage2D]\n";
400  out << "first part: \n";
401  for (ConstForwardIterator i = myPHull.begin();
402  i != myPHull.end(); ++i) {
403  out << *i << ", ";
404  }
405  out << "\n";
406  out << "second part: \n";
407  for (ConstForwardIterator i = myQHull.begin();
408  i != myQHull.end(); ++i) {
409  out << *i << ", ";
410  }
411  out << "\n";
412 }
413 
414 template <typename Shape>
415 inline
416 bool
417 DGtal::Preimage2D<Shape>::isValid() const
418 {
419  return true;
420 }
421 
422 template <typename Shape>
423 inline
424 typename DGtal::Preimage2D<Shape>::Point
425 DGtal::Preimage2D<Shape>::Uf() const
426 {
427  return *myPHull.rbegin();
428 }
429 
430 template <typename Shape>
431 inline
432 typename DGtal::Preimage2D<Shape>::Point
433 DGtal::Preimage2D<Shape>::Ul() const
434 {
435  return *myPHull.begin();
436 }
437 
438 template <typename Shape>
439 inline
440 typename DGtal::Preimage2D<Shape>::Point
441 DGtal::Preimage2D<Shape>::Lf() const
442 {
443  return *myQHull.rbegin();
444 }
445 
446 template <typename Shape>
447 inline
448 typename DGtal::Preimage2D<Shape>::Point
449 DGtal::Preimage2D<Shape>::Ll() const
450 {
451  return *myQHull.begin();
452 }
453 
454 template <typename Shape>
455 inline
456 void
457 DGtal::Preimage2D<Shape>::getSeparatingStraightLine(
458  double& alpha,
459  double& beta,
460  double& gamma) const
461 {
462  //critical points
463  Point localUf = Uf();
464  Point localUl = Ul();
465  Point localLf = Lf();
466  Point localLl = Ll();
467 
468  //parameters
469  typedef typename Point::Coordinate Coordinate;
470 
471  double a = -NumberTraits<Coordinate>::castToDouble(localLl[1]-localUf[1]);
472  double b = NumberTraits<Coordinate>::castToDouble(localLl[0]-localUf[0]);
473  double c = -NumberTraits<Coordinate>::castToDouble(localUf[0])*a
474  -NumberTraits<Coordinate>::castToDouble(localUf[1])*b;
475 
476  double ap = -NumberTraits<Coordinate>::castToDouble(localUl[1]-localLf[1]);
477  double bp = NumberTraits<Coordinate>::castToDouble(localUl[0]-localLf[0]);
478  double cp = -NumberTraits<Coordinate>::castToDouble(localLf[0])*ap
479  -NumberTraits<Coordinate>::castToDouble(localLf[1])*bp;
480 
481  double x, y;
482  double det = (ap*b-bp*a);
483  if (det != 0)
484  {
485  //intersection point
486  x = -(b*cp-bp*c)/det;
487  y = -(a*cp-ap*c)/(-det);
488  //normalisation of (ap,bp) with respect to (a,b)
489  double l = std::sqrt(a*a + b*b);
490  double lp = std::sqrt(ap*ap + bp*bp);
491  double apn = ap/lp*l;
492  double bpn = bp/lp*l;
493  //slope bisector of (UfLl) and (UlLf)
494  alpha = (a+apn)/2.0;
495  beta = (b+bpn)/2.0;
496  //intercept
497  gamma = -alpha*x - beta*y;
498  }
499  else
500  {//parallel case
501  alpha = a;
502  beta = b;
503  gamma = c;
504  }
505 }
506 
507 
508 ///////////////////////////////////////////////////////////////////////////////
509 // Implementation of inline functions //
510 
511 template <typename Shape>
512 inline
513 std::ostream&
514 DGtal::operator<< ( std::ostream & out,
515  const Preimage2D<Shape> & object )
516 {
517  object.selfDisplay( out );
518  return out;
519 }
520 
521 // //
522 ///////////////////////////////////////////////////////////////////////////////
523 
524