DGtal  1.5.beta
StarShaped2D.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 StarShaped2D.ih
19  * @author David Coeurjolly (\c david.coeurjolly@liris.cnrs.fr )
20  * Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France
21  *
22  * @date 2011/04/12
23  *
24  * Implementation of inline methods defined in StarShaped2D.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 /////////////////////////////////////////////////////////////////////////////
43 // ------------------------- star-shaped services -------------------------
44 
45 /**
46  * @param p any point in the plane.
47  *
48  * @return 'true' if the point is inside the shape, 'false' if it
49  * is strictly outside.
50  */
51 template<typename TSpace>
52 inline
53 DGtal::Orientation
54 DGtal::StarShaped2D<TSpace>::orientation( const RealPoint& p ) const
55 {
56  RealPoint x_rel( x(parameter(p)) - center() );
57  RealPoint p_rel( p - center() );
58 
59  const double diff = p_rel.norm() - x_rel.norm();
60 
61  return isAlmostEqual(diff,0.) ? ON : (diff > 0. ? OUTSIDE : INSIDE);
62 }
63 
64 
65 /**
66  * @param t any angle between 0 and 2*Pi.
67  *
68  * @return the vector (x'(t),y'(t)) made unitary which is the unit
69  * tangent to the shape boundary.
70  */
71 template<typename TSpace>
72 inline
73 typename DGtal::StarShaped2D<TSpace>::RealPoint
74 DGtal::StarShaped2D<TSpace>::tangent( const double t ) const
75 {
76  const RealPoint tgt( xp(t) );
77  return tgt / tgt.norm();
78 }
79 
80 
81 /**
82  * @param t any angle between 0 and 2*Pi.
83  *
84  * @return the vector (x''(t),y''(t)) made unitary which is the unit
85  * normal to the shape boundary looking inside the shape.
86 b */
87 template<typename TSpace>
88 inline
89 typename DGtal::StarShaped2D<TSpace>::RealPoint
90 DGtal::StarShaped2D<TSpace>::normal( const double t ) const
91 {
92  RealPoint tgt( tangent(t) );
93  return RealPoint( -tgt[1], tgt[0] );
94 }
95 
96 
97 /**
98  * @param t any angle between 0 and 2*Pi.
99  *
100  * @return the algebraic curvature at point (x(t),y(t)), positive
101  * is convex, negative is concave when shape is to the left and
102  * the shape boundary is followed counterclockwise.
103  */
104 template<typename TSpace>
105 inline
106 double
107 DGtal::StarShaped2D<TSpace>::curvature( const double t ) const
108 {
109  RealPoint tgt( xp(t) );
110  RealPoint dt( xpp(t) );
111  const double norm = tgt.norm();
112  return - ( dt[0] * tgt[1] - dt[1] * tgt[0] ) / ( norm * norm * norm );
113 }
114 
115 
116 /**
117  * @param t1 any angle between 0 and 2*Pi.
118  * @param t2 any angle between 0 and 2*Pi, further from [t1].
119  * @param nb the number of points used to estimate the arclength between x(t1) and x(t2).
120  * @return the estimated arclength.
121  */
122 template<typename TSpace>
123 inline
124 double
125 DGtal::StarShaped2D<TSpace>::arclength( const double t1, double t2, const unsigned int nb ) const
126 {
127  while ( t2 < t1 ) t2 += 2.0*M_PI;
128 
129  RealPoint x0( x(t1) );
130  double l = 0.;
131  // JOL 2008/08/28
132  for ( unsigned int i = 1; i <= nb; ++i )
133  {
134  const double t = ((t2 - t1) * i) / nb;
135  const RealPoint x1( x(t1 + t) );
136  l += sqrt(
137  (x1[0] - x0[0]) * (x1[0] - x0[0])
138  + (x1[1] - x0[1]) * (x1[1] - x0[1])
139  );
140  x0 = x1;
141  }
142  return l;
143 }
144 
145 /**
146  * Return a point on the segment [inner;outer] that is at most \f$\epsilon\f$ from the shape in \f$L_2\f$ norm.
147  *
148  * @param inner a point that is inside the shape
149  * @param outer a point that is outside the shape
150  * @param epsilon error parameter
151  *
152  * @return the intersected point.
153  */
154 template <typename TSpace>
155 inline
156 typename DGtal::StarShaped2D<TSpace>::RealPoint
157 DGtal::StarShaped2D<TSpace>::findIntersection( const RealPoint& inner,
158  const RealPoint& outer,
159  const double epsilon ) const
160 {
161  const typename DGtal::StarShaped2D<TSpace>::RealPoint mid = RealPoint(0.5 * (inner + outer));
162 
163  // We found a point that is at distance epsilon from the shape
164  if((inner - outer).norm() < epsilon)
165  return mid;
166  // The point lies inside the shape
167  else if(orientation(mid) == Orientation::INSIDE)
168  return findIntersection( mid, outer, epsilon );
169  // The point is right onto the shape
170  else if(orientation(mid) == Orientation::ON)
171  return mid;
172  // The point lies outside the shape
173  else if(orientation(mid) == Orientation::OUTSIDE)
174  return findIntersection( inner, mid, epsilon );
175 
176  ASSERT( false ); //this should not be reached
177  return RealPoint(0., 0.);
178 }
179 
180 /**
181  * Return a point that lies between the projection of left and right and that is the closest regarding the \f$L_2\f$ norm
182  *
183  * @param p the point to be projected
184  * @param left a point that is supposed to be projected left of p (regarding the angle)
185  * @param right a point that is supposed to be projected right of p (regarding the angle)
186  * @param step precision of the approximation
187  *
188  * @return a point.
189  **/
190 template <typename TSpace>
191 inline
192 typename DGtal::StarShaped2D<TSpace>::RealPoint
193 DGtal::StarShaped2D<TSpace>::closestPointWithWitnesses( const RealPoint& p,
194  const RealPoint& left, const RealPoint& right, const int step ) const
195 {
196  if ( step == 0 )
197  return RealPoint(0., 0.);
198 
199  const double left_angl = parameter(left);
200  const double right_angl = parameter(right);
201 
202  std::vector<RealPoint> points;
203 
204  for( int i = 0; i < step; i++ )
205  {
206  double arc = fabs(right_angl - left_angl);
207  if(arc > M_PI) arc = 2 * M_PI - arc;
208  const double current_angl = fmod(left_angl + arc / step * i, 2 * M_PI);
209  points.push_back(x(current_angl));
210  }
211 
212  RealPoint p_return(points[0]);
213  double p_norm = (p_return - p).norm();
214 
215  for( unsigned int i = 1; i < points.size(); i++ )
216  {
217  const double p_norm_current = (points[i] - p).norm();
218  if ( p_norm_current < p_norm )
219  {
220  p_return = points[i];
221  p_norm = p_norm_current;
222  }
223  }
224 
225  return p_return;
226 }
227 
228 ///////////////////////////////////////////////////////////////////////////////
229 // Interface - public :
230 
231 /**
232  * Writes/Displays the object on an output stream.
233  * @param out the output stream where the object is written.
234  */
235 template <typename T>
236 inline
237 void
238 DGtal::StarShaped2D<T>::selfDisplay ( std::ostream & out ) const
239 {
240  out << "[StarShaped2D]";
241 }
242 
243 /**
244  * Checks the validity/consistency of the object.
245  * @return 'true' if the object is valid, 'false' otherwise.
246  */
247 template <typename T>
248 inline
249 bool
250 DGtal::StarShaped2D<T>::isValid() const
251 {
252  return true;
253 }
254 
255 
256 
257 ///////////////////////////////////////////////////////////////////////////////
258 // Implementation of inline functions //
259 
260 template <typename T>
261 inline
262 std::ostream&
263 DGtal::operator<< ( std::ostream & out,
264  const StarShaped2D<T> & object )
265 {
266  object.selfDisplay( out );
267  return out;
268 }
269 
270 // //
271 ///////////////////////////////////////////////////////////////////////////////
272 
273