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.
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.
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/>.
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
24 * @brief Implementation of inline methods defined in FP.h
26 * This file is part of the DGtal library.
30//////////////////////////////////////////////////////////////////////////////
32//////////////////////////////////////////////////////////////////////////////
34///////////////////////////////////////////////////////////////////////////////
35// IMPLEMENTATION of inline methods.
36///////////////////////////////////////////////////////////////////////////////
38///////////////////////////////////////////////////////////////////////////////
39// ----------------------- Standard services ------------------------------
41template <typename TIterator, typename TInteger, int connectivity>
43DGtal::FP<TIterator,TInteger,connectivity>::
44FP(const TIterator& itb,
45 const TIterator& ite )
50template <typename TIterator, typename TInteger, int connectivity>
53DGtal::FP<TIterator,TInteger,connectivity>::
54algorithm(const TIterator& itb,
55 const TIterator& ite )
57 if (isNotEmpty(itb,ite))
59 typedef typename IteratorCirculatorTraits<TIterator>::Type Type;
60 algorithm( itb, ite, Type() );
64template <typename TIterator, typename TInteger, int connectivity>
67DGtal::FP<TIterator,TInteger,connectivity>::
68algorithm(const TIterator& itb,
69 const TIterator& ite, IteratorType )
71 ASSERT(isNotEmpty(itb,ite));
73 /////////////////////////////////////// open
74 //list of successive upper (U) and lower (L)
76 std::list<Point> vTmpU, vTmpL;
77 vTmpU.push_back(*itb);
78 vTmpL.push_back(*itb);
81 DSSComputer longestDSS;
84 while ( (longestDSS.end() != ite)&&(longestDSS.extendFront()) )
86 //store the first upper leaning point
87 if (longestDSS.Uf() != vTmpU.back()) {
88 vTmpU.push_back(longestDSS.Uf());
90 //store the first lower leaning point
91 if (longestDSS.Lf() != vTmpL.back()) {
92 vTmpL.push_back(longestDSS.Lf());
96 //std::cerr << "First MS" << std::endl << longestDSS << std::endl;
98 typedef detail::DSSDecorator<DSSComputer> DSSDecorator;
99 DSSDecorator* adapter = 0; //adapter for the current DSS
101 if (longestDSS.end() != ite)
103 //if the curve is not straight
104 //it is either locally convex or concave at longestDSS.end()
105 adapter = initConvexityConcavity<DSSDecorator>( longestDSS );
108 if ( adapter->isInConvexPart() ) myPolygon = vTmpU;
109 else myPolygon = vTmpL;
110 ASSERT(myPolygon.size() > 0);
115 if ( !removingStep( adapter ) )
116 { //disconnected digital curve
117 throw InputException();
119 go = addingStep( adapter, ite );
123 adapter = initConvexityConcavity<DSSDecorator>( longestDSS );
130 //the curve is assumed to be convex
133 adapter = new detail::DSSDecorator4ConvexPart<DSSComputer>(longestDSS);
137 //store the last leaning point
138 //if the first and last leaning points
139 //of the MS are not confounded
140 if (adapter->firstLeaningPoint() != adapter->lastLeaningPoint()) {
141 myPolygon.push_back(adapter->lastLeaningPoint());
145 while ( longestDSS.retractBack() ) {
146 //store the last leaning point
147 if (adapter->lastLeaningPoint() != myPolygon.back()) {
148 myPolygon.push_back(adapter->lastLeaningPoint());
152 ASSERT(adapter);//had to be allocated
156template <typename TIterator, typename TInteger, int connectivity>
159DGtal::FP<TIterator,TInteger,connectivity>::
160algorithm(const TIterator& itb,
161 const TIterator& ite, CirculatorType )
163 ASSERT(isNotEmpty(itb,ite)); boost::ignore_unused_variable_warning(ite);
165 /////////////////////////// closed
167 DSSComputer currentDSS;
168 currentDSS.init( itb );
170 while ( currentDSS.extendFront() ) {}
172 while ( currentDSS.extendBack() ) {}
175 typedef detail::DSSDecorator<DSSComputer> DSSDecorator;
176 DSSDecorator* adapter = 0; //adapter for the current DSS
177 adapter = initConvexityConcavity<DSSDecorator>( currentDSS );
179 if (adapter->firstLeaningPoint() == adapter->lastLeaningPoint()) {
180 myPolygon.push_back( adapter->lastLeaningPoint() );
181 }//stored in removingStep function otherwise
184 DSSComputer firstMS = currentDSS;
186 //since there are more than 2 MS (closed case)
187 //but no more than 2 MS sharing a leaning point
188 //at the same position
189 if ( !removingStep( adapter ) )
190 { //disconnected digital curve
191 throw InputException();
193 addingStep( adapter );
198 adapter = initConvexityConcavity<DSSDecorator>( currentDSS );
200 if ( !removingStep( adapter ) )
201 { //disconnected digital curve
202 throw InputException();
204 addingStep( adapter );
205 if (currentDSS == firstMS)
206 { //stop and remove the last point to avoid a repetition
207 if (adapter->firstLeaningPoint() == myPolygon.front()) {
208 ASSERT( myPolygon.size() > 0 );
209 myPolygon.pop_back();
218template <typename TIterator, typename TInteger, int connectivity>
219template<typename Adapter>
222DGtal::FP<TIterator,TInteger,connectivity>
223::initConvexityConcavity( typename Adapter::DSS &aDSS )
226 ASSERT( aDSS.isExtendableFront() == false );
228 if ( aDSS.remainder( aDSS.end() ) < (aDSS.mu()) )
231 ::DSSDecorator4ConcavePart<typename Adapter::DSS>(aDSS);
236 ::DSSDecorator4ConvexPart<typename Adapter::DSS>(aDSS);
240template <typename TIterator, typename TInteger, int connectivity>
241template<typename Adapter>
244DGtal::FP<TIterator,TInteger,connectivity>
245::removingStep( Adapter* adapter )
248 ASSERT( adapter->isExtendableFront() == false );
250 //store the last leaning point
251 //if the first and last leaning points
252 //of the MS are not confounded
253 if (adapter->firstLeaningPoint() != adapter->lastLeaningPoint()) {
254 myPolygon.push_back(adapter->lastLeaningPoint());
258 while ( !adapter->isExtendableFront() ) {
259 //remove a point from the back
260 if ( adapter->retractBack() ) {
261 //store the last leaning point
262 ASSERT( myPolygon.size() > 0 );
263 if (adapter->lastLeaningPoint() != myPolygon.back()) {
264 myPolygon.push_back(adapter->lastLeaningPoint());
274template <typename TIterator, typename TInteger, int connectivity>
275template<typename Adapter>
278DGtal::FP<TIterator,TInteger,connectivity>
279::addingStep( Adapter* adapter,
280 const typename Adapter::DSS::ConstIterator& itEnd )
283 ASSERT( adapter->isExtendableFront() == true );
285 //remove the last leaning point
286 //if the first and last leaning points
287 //of the current DSS are not confounded
288 if (adapter->firstLeaningPoint() != adapter->lastLeaningPoint()) {
289 ASSERT( myPolygon.size() > 0 );
290 myPolygon.pop_back();
294 while ( (adapter->end() != itEnd)&&(adapter->extendFront()) ) {
295 //store the first leaning point
296 ASSERT( myPolygon.size() > 0 );
297 if (adapter->firstLeaningPoint() != myPolygon.back()) {
298 myPolygon.push_back(adapter->firstLeaningPoint());
302 return (adapter->end() != itEnd);
305template <typename TIterator, typename TInteger, int connectivity>
306template<typename Adapter>
309DGtal::FP<TIterator,TInteger,connectivity>
310::addingStep( Adapter* adapter )
313 ASSERT( adapter->isExtendableFront() == true );
315 //remove the last leaning point
316 //if the first and last leaning points
317 //of the current DSS are not confounded
318 if (adapter->firstLeaningPoint() != adapter->lastLeaningPoint()) {
319 ASSERT( myPolygon.size() > 0 );
320 myPolygon.pop_back();
324 while ( adapter->extendFront() ) {
325 //store the first leaning point
326 ASSERT( myPolygon.size() > 0 );
327 if (adapter->firstLeaningPoint() != myPolygon.back()) {
328 myPolygon.push_back(adapter->firstLeaningPoint());
334template <typename TIterator, typename TInteger, int connectivity>
336DGtal::FP<TIterator,TInteger,connectivity>::~FP()
340///////////////////////////////////////////////////////////////////////////////
341// Interface - public :
343template <typename TIterator, typename TInteger, int connectivity>
345const typename DGtal::FP<TIterator,TInteger,connectivity>::Polygon&
346DGtal::FP<TIterator,TInteger,connectivity>::polygon() const
351template <typename TIterator, typename TInteger, int connectivity>
354DGtal::FP<TIterator,TInteger,connectivity>::isClosed() const
356 //since the input digital curve has to be connected
357 return IsCirculator<TIterator>::value;
360template <typename TIterator, typename TInteger, int connectivity>
363DGtal::FP<TIterator,TInteger,connectivity>
364::isValid(const Point& a,const Point& b, const Point& c) const {
366 Vector e1 = b - a; //previous edge
367 Vector e2 = c - b; //next edge
369 if ( (quadrant(e1,1))&&(quadrant(e2,1)) ) {
371 } else if ( (quadrant(e1,2))&&(quadrant(e2,2)) ) {
373 } else if ( (quadrant(e1,3))&&(quadrant(e2,3)) ) {
375 } else if ( (quadrant(e1,4))&&(quadrant(e2,4)) ) {
383template <typename TIterator, typename TInteger, int connectivity>
386DGtal::FP<TIterator,TInteger,connectivity>::isValid() const
388 typedef typename Polygon::const_iterator I;
390 //not two consecutive confounded points
392 I it = myPolygon.begin();
393 if (it != myPolygon.end())
396 if (it != myPolygon.end())
398 while ( (it != myPolygon.end())&&(flag1) )
400 flag1 = (*itPrev != *it);
404 }//if only one point ok
407 //valid quadrant for all consecutive pairs of edges
409 if (myPolygon.size() >= 3) {
412 i = myPolygon.begin();
416 if ( isClosed() ) { ///////// closed
419 flag2 = isValid(myPolygon.back(),*i,*j);
421 while ( (k != myPolygon.end())&&(flag2) ) {
422 flag2 = isValid(*i,*j,*k);
427 flag2 = isValid(*i,*j,myPolygon.front());
429 } else { ////////////////////// open
432 while ( (k != myPolygon.end())&&(flag2) ) {
433 flag2 = isValid(*i,*j,*k);
438 }//special case of less than 3 points ok
440 return flag1 && flag2;
443template <typename TIterator, typename TInteger, int connectivity>
445typename DGtal::FP<TIterator,TInteger,connectivity>::Polygon::size_type
446DGtal::FP<TIterator,TInteger,connectivity>::size() const
448 return myPolygon.size();
452template <typename TIterator, typename TInteger, int connectivity>
453template <typename OutputIterator>
456DGtal::FP<TIterator,TInteger,connectivity>::copyFP(OutputIterator result) const {
457 typename Polygon::const_iterator i = myPolygon.begin();
458 while ( i != myPolygon.end() ) {
464template <typename TIterator, typename TInteger, int connectivity>
465template <typename OutputIterator>
468DGtal::FP<TIterator,TInteger,connectivity>::copyMLP(OutputIterator result) const {
472 unsigned int n = (unsigned int) myPolygon.size();
473 if (n < 3) { //special case < 3 points
475 typename Polygon::const_iterator i = myPolygon.begin();
476 for ( ; i!= myPolygon.end() ; ++i) {
477 *result++ = RealPoint( *i );
480 } else { //standard case
482 typename Polygon::const_iterator i, j, k;
483 i = myPolygon.begin();
487 if ( isClosed() ) { ///////// closed
490 *result++ = getRealPoint(myPolygon.back(),*i,*j);
492 while ( k != myPolygon.end() ) {
493 *result++ = getRealPoint(*i,*j,*k);
497 *result++ = getRealPoint(*i,*j,myPolygon.front());
499 } else { ////////////////////// open
502 *result++ = RealPoint( myPolygon.front() );
504 while ( k != myPolygon.end() ) {
505 *result++ = getRealPoint(*i,*j,*k);
509 *result++ = RealPoint( myPolygon.back() );
517template <typename TIterator, typename TInteger, int connectivity>
519DGtal::PointVector<2,double>
520DGtal::FP<TIterator,TInteger,connectivity>
521::getRealPoint (const Point& a,const Point& b, const Point& c) const {
527 Vector e1 = b - a; //previous edge
528 Vector e2 = c - b; //next edge
530 if ( (e1[0]*e2[1]-e1[1]*e2[0]) <= 0 ) {
533 if ( (quadrant(e1,1))&&(quadrant(e2,1)) ) {
534 shift = RealVector(0.5,-0.5);
535 } else if ( (quadrant(e1,2))&&(quadrant(e2,2)) ) {
536 shift = RealVector(-0.5,-0.5);
537 } else if ( (quadrant(e1,3))&&(quadrant(e2,3)) ) {
538 shift = RealVector(-0.5,0.5);
539 } else if ( (quadrant(e1,4))&&(quadrant(e2,4)) ) {
540 shift = RealVector(0.5,0.5);
542 ASSERT(false && "DGtal::FP<TIterator,TInteger,connectivity>::getRealPoint: not valid polygon" );
548 if ( (quadrant(e1,1))&&(quadrant(e2,1)) ) {
549 shift = RealVector(-0.5,0.5);
550 } else if ( (quadrant(e1,2))&&(quadrant(e2,2)) ) {
551 shift = RealVector(0.5,0.5);
552 } else if ( (quadrant(e1,3))&&(quadrant(e2,3)) ) {
553 shift = RealVector(0.5,-0.5);
554 } else if ( (quadrant(e1,4))&&(quadrant(e2,4)) ) {
555 shift = RealVector(-0.5,-0.5);
557 ASSERT(false && "DGtal::FP<TIterator,TInteger,connectivity>::getRealPoint: not valid polygon" );
562 return ( RealPoint(b) + shift );
565template <typename TIterator, typename TInteger, int connectivity>
568DGtal::FP<TIterator,TInteger,connectivity>
569::quadrant (const Vector& v, const int& q) const {
572 return ( (v[0]>=0)&&(v[1]>=0) );
574 return ( (v[0]>=0)&&(v[1]<=0) );
576 return ( (v[0]<=0)&&(v[1]<=0) );
578 return ( (v[0]<=0)&&(v[1]>=0) );
581 "DGtal::FP<TIterator,TInteger,connectivity>::quadrant: quadrant number should be 0,1,2 or 3" );
586///////////////////////////////////////////////////////////////////////////////
589template <typename TIterator, typename TInteger, int connectivity>
592DGtal::FP<TIterator,TInteger,connectivity>::className() const
598template <typename TIterator, typename TInteger, int connectivity>
601DGtal::FP<TIterator,TInteger,connectivity>::selfDisplay ( std::ostream & out ) const
603 out << "[FP]" << std::endl;
604 typename Polygon::const_iterator i = myPolygon.begin();
605 for ( ;i != myPolygon.end();++i)
607 out << "\t " << (*i) << std::endl;
609 out << "[end FP]" << std::endl;
616///////////////////////////////////////////////////////////////////////////////
617// Implementation of inline functions //
619template <typename TIterator, typename TInteger, int connectivity>
622DGtal::operator<< ( std::ostream & out,
623 const FP<TIterator,TInteger,connectivity> & object )
625 object.selfDisplay( out );
630///////////////////////////////////////////////////////////////////////////////