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.
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.
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/>.
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
24 * Implementation of inline methods defined in ExactLpSeparableMetric.h
26 * This file is part of the DGtal library.
30//////////////////////////////////////////////////////////////////////////////
32//////////////////////////////////////////////////////////////////////////////
34///////////////////////////////////////////////////////////////////////////////
35// IMPLEMENTATION of inline methods.
36///////////////////////////////////////////////////////////////////////////////
38///////////////////////////////////////////////////////////////////////////////
39// ----------------------- Standard services ------------------------------
40template <typename T, DGtal::uint32_t p, typename P>
42DGtal::ExactPredicateLpSeparableMetric<T,p,P>::ExactPredicateLpSeparableMetric()
45//------------------------------------------------------------------------------
46template <typename T, DGtal::uint32_t p, typename P>
48DGtal::ExactPredicateLpSeparableMetric<T,p,P>::~ExactPredicateLpSeparableMetric()
51//------------------------------------------------------------------------------
52template <typename T, DGtal::uint32_t p, typename P>
54typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::RawValue
55DGtal::ExactPredicateLpSeparableMetric<T,p,P>::rawDistance (const Point &aP,
56 const Point &aQ) const
58 RawValue res= NumberTraits<RawValue>::ZERO;
59 for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
61 res += functions::power(static_cast<RawValue>(abs(aP[d]-aQ[d])), p);
65//------------------------------------------------------------------------------
66template <typename T, DGtal::uint32_t p, typename P>
68typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::Value
69DGtal::ExactPredicateLpSeparableMetric<T,p,P>::operator()(const Point &aP,
70 const Point &aQ) const
72 return std::pow( NumberTraits<RawValue>::castToDouble(rawDistance(aP,aQ)), 1.0/(double)p);
74//------------------------------------------------------------------------------
75template <typename T, DGtal::uint32_t p, typename P>
78DGtal::ExactPredicateLpSeparableMetric<T,p,P>::closest (const Point &origin,
80 const Point &second) const
82 RawValue a=NumberTraits<RawValue>::ZERO,
83 b=NumberTraits<RawValue>::ZERO;
85 a = rawDistance(origin,first);
86 b = rawDistance(origin,second);
96//------------------------------------------------------------------------------
97template <typename T, DGtal::uint32_t p, typename P>
99typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::Abscissa
100DGtal::ExactPredicateLpSeparableMetric<T,p,P>::binarySearchHidden(const Abscissa &udim,
101 const Abscissa &vdim,
104 const Abscissa &lower,
105 const Abscissa &upper) const
107 ASSERT( (nu + functions::power( static_cast<RawValue>(abs( udim - lower)), p)) <
108 (nv + functions::power( static_cast<RawValue>(abs( vdim - lower)), p)));
111 if ( (upper - lower) <= NumberTraits<Abscissa>::ONE)
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)
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);
127 if ( nuUpdated < nvUpdated)
128 return binarySearchHidden(udim,vdim,nu,nv,mid,upper);
130 return binarySearchHidden(udim,vdim,nu,nv,lower,mid);
133//------------------------------------------------------------------------------
134template <typename T, DGtal::uint32_t p , typename P>
137DGtal::ExactPredicateLpSeparableMetric<T,p,P>::hiddenBy(const Point &u,
140 const Point &startingPoint,
141 const Point &endPoint,
142 const typename Point::UnsignedComponent dim) const
144 //Interval bound for the binary search
145 Abscissa lower = startingPoint[dim];
146 Abscissa upper = endPoint[dim];
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++)
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);
160 //Abscissa of voronoi edges
162 RawValue dv,dw,du,ddv,ddw;
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);
169 //Precondition of binarySearchHidden is true
172 uv = binarySearchHidden(u[dim],v[dim],nu,nv,lower,upper);
175 vw = binarySearchHidden(v[dim],w[dim],nv,nw,lower,upper); //precondition
183 //check if uv + 1 is stricly in W
185 //first, optimisation
186 if (uv == upper) return true;
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);
205//------------------------------------------------------------------------------
206template <typename T, DGtal::uint32_t p, typename P>
209DGtal::ExactPredicateLpSeparableMetric<T,p,P>::selfDisplay ( std::ostream & out ) const
211 out << "[ExactPredicateLpSeparableMetric] p="<<p;
213//------------------------------------------------------------------------------
214template <typename T, DGtal::uint32_t p, typename P>
217DGtal::ExactPredicateLpSeparableMetric<T,p,P>::isValid() const
221//------------------------------------------------------------------------------
222template <typename T, DGtal::uint32_t p, typename P>
225DGtal::operator<< ( std::ostream & out,
226 const ExactPredicateLpSeparableMetric<T,p,P> & object )
228 object.selfDisplay( out );
232///////////////////////////////////////////////////////////////////////////////
233// L_2 specialization //
234///////////////////////////////////////////////////////////////////////////////
237// ----------------------- Standard services ------------------------------
238template <typename T, typename P>
240DGtal::ExactPredicateLpSeparableMetric<T,2,P>::ExactPredicateLpSeparableMetric()
243//------------------------------------------------------------------------------
244template <typename T, typename P>
246DGtal::ExactPredicateLpSeparableMetric<T,2,P>::~ExactPredicateLpSeparableMetric()
249//------------------------------------------------------------------------------
250template <typename T, typename P>
252typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::RawValue
253DGtal::ExactPredicateLpSeparableMetric<T,2,P>::rawDistance (const Point &aP,
254 const Point &aQ) const
256 RawValue res= NumberTraits<RawValue>::ZERO;
257 for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
259 res += static_cast<RawValue>(aP[d]-aQ[d])*static_cast<RawValue>(aP[d]-aQ[d]);
263//------------------------------------------------------------------------------
264template <typename T, typename P>
266typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Value
267DGtal::ExactPredicateLpSeparableMetric<T,2,P>::local (const Point &/*aP*/,
268 const Vector &aDir) const
270 RawValue res= NumberTraits<RawValue>::ZERO;
271 for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
273 res += (static_cast<RawValue>(aDir[d]))*(static_cast<RawValue>(aDir[d]));
275 return std::pow( NumberTraits<RawValue>::castToDouble(res), 1.0/2.0);
277//------------------------------------------------------------------------------
278template <typename T, typename P>
280typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Value
281DGtal::ExactPredicateLpSeparableMetric<T,2,P>::operator() (const Point &aP,
282 const Point &aQ) const
284 return std::pow( NumberTraits<RawValue>::castToDouble(rawDistance(aP,aQ)),
287//------------------------------------------------------------------------------
288template <typename T, typename P>
291DGtal::ExactPredicateLpSeparableMetric<T,2,P>::closest (const Point &origin,
293 const Point &second) const
295 RawValue a=NumberTraits<RawValue>::ZERO,
296 b=NumberTraits<RawValue>::ZERO;
298 a = rawDistance(origin,first);
299 b = rawDistance(origin,second);
305 return ClosestSECOND;
309//------------------------------------------------------------------------------
310template <typename T, typename P>
312typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Abscissa
313DGtal::ExactPredicateLpSeparableMetric<T,2,P>::binarySearchHidden(const Abscissa &,
318 const Abscissa &) const
320 ASSERT(false && "Not Necessary for l_2");
323//------------------------------------------------------------------------------
324template <typename T, typename P>
327DGtal::ExactPredicateLpSeparableMetric<T,2,P>::hiddenBy(const Point &u,
330 const Point &startingPoint,
331 const Point &/*endPoint*/,
332 const typename Point::UnsignedComponent dim) const
340 RawValue d2_v=NumberTraits<RawValue>::ZERO, d2_u=NumberTraits<RawValue>::ZERO ,d2_w=NumberTraits<RawValue>::ZERO;
342 for(DGtal::Dimension i = 0 ; i < Point::dimension ; i++)
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] );
350 return (c * d2_v - b*d2_u - a*d2_w - a*b*c) > 0 ;
352//------------------------------------------------------------------------------
353template <typename T, typename P>
356DGtal::ExactPredicateLpSeparableMetric<T,2,P>::selfDisplay ( std::ostream & out ) const
358 out << "[ExactPredicateLpSeparableMetric] p=2";
360//------------------------------------------------------------------------------
361template <typename T, typename P>
364DGtal::ExactPredicateLpSeparableMetric<T,2,P>::isValid() const