DGtal 1.4.0
Loading...
Searching...
No Matches
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 ------------------------------
40template <typename T, DGtal::uint32_t p, typename P>
41inline
42DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::ExactPredicateLpPowerSeparableMetric()
43{
44}
45//------------------------------------------------------------------------------
46template <typename T, DGtal::uint32_t p, typename P>
47inline
48DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::~ExactPredicateLpPowerSeparableMetric()
49{
50}
51//------------------------------------------------------------------------------
52template <typename T, DGtal::uint32_t p, typename P>
53inline
54typename DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::Promoted
55DGtal::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//------------------------------------------------------------------------------
66template <typename T,DGtal::uint32_t p, typename P>
67inline
68typename DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::Weight
69DGtal::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//------------------------------------------------------------------------------
76template <typename T, DGtal::uint32_t p, typename P>
77inline
78DGtal::Closest
79DGtal::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//------------------------------------------------------------------------------
99template <typename T, DGtal::uint32_t p, typename P>
100inline
101typename DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::Abscissa
102DGtal::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//------------------------------------------------------------------------------
135template <typename T, DGtal::uint32_t p , typename P>
136inline
137bool
138DGtal::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//------------------------------------------------------------------------------
211template <typename T, DGtal::uint32_t p, typename P>
212inline
213void
214DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::selfDisplay ( std::ostream & out ) const
215{
216 out << "[ExactPredicateLpPowerSeparableMetric] p="<<p;
217}
218//------------------------------------------------------------------------------
219template <typename T, DGtal::uint32_t p, typename P>
220inline
221bool
222DGtal::ExactPredicateLpPowerSeparableMetric<T,p,P>::isValid() const
223{
224 return true;
225}
226//------------------------------------------------------------------------------
227template <typename T, DGtal::uint32_t p, typename P>
228inline
229std::ostream&
230DGtal::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 ------------------------------
243template <typename T, typename P>
244inline
245DGtal::ExactPredicateLpPowerSeparableMetric<T,2,P>::ExactPredicateLpPowerSeparableMetric()
246{
247}
248//------------------------------------------------------------------------------
249template <typename T, typename P>
250inline
251DGtal::ExactPredicateLpPowerSeparableMetric<T,2,P>::~ExactPredicateLpPowerSeparableMetric()
252{
253}
254//------------------------------------------------------------------------------
255template <typename T, typename P>
256inline
257typename DGtal::ExactPredicateLpPowerSeparableMetric<T,2,P>::Promoted
258DGtal::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//------------------------------------------------------------------------------
269template <typename T, typename P>
270inline
271typename DGtal::ExactPredicateLpPowerSeparableMetric<T,2,P>::Weight
272DGtal::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//------------------------------------------------------------------------------
279template <typename T, typename P>
280inline
281DGtal::Closest
282DGtal::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//------------------------------------------------------------------------------
303template <typename T, typename P>
304inline
305bool
306DGtal::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//------------------------------------------------------------------------------
337template <typename T, typename P>
338inline
339void
340DGtal::ExactPredicateLpPowerSeparableMetric<T,2,P>::selfDisplay ( std::ostream & out ) const
341{
342 out << "[ExactPredicateLpPowerSeparableMetric] p=2";
343}
344//------------------------------------------------------------------------------
345template <typename T, typename P>
346inline
347bool
348DGtal::ExactPredicateLpPowerSeparableMetric<T,2,P>::isValid() const
349{
350 return true;
351}