DGtal  1.2.0
ExactPredicateLpSeparableMetric.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
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 2012/11/02
23  *
24  * Implementation of inline methods defined in ExactLpSeparableMetric.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 template <typename T, DGtal::uint32_t p, typename P>
41 inline
42 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::ExactPredicateLpSeparableMetric()
43 {
44 }
45 //------------------------------------------------------------------------------
46 template <typename T, DGtal::uint32_t p, typename P>
47 inline
48 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::~ExactPredicateLpSeparableMetric()
49 {
50 }
51 //------------------------------------------------------------------------------
52 template <typename T, DGtal::uint32_t p, typename P>
53 inline
54 typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::RawValue
55 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::rawDistance (const Point &aP,
56  const Point &aQ) const
57 {
58  RawValue res= NumberTraits<RawValue>::ZERO;
59  for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
60  {
61  res += functions::power(static_cast<RawValue>(abs(aP[d]-aQ[d])), p);
62  }
63  return res;
64 }
65 //------------------------------------------------------------------------------
66 template <typename T, DGtal::uint32_t p, typename P>
67 inline
68 typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::Value
69 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::operator()(const Point &aP,
70  const Point &aQ) const
71 {
72  return std::pow( NumberTraits<RawValue>::castToDouble(rawDistance(aP,aQ)), 1.0/(double)p);
73 }
74 //------------------------------------------------------------------------------
75 template <typename T, DGtal::uint32_t p, typename P>
76 inline
77 DGtal::Closest
78 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::closest (const Point &origin,
79  const Point &first,
80  const Point &second) const
81 {
82  RawValue a=NumberTraits<RawValue>::ZERO,
83  b=NumberTraits<RawValue>::ZERO;
84 
85  a = rawDistance(origin,first);
86  b = rawDistance(origin,second);
87 
88  if (a<b)
89  return ClosestFIRST;
90  else
91  if (a>b)
92  return ClosestSECOND;
93  else
94  return ClosestBOTH;
95 }
96 //------------------------------------------------------------------------------
97 template <typename T, DGtal::uint32_t p, typename P>
98 inline
99 typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::Abscissa
100 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::binarySearchHidden(const Abscissa &udim,
101  const Abscissa &vdim,
102  const RawValue &nu,
103  const RawValue &nv,
104  const Abscissa &lower,
105  const Abscissa &upper) const
106 {
107  ASSERT( (nu + functions::power( static_cast<RawValue>(abs( udim - lower)), p)) <
108  (nv + functions::power( static_cast<RawValue>(abs( vdim - lower)), p)));
109 
110  //Recurrence stop
111  if ( (upper - lower) <= NumberTraits<Abscissa>::ONE)
112  {
113  //testing upper
114  RawValue nuUpdated = nu + functions::power( static_cast<RawValue>(abs( udim - upper )), p);
115  RawValue nvUpdated = nv + functions::power( static_cast<RawValue>(abs( vdim - upper )), p);
116  if (nuUpdated < nvUpdated)
117  return upper;
118  else
119  return lower;
120  }
121 
122  Abscissa mid = (lower + upper)/2;
123  RawValue nuUpdated = nu + functions::power( static_cast<RawValue>(abs( udim - mid )), p);
124  RawValue nvUpdated = nv + functions::power( static_cast<RawValue>(abs( vdim - mid )), p);
125 
126  //Recursive call
127  if ( nuUpdated < nvUpdated)
128  return binarySearchHidden(udim,vdim,nu,nv,mid,upper);
129  else
130  return binarySearchHidden(udim,vdim,nu,nv,lower,mid);
131 
132 }
133 //------------------------------------------------------------------------------
134 template <typename T, DGtal::uint32_t p , typename P>
135 inline
136 bool
137 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::hiddenBy(const Point &u,
138  const Point &v,
139  const Point &w,
140  const Point &startingPoint,
141  const Point &endPoint,
142  const typename Point::UnsignedComponent dim) const
143 {
144  //Interval bound for the binary search
145  Abscissa lower = startingPoint[dim];
146  Abscissa upper = endPoint[dim];
147 
148  //Partial norm computation (sum_{i!=dim} |u_i-v_i|^p
149  RawValue nu = NumberTraits<RawValue>::ZERO;
150  RawValue nv = NumberTraits<RawValue>::ZERO;
151  RawValue nw = NumberTraits<RawValue>::ZERO;
152  for(DGtal::Dimension i = 0 ; i < Point::dimension ; i++)
153  if (i != dim)
154  {
155  nu += functions::power ( static_cast<RawValue>(abs(u[i] - startingPoint[i])), p);
156  nv += functions::power ( static_cast<RawValue>(abs(v[i] - startingPoint[i])), p);
157  nw += functions::power ( static_cast<RawValue>(abs(w[i] - startingPoint[i])), p);
158  }
159 
160  //Abscissa of voronoi edges
161  Abscissa uv,vw;
162  RawValue dv,dw,du,ddv,ddw;
163 
164  //checking distances to lower bound
165  du = nu + functions::power( static_cast<RawValue>(abs( u[dim] - lower)), p);
166  dv = nv + functions::power( static_cast<RawValue>(abs( v[dim] - lower)), p);
167  dw = nw + functions::power( static_cast<RawValue>(abs( w[dim] - lower)), p);
168 
169  //Precondition of binarySearchHidden is true
170  if (du < dv )
171  {
172  uv = binarySearchHidden(u[dim],v[dim],nu,nv,lower,upper);
173  if (dv < dw)
174  {
175  vw = binarySearchHidden(v[dim],w[dim],nv,nw,lower,upper); //precondition
176  return (uv > vw);
177  }
178 
179  if (dw > dv)
180  return true;
181  else
182  {
183  //check if uv + 1 is stricly in W
184 
185  //first, optimisation
186  if (uv == upper) return true;
187 
188  //distances at uv+1
189  ddv = nv + functions::power( static_cast<RawValue>(abs( v[dim] - uv -1)), p);
190  ddw = nw + functions::power( static_cast<RawValue>(abs( w[dim] - uv -1)), p);
191  if (ddw < ddv)
192  return true;
193  else
194  return false;
195  }
196  }
197  else // du >= dv
198  {
199  if (dv <= dw)
200  return false;
201  else
202  return true;
203  }
204 }
205 //------------------------------------------------------------------------------
206 template <typename T, DGtal::uint32_t p, typename P>
207 inline
208 void
209 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::selfDisplay ( std::ostream & out ) const
210 {
211  out << "[ExactPredicateLpSeparableMetric] p="<<p;
212 }
213 //------------------------------------------------------------------------------
214 template <typename T, DGtal::uint32_t p, typename P>
215 inline
216 bool
217 DGtal::ExactPredicateLpSeparableMetric<T,p,P>::isValid() const
218 {
219  return true;
220 }
221 //------------------------------------------------------------------------------
222 template <typename T, DGtal::uint32_t p, typename P>
223 inline
224 std::ostream&
225 DGtal::operator<< ( std::ostream & out,
226  const ExactPredicateLpSeparableMetric<T,p,P> & object )
227 {
228  object.selfDisplay( out );
229  return out;
230 }
231 
232 ///////////////////////////////////////////////////////////////////////////////
233 // L_2 specialization //
234 ///////////////////////////////////////////////////////////////////////////////
235 
236 
237 // ----------------------- Standard services ------------------------------
238 template <typename T, typename P>
239 inline
240 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::ExactPredicateLpSeparableMetric()
241 {
242 }
243 //------------------------------------------------------------------------------
244 template <typename T, typename P>
245 inline
246 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::~ExactPredicateLpSeparableMetric()
247 {
248 }
249 //------------------------------------------------------------------------------
250 template <typename T, typename P>
251 inline
252 typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::RawValue
253 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::rawDistance (const Point &aP,
254  const Point &aQ) const
255 {
256  RawValue res= NumberTraits<RawValue>::ZERO;
257  for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
258  {
259  res += static_cast<RawValue>(aP[d]-aQ[d])*static_cast<RawValue>(aP[d]-aQ[d]);
260  }
261  return res;
262 }
263 //------------------------------------------------------------------------------
264 template <typename T, typename P>
265 inline
266 typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Value
267 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::local (const Point &/*aP*/,
268  const Vector &aDir) const
269 {
270  RawValue res= NumberTraits<RawValue>::ZERO;
271  for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
272  {
273  res += (static_cast<RawValue>(aDir[d]))*(static_cast<RawValue>(aDir[d]));
274  }
275  return std::pow( NumberTraits<RawValue>::castToDouble(res), 1.0/2.0);
276 }
277 //------------------------------------------------------------------------------
278 template <typename T, typename P>
279 inline
280 typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Value
281 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::operator() (const Point &aP,
282  const Point &aQ) const
283 {
284  return std::pow( NumberTraits<RawValue>::castToDouble(rawDistance(aP,aQ)),
285  1.0/2.0);
286 }
287 //------------------------------------------------------------------------------
288 template <typename T, typename P>
289 inline
290 DGtal::Closest
291 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::closest (const Point &origin,
292  const Point &first,
293  const Point &second) const
294 {
295  RawValue a=NumberTraits<RawValue>::ZERO,
296  b=NumberTraits<RawValue>::ZERO;
297 
298  a = rawDistance(origin,first);
299  b = rawDistance(origin,second);
300 
301  if (a<b)
302  return ClosestFIRST;
303  else
304  if (a>b)
305  return ClosestSECOND;
306  else
307  return ClosestBOTH;
308 }
309 //------------------------------------------------------------------------------
310 template <typename T, typename P>
311 inline
312 typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Abscissa
313 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::binarySearchHidden(const Abscissa &,
314  const Abscissa &,
315  const RawValue &,
316  const RawValue &,
317  const Abscissa &,
318  const Abscissa &) const
319 {
320  ASSERT(false && "Not Necessary for l_2");
321  return 0;
322 }
323 //------------------------------------------------------------------------------
324 template <typename T, typename P>
325 inline
326 bool
327 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::hiddenBy(const Point &u,
328  const Point &v,
329  const Point &w,
330  const Point &startingPoint,
331  const Point &/*endPoint*/,
332  const typename Point::UnsignedComponent dim) const
333 {
334  RawValue a,b, c;
335 
336  a = v[dim] - u[dim];
337  b = w[dim] - v[dim];
338  c = a + b;
339 
340  RawValue d2_v=NumberTraits<RawValue>::ZERO, d2_u=NumberTraits<RawValue>::ZERO ,d2_w=NumberTraits<RawValue>::ZERO;
341 
342  for(DGtal::Dimension i = 0 ; i < Point::dimension ; i++)
343  if (i != dim)
344  {
345  d2_u += static_cast<RawValue>(u[i] - startingPoint[i] ) *static_cast<RawValue>(u[i] - startingPoint[i] );
346  d2_v += static_cast<RawValue>(v[i] - startingPoint[i] ) *static_cast<RawValue>(v[i] - startingPoint[i] );
347  d2_w += static_cast<RawValue>(w[i] - startingPoint[i] ) *static_cast<RawValue>(w[i] - startingPoint[i] );
348  }
349 
350  return (c * d2_v - b*d2_u - a*d2_w - a*b*c) > 0 ;
351 }
352 //------------------------------------------------------------------------------
353 template <typename T, typename P>
354 inline
355 void
356 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::selfDisplay ( std::ostream & out ) const
357 {
358  out << "[ExactPredicateLpSeparableMetric] p=2";
359 }
360 //------------------------------------------------------------------------------
361 template <typename T, typename P>
362 inline
363 bool
364 DGtal::ExactPredicateLpSeparableMetric<T,2,P>::isValid() const
365 {
366  return true;
367 }
Generated on Tue Jun 1 2021 17:05:08 for DGtal by doxygen 1.9.1