DGtal 1.4.0
Loading...
Searching...
No Matches
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 ------------------------------
40template <typename T, DGtal::uint32_t p, typename P>
41inline
42DGtal::ExactPredicateLpSeparableMetric<T,p,P>::ExactPredicateLpSeparableMetric()
43{
44}
45//------------------------------------------------------------------------------
46template <typename T, DGtal::uint32_t p, typename P>
47inline
48DGtal::ExactPredicateLpSeparableMetric<T,p,P>::~ExactPredicateLpSeparableMetric()
49{
50}
51//------------------------------------------------------------------------------
52template <typename T, DGtal::uint32_t p, typename P>
53inline
54typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::RawValue
55DGtal::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//------------------------------------------------------------------------------
66template <typename T, DGtal::uint32_t p, typename P>
67inline
68typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::Value
69DGtal::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//------------------------------------------------------------------------------
75template <typename T, DGtal::uint32_t p, typename P>
76inline
77DGtal::Closest
78DGtal::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//------------------------------------------------------------------------------
97template <typename T, DGtal::uint32_t p, typename P>
98inline
99typename DGtal::ExactPredicateLpSeparableMetric<T,p,P>::Abscissa
100DGtal::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//------------------------------------------------------------------------------
134template <typename T, DGtal::uint32_t p , typename P>
135inline
136bool
137DGtal::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//------------------------------------------------------------------------------
206template <typename T, DGtal::uint32_t p, typename P>
207inline
208void
209DGtal::ExactPredicateLpSeparableMetric<T,p,P>::selfDisplay ( std::ostream & out ) const
210{
211 out << "[ExactPredicateLpSeparableMetric] p="<<p;
212}
213//------------------------------------------------------------------------------
214template <typename T, DGtal::uint32_t p, typename P>
215inline
216bool
217DGtal::ExactPredicateLpSeparableMetric<T,p,P>::isValid() const
218{
219 return true;
220}
221//------------------------------------------------------------------------------
222template <typename T, DGtal::uint32_t p, typename P>
223inline
224std::ostream&
225DGtal::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 ------------------------------
238template <typename T, typename P>
239inline
240DGtal::ExactPredicateLpSeparableMetric<T,2,P>::ExactPredicateLpSeparableMetric()
241{
242}
243//------------------------------------------------------------------------------
244template <typename T, typename P>
245inline
246DGtal::ExactPredicateLpSeparableMetric<T,2,P>::~ExactPredicateLpSeparableMetric()
247{
248}
249//------------------------------------------------------------------------------
250template <typename T, typename P>
251inline
252typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::RawValue
253DGtal::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//------------------------------------------------------------------------------
264template <typename T, typename P>
265inline
266typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Value
267DGtal::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//------------------------------------------------------------------------------
278template <typename T, typename P>
279inline
280typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Value
281DGtal::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//------------------------------------------------------------------------------
288template <typename T, typename P>
289inline
290DGtal::Closest
291DGtal::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//------------------------------------------------------------------------------
310template <typename T, typename P>
311inline
312typename DGtal::ExactPredicateLpSeparableMetric<T,2,P>::Abscissa
313DGtal::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//------------------------------------------------------------------------------
324template <typename T, typename P>
325inline
326bool
327DGtal::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//------------------------------------------------------------------------------
353template <typename T, typename P>
354inline
355void
356DGtal::ExactPredicateLpSeparableMetric<T,2,P>::selfDisplay ( std::ostream & out ) const
357{
358 out << "[ExactPredicateLpSeparableMetric] p=2";
359}
360//------------------------------------------------------------------------------
361template <typename T, typename P>
362inline
363bool
364DGtal::ExactPredicateLpSeparableMetric<T,2,P>::isValid() const
365{
366 return true;
367}