DGtal  0.9.2
MelkmanConvexHull.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 MelkmanConvexHull.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 2013/12/20
23  *
24  * Implementation of inline methods defined in MelkmanConvexHull.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 // ----------------------------------------------------------------------------
40 template <typename TPoint, typename TOrientationFunctor>
41 inline
42 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::MelkmanConvexHull( Alias<Functor> aFunctor )
43  : myContainer(),
44  myBackwardPredicate( aFunctor ),
45  myForwardPredicate( aFunctor )
46 {
47 }
48 
49 // ----------------------------------------------------------------------------
50 template <typename TPoint, typename TOrientationFunctor>
51 inline
52 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::MelkmanConvexHull()
53  : myContainer(),
54  myBackwardPredicate(myDefaultFunctor),
55  myForwardPredicate(myDefaultFunctor)
56 {
57 }
58 
59 // ----------------------------------------------------------------------------
60 template <typename TPoint, typename TOrientationFunctor>
61 inline
62 void
63 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::add(const Point& aPoint)
64 {
65 
66  using namespace DGtal::functions::Hull2D;
67 
68  if (myContainer.size() < 4)
69  {
70  if (myContainer.size() == 0)
71  {
72  myFirstPoint = aPoint;
73 
74  myContainer.push_back( aPoint );
75  myContainer.push_front( aPoint );
76  }
77  else if (myContainer.size() == 2)
78  {
79  myContainer.pop_back();
80  myContainer.push_back( aPoint );
81  myContainer.push_front( aPoint );
82  }
83  else if (myContainer.size() == 3)
84  {
85  //required to deal with the case where the k first input points are aligned.
86  if ( !myBackwardPredicate( *boost::next(myContainer.rbegin()), myContainer.back(), aPoint ) )
87  myContainer.pop_back();
88  myContainer.push_back( aPoint );
89  if ( !myForwardPredicate( *boost::next(myContainer.begin()), myContainer.front(), aPoint ) )
90  myContainer.pop_front();
91  myContainer.push_front( aPoint );
92  }
93  }
94  else
95  {
96  if ( ( !myBackwardPredicate( *boost::next(myContainer.rbegin()), myContainer.back(), aPoint ) ||
97  !myForwardPredicate( *boost::next(myContainer.begin()), myContainer.front(), aPoint ) ) )
98  {
99  //backward scan
100  updateHullWithAdaptedStack( backStack(myContainer), aPoint, myBackwardPredicate );
101  myContainer.push_back( aPoint );
102 
103  //forward scan
104  updateHullWithAdaptedStack( frontStack(myContainer), aPoint, myForwardPredicate );
105  myContainer.push_front( aPoint );
106  }
107  }
108 }
109 
110 // ----------------------------------------------------------------------------
111 template <typename TPoint, typename TOrientationFunctor>
112 inline
113 typename DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::ConstIterator
114 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::begin() const
115 {
116  if (myContainer.size() == 0)
117  return myContainer.end();
118  else
119  return boost::next(myContainer.begin());
120 }
121 
122 // ----------------------------------------------------------------------------
123 template <typename TPoint, typename TOrientationFunctor>
124 inline
125 typename DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::ConstIterator
126 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::end() const
127 {
128  return myContainer.end();
129 }
130 
131 // ----------------------------------------------------------------------------
132 template <typename TPoint, typename TOrientationFunctor>
133 inline
134 void
135 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::selfDisplay ( std::ostream & out ) const
136 {
137  out << "[MelkmanConvexHull]" << " #";
138  if ( myContainer.size() == 0 )
139  out << " 0 " << std::endl;
140  else
141  out << myContainer.size() - 1 << std::endl;
142  std::copy( myContainer.begin(), myContainer.end(),
143  std::ostream_iterator<Point>( out, "," ) );
144  out << std::endl;
145 }
146 
147 // ----------------------------------------------------------------------------
148 template <typename TPoint, typename TOrientationFunctor>
149 inline
150 bool
151 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::isValid() const
152 {
153  return true;
154 }
155 
156 // ----------------------------------------------------------------------------
157 template <typename TPoint, typename TOrientationFunctor>
158 inline
159 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>&
160 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::operator= (const Self & mch)
161 {
162  myContainer = mch.myContainer;
163  return *this;
164 }
165 
166 // ----------------------------------------------------------------------------
167 template <typename TPoint, typename TOrientationFunctor>
168 inline
169 const TPoint &
170 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::operator[](unsigned int i) const
171 {
172  ASSERT( i < myContainer.size() );
173  return myContainer[i];
174 }
175 
176 // ----------------------------------------------------------------------------
177 template <typename TPoint, typename TOrientationFunctor>
178 inline
179 unsigned int
180 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::size() const
181 {
182  // by definition the first and last points of the deque are the same.
183  return myContainer.size()-1;
184 
185 }
186 // ----------------------------------------------------------------------------
187 template <typename TPoint, typename TOrientationFunctor>
188 inline
189 void
190 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::clear()
191 {
192  myContainer.clear();
193 }
194 
195 // ----------------------------------------------------------------------------
196 template <typename TPoint, typename TOrientationFunctor>
197 inline
198 void
199 DGtal::MelkmanConvexHull<TPoint, TOrientationFunctor>::reverse()
200 {
201  // if convexhull is reduced into a single segment no need to reverse anything.
202  if(myContainer.size()<=3)
203  return;
204  TPoint theLast = myContainer.back();
205  myContainer.pop_back();
206  bool foundFirst = myContainer.back() == myFirstPoint;
207  while(!foundFirst){
208  myContainer.push_front(myContainer.back());
209  myContainer.pop_back();
210  foundFirst = myContainer.back() == myFirstPoint;
211  }
212  myContainer.push_front(myContainer.back());
213  myFirstPoint = theLast;
214 }
215 
216 
217 ///////////////////////////////////////////////////////////////////////////////
218 // Implementation of inline functions //
219 
220 template <typename TPoint, typename TOrientationFunctor>
221 inline
222 std::ostream&
223 DGtal::operator<< ( std::ostream & out,
224  const MelkmanConvexHull<TPoint, TOrientationFunctor> & object )
225 {
226  object.selfDisplay( out );
227  return out;
228 }
229 
230 ///////////////////////////////////////////////////////////////////////////////
231 template <typename ForwardIterator,
232  typename OutputIterator,
233  typename Functor >
234 inline
235 void DGtal::functions::Hull2D::
236 melkmanConvexHullAlgorithm(const ForwardIterator& itb, const ForwardIterator& ite,
237  OutputIterator res,
238  Functor& aFunctor )
239 {
240  BOOST_CONCEPT_ASSERT(( boost_concepts::ForwardTraversalConcept<ForwardIterator> ));
241  BOOST_CONCEPT_ASSERT(( boost_concepts::ReadableIteratorConcept<ForwardIterator> ));
242  typedef typename DGtal::IteratorCirculatorTraits<ForwardIterator>::Value Point;
243  BOOST_CONCEPT_ASSERT(( boost_concepts::IncrementableIteratorConcept<OutputIterator> ));
244  BOOST_CONCEPT_ASSERT(( boost_concepts::WritableIteratorConcept<OutputIterator,Point> ));
245 
246  if ( itb != ite )
247  {
248 
249  //convex hull computation with Melkman's algorithm
250  DGtal::MelkmanConvexHull<Point, Functor> ch( aFunctor );
251  for (ForwardIterator it = itb; it != ite; ++it)
252  ch.add( *it );
253 
254  std::copy( ch.begin(), ch.end(), res );
255  }
256 }
257 // //
258 ///////////////////////////////////////////////////////////////////////////////
259 
260