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