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