DGtal  1.5.beta
InexactPredicateLpSeparableMetric.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 InexactLpSeparableMetric.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, typename V>
41 inline
42 DGtal::InexactPredicateLpSeparableMetric<T,V>::InexactPredicateLpSeparableMetric(const double anExponent):
43  myExponent(anExponent)
44 {
45 }
46 //------------------------------------------------------------------------------
47 template <typename T, typename V>
48 inline
49 DGtal::InexactPredicateLpSeparableMetric<T,V>::~InexactPredicateLpSeparableMetric()
50 {
51 }
52 //------------------------------------------------------------------------------
53 template <typename T, typename V>
54 inline
55 typename DGtal::InexactPredicateLpSeparableMetric<T,V>::Value
56 DGtal::InexactPredicateLpSeparableMetric<T,V>::rawDistance (const Point &aP,
57  const Point &aQ) const
58 {
59  Value res= 0.0;
60  for(DGtal::Dimension d=0; d< Point::dimension ; ++d)
61  {
62  res += std::pow(static_cast<Value>(abs(aP[d]-aQ[d])), myExponent);
63  }
64  return res;
65 }
66 //------------------------------------------------------------------------------
67 template <typename T, typename V>
68 inline
69 typename DGtal::InexactPredicateLpSeparableMetric<T,V>::Value
70 DGtal::InexactPredicateLpSeparableMetric<T,V>::operator() (const Point &aP,
71  const Point &aQ) const
72 {
73  return std::pow( rawDistance(aP,aQ) , 1.0/myExponent);
74 }
75 //------------------------------------------------------------------------------
76 template <typename T, typename V>
77 inline
78 DGtal::Closest
79 DGtal::InexactPredicateLpSeparableMetric<T,V>::closest (const Point &origin,
80  const Point &first,
81  const Point &second) const
82 {
83  Value a=0.0, b=0.0;
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, typename V>
98 inline
99 typename DGtal::InexactPredicateLpSeparableMetric<T,V>::Abscissa
100 DGtal::InexactPredicateLpSeparableMetric<T,V>::binarySearchHidden(const Abscissa &udim,
101  const Abscissa &vdim,
102  const Value &nu,
103  const Value &nv,
104  const Abscissa &lower,
105  const Abscissa &upper) const
106 {
107  ASSERT( (nu + std::pow( static_cast<Value>(abs( udim - lower)), myExponent)) <
108  (nv + std::pow( static_cast<Value>(abs( vdim - lower)), myExponent)));
109 
110  //Recurrence stop
111  if ( (upper - lower) <= NumberTraits<Abscissa>::ONE)
112  {
113  //testing upper
114  Value nuUpdated = nu + std::pow( static_cast<Value>(abs( udim - upper )), myExponent);
115  Value nvUpdated = nv + std::pow( static_cast<Value>(abs( vdim - upper )), myExponent);
116  if (nuUpdated < nvUpdated)
117  return upper;
118  else
119  return lower;
120  }
121 
122  Abscissa mid = (lower + upper)/2;
123  Value nuUpdated = nu + std::pow( static_cast<Value>(abs( udim - mid )), myExponent);
124  Value nvUpdated = nv + std::pow( static_cast<Value>(abs( vdim - mid )), myExponent);
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, typename V>
135 inline
136 bool
137 DGtal::InexactPredicateLpSeparableMetric<T,V>::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  Value nu = 0.0;
150  Value nv = 0.0;
151  Value nw = 0.0;
152  for(DGtal::Dimension i = 0 ; i < Point::dimension ; i++)
153  if (i != dim)
154  {
155  nu += std::pow( static_cast<Value>(abs(u[i] - startingPoint[i])), myExponent);
156  nv += std::pow( static_cast<Value>(abs(v[i] - startingPoint[i])), myExponent);
157  nw += std::pow( static_cast<Value>(abs(w[i] - startingPoint[i])), myExponent);
158  }
159 
160  //Abscissa of voronoi edges
161  Abscissa uv,vw;
162  Value dv,dw,du,ddv,ddw;
163 
164  //checking distances to lower bound
165  du = nu + std::pow( static_cast<Value>(abs( u[dim] - lower)), myExponent);
166  dv = nv + std::pow( static_cast<Value>(abs( v[dim] - lower)), myExponent);
167  dw = nw + std::pow( static_cast<Value>(abs( w[dim] - lower)), myExponent);
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 + std::pow( static_cast<Value>(abs( v[dim] - uv -1)), myExponent);
190  ddw = nw + std::pow( static_cast<Value>(abs( w[dim] - uv -1)), myExponent);
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, typename V>
207 inline
208 void
209 DGtal::InexactPredicateLpSeparableMetric<T,V>::selfDisplay ( std::ostream & out ) const
210 {
211  out << "[InexactPredicateLpSeparableMetric] p="<<myExponent;
212 }
213 //------------------------------------------------------------------------------
214 template <typename T, typename V>
215 inline
216 bool
217 DGtal::InexactPredicateLpSeparableMetric<T,V>::isValid() const
218 {
219  return true;
220 }
221 //------------------------------------------------------------------------------
222 template <typename T, typename V>
223 inline
224 std::ostream&
225 DGtal::operator<< ( std::ostream & out,
226  const InexactPredicateLpSeparableMetric<T,V> & object )
227 {
228  object.selfDisplay( out );
229  return out;
230 }