src/2geom/numeric/fitting-model.h

   1 /*\r
   2  * Fitting Models for Geom Types\r
   3  *\r
   4  * Authors:\r
   5  *      Marco Cecchetti <mrcekets at gmail.com>\r
   6  *\r
   7  * Copyright 2008  authors\r
   8  *\r
   9  * This library is free software; you can redistribute it and/or\r
  10  * modify it either under the terms of the GNU Lesser General Public\r
  11  * License version 2.1 as published by the Free Software Foundation\r
  12  * (the "LGPL") or, at your option, under the terms of the Mozilla\r
  13  * Public License Version 1.1 (the "MPL"). If you do not alter this\r
  14  * notice, a recipient may use your version of this file under either\r
  15  * the MPL or the LGPL.\r
  16  *\r
  17  * You should have received a copy of the LGPL along with this library\r
  18  * in the file COPYING-LGPL-2.1; if not, write to the Free Software\r
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\r
  20  * You should have received a copy of the MPL along with this library\r
  21  * in the file COPYING-MPL-1.1\r
  22  *\r
  23  * The contents of this file are subject to the Mozilla Public License\r
  24  * Version 1.1 (the "License"); you may not use this file except in\r
  25  * compliance with the License. You may obtain a copy of the License at\r
  26  * http://www.mozilla.org/MPL/\r
  27  *\r
  28  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY\r
  29  * OF ANY KIND, either express or implied. See the LGPL or the MPL for\r
  30  * the specific language governing rights and limitations.\r
  31  */\r
  32 \r
  33 \r
  34 #ifndef _NL_FITTING_MODEL_H_\r
  35 #define _NL_FITTING_MODEL_H_\r
  36 \r
  37 \r
  38 #include <2geom/d2.h>\r
  39 #include <2geom/sbasis.h>\r
  40 #include <2geom/bezier.h>\r
  41 #include <2geom/bezier-curve.h>\r
  42 #include <2geom/poly.h>\r
  43 #include <2geom/ellipse.h>\r
  44 #include <2geom/utils.h>\r
  45 \r
  46 \r
  47 namespace Geom { namespace NL {\r
  48 \r
  49 \r
  50 /*\r
  51  *   completely unknown models must inherit from this template class;\r
  52  *   example: the model a*x^2 + b*x + c = 0 to be solved wrt a, b, c;\r
  53  *   example: the model A(t) = known_sample_value_at(t) to be solved wrt\r
  54  *       the coefficients of the curve A(t) expressed in S-Basis form;\r
  55  *   parameter type: the type of x and t variable in the examples above;\r
  56  *   value type:     the type of the known sample values (in the first example\r
  57  *                   is constant )\r
  58  *   instance type:  the type of the objects produced by using\r
  59  *                   the fitting raw data solution\r
  60  */\r
  61 template< typename ParameterType, typename ValueType, typename InstanceType >\r
  62 class LinearFittingModel\r
  63 {\r
  64   public:\r
  65     typedef ParameterType       parameter_type;\r
  66     typedef ValueType           value_type;\r
  67     typedef InstanceType        instance_type;\r
  68 \r
  69     static const bool WITH_FIXED_TERMS = false;\r
  70 \r
  71     /*\r
  72      * a LinearFittingModel must implement the following methods:\r
  73      *\r
  74      * void feed( VectorView & vector,\r
  75      *            parameter_type const& sample_parameter ) const;\r
  76      *\r
  77      * size_t size() const;\r
  78      *\r
  79      * void instance(instance_type &, raw_type const& raw_data) const;\r
  80      *\r
  81      */\r
  82 };\r
  83 \r
  84 \r
  85 /*\r
  86  *   partially known models must inherit from this template class\r
  87  *   example: the model a*x^2 + 2*x + c = 0 to be solved wrt a and c\r
  88  */\r
  89 template< typename ParameterType, typename ValueType, typename InstanceType >\r
  90 class LinearFittingModelWithFixedTerms\r
  91 {\r
  92   public:\r
  93     typedef ParameterType       parameter_type;\r
  94     typedef ValueType           value_type;\r
  95     typedef InstanceType        instance_type;\r
  96 \r
  97     static const bool WITH_FIXED_TERMS = true;\r
  98 \r
  99     /*\r
 100      * a LinearFittingModelWithFixedTerms must implement the following methods:\r
 101      *\r
 102      * void feed( VectorView & vector,\r
 103      *            value_type & fixed_term,\r
 104      *            parameter_type const& sample_parameter ) const;\r
 105      *\r
 106      * size_t size() const;\r
 107      *\r
 108      * void instance(instance_type &, raw_type const& raw_data) const;\r
 109      *\r
 110      */\r
 111 \r
 112 \r
 113 };\r
 114 \r
 115 \r
 116 // incomplete model, it can be inherited to make up different kinds of\r
 117 // instance type; the raw data is a vector of coefficients of a polynomial\r
 118 // rapresented in standard power basis\r
 119 template< typename InstanceType >\r
 120 class LFMPowerBasis\r
 121     : public LinearFittingModel<double, double, InstanceType>\r
 122 {\r
 123   public:\r
 124     LFMPowerBasis(size_t degree)\r
 125         : m_size(degree + 1)\r
 126     {\r
 127     }\r
 128 \r
 129     void feed( VectorView & coeff, double sample_parameter ) const\r
 130     {\r
 131         coeff[0] = 1;\r
 132         double x_i = 1;\r
 133         for (size_t i = 1; i < coeff.size(); ++i)\r
 134         {\r
 135           x_i *= sample_parameter;\r
 136           coeff[i] = x_i;\r
 137         }\r
 138     }\r
 139 \r
 140     size_t size() const\r
 141     {\r
 142         return m_size;\r
 143     }\r
 144 \r
 145   private:\r
 146     size_t m_size;\r
 147 };\r
 148 \r
 149 \r
 150 // this model generates Geom::Poly objects\r
 151 class LFMPoly\r
 152     : public LFMPowerBasis<Poly>\r
 153 {\r
 154   public:\r
 155     LFMPoly(size_t degree)\r
 156         : LFMPowerBasis<Poly>(degree)\r
 157     {\r
 158     }\r
 159 \r
 160     void instance(Poly & poly, ConstVectorView const& raw_data) const\r
 161     {\r
 162         poly.clear();\r
 163         poly.resize(size());\r
 164         for (size_t i = 0; i < raw_data.size(); ++i)\r
 165         {\r
 166             poly[i] =  raw_data[i];\r
 167         }\r
 168     }\r
 169 };\r
 170 \r
 171 \r
 172 // incomplete model, it can be inherited to make up different kinds of\r
 173 // instance type; the raw data is a vector of coefficients of a polynomial\r
 174 // rapresented in standard power basis with leading term coefficient equal to 1\r
 175 template< typename InstanceType >\r
 176 class LFMNormalizedPowerBasis\r
 177     : public LinearFittingModelWithFixedTerms<double, double, InstanceType>\r
 178 {\r
 179   public:\r
 180     LFMNormalizedPowerBasis(size_t _degree)\r
 181         : m_model( _degree - 1)\r
 182     {\r
 183         assert(_degree > 0);\r
 184     }\r
 185 \r
 186 \r
 187     void feed( VectorView & coeff,\r
 188                double & known_term,\r
 189                double sample_parameter ) const\r
 190     {\r
 191         m_model.feed(coeff, sample_parameter);\r
 192         known_term = coeff[m_model.size()-1] * sample_parameter;\r
 193     }\r
 194 \r
 195     size_t size() const\r
 196     {\r
 197         return m_model.size();\r
 198     }\r
 199 \r
 200   private:\r
 201     LFMPowerBasis<InstanceType> m_model;\r
 202 };\r
 203 \r
 204 \r
 205 // incomplete model, it can be inherited to make up different kinds of\r
 206 // instance type; the raw data is a vector of coefficients of the equation\r
 207 // of an ellipse curve\r
 208 template< typename InstanceType >\r
 209 class LFMEllipseEquation\r
 210     : public LinearFittingModelWithFixedTerms<Point, double, InstanceType>\r
 211 {\r
 212   public:\r
 213     void feed( VectorView & coeff, double & fixed_term, Point const& p ) const\r
 214     {\r
 215         coeff[0] = p[X] * p[Y];\r
 216         coeff[1] = p[Y] * p[Y];\r
 217         coeff[2] = p[X];\r
 218         coeff[3] = p[Y];\r
 219         coeff[4] = 1;\r
 220         fixed_term = p[X] * p[X];\r
 221     }\r
 222 \r
 223     size_t size() const\r
 224     {\r
 225         return 5;\r
 226     }\r
 227 };\r
 228 \r
 229 \r
 230 // this model generates Ellipse curves\r
 231 class LFMEllipse\r
 232     : public LFMEllipseEquation<Ellipse>\r
 233 {\r
 234   public:\r
 235     void instance(Ellipse & e, ConstVectorView const& coeff) const\r
 236     {\r
 237         e.set(1, coeff[0], coeff[1], coeff[2], coeff[3], coeff[4]);\r
 238     }\r
 239 };\r
 240 \r
 241 \r
 242 // this model generates SBasis objects\r
 243 class LFMSBasis\r
 244     : public LinearFittingModel<double, double, SBasis>\r
 245 {\r
 246   public:\r
 247     LFMSBasis( size_t _order )\r
 248         : m_size( 2*(_order+1) ),\r
 249           m_order(_order)\r
 250     {\r
 251     }\r
 252 \r
 253     void feed( VectorView & coeff, double t ) const\r
 254     {\r
 255         double u0 = 1-t;\r
 256         double u1 = t;\r
 257         double s = u0 * u1;\r
 258         coeff[0] = u0;\r
 259         coeff[1] = u1;\r
 260         for (size_t i = 2; i < size(); i+=2)\r
 261         {\r
 262             u0 *= s;\r
 263             u1 *= s;\r
 264             coeff[i] = u0;\r
 265             coeff[i+1] = u1;\r
 266         }\r
 267     }\r
 268 \r
 269     size_t size() const\r
 270     {\r
 271         return m_size;\r
 272     }\r
 273 \r
 274     void instance(SBasis & sb, ConstVectorView const& raw_data) const\r
 275     {\r
 276         sb.clear();\r
 277         sb.resize(m_order+1);\r
 278         for (unsigned int i = 0, k = 0; i < raw_data.size(); i+=2, ++k)\r
 279         {\r
 280             sb[k][0] = raw_data[i];\r
 281             sb[k][1] = raw_data[i+1];\r
 282         }\r
 283     }\r
 284 \r
 285   private:\r
 286     size_t m_size;\r
 287     size_t m_order;\r
 288 };\r
 289 \r
 290 \r
 291 // this model generates D2<SBasis> objects\r
 292 class LFMD2SBasis\r
 293     : public LinearFittingModel< double, Point, D2<SBasis> >\r
 294 {\r
 295   public:\r
 296     LFMD2SBasis( size_t _order )\r
 297         : mosb(_order)\r
 298     {\r
 299     }\r
 300 \r
 301     void feed( VectorView & coeff, double t ) const\r
 302     {\r
 303         mosb.feed(coeff, t);\r
 304     }\r
 305 \r
 306     size_t size() const\r
 307     {\r
 308         return mosb.size();\r
 309     }\r
 310 \r
 311     void instance(D2<SBasis> & d2sb, ConstMatrixView const& raw_data) const\r
 312     {\r
 313         mosb.instance(d2sb[X], raw_data.column_const_view(X));\r
 314         mosb.instance(d2sb[Y], raw_data.column_const_view(Y));\r
 315     }\r
 316 \r
 317   private:\r
 318     LFMSBasis mosb;\r
 319 };\r
 320 \r
 321 \r
 322 // this model generates Bezier objects\r
 323 class LFMBezier\r
 324     : public LinearFittingModel<double, double, Bezier>\r
 325 {\r
 326   public:\r
 327     LFMBezier( size_t _order )\r
 328         : m_size(_order + 1),\r
 329           m_order(_order)\r
 330     {\r
 331         binomial_coefficients(m_bc, m_order);\r
 332     }\r
 333 \r
 334     void feed( VectorView & coeff, double t ) const\r
 335     {\r
 336         double s = 1;\r
 337         for (size_t i = 0; i < size(); ++i)\r
 338         {\r
 339             coeff[i] = s * m_bc[i];\r
 340             s *= t;\r
 341         }\r
 342         double u = 1-t;\r
 343         s = 1;\r
 344         for (size_t i = size()-1; i > 0; --i)\r
 345         {\r
 346             coeff[i] *= s;\r
 347             s *= u;\r
 348         }\r
 349         coeff[0] *= s;\r
 350     }\r
 351 \r
 352     size_t size() const\r
 353     {\r
 354         return m_size;\r
 355     }\r
 356 \r
 357     void instance(Bezier & b, ConstVectorView const& raw_data) const\r
 358     {\r
 359         assert(b.size() == raw_data.size());\r
 360         for (unsigned int i = 0; i < raw_data.size(); ++i)\r
 361         {\r
 362             b[i] = raw_data[i];\r
 363         }\r
 364     }\r
 365 \r
 366   private:\r
 367     size_t m_size;\r
 368     size_t m_order;\r
 369     std::vector<size_t> m_bc;\r
 370 };\r
 371 \r
 372 \r
 373 // this model generates Bezier curves\r
 374 template< unsigned int N >\r
 375 class LFMBezierCurve\r
 376     : public LinearFittingModel< double, Point, BezierCurve<N> >\r
 377 {\r
 378   public:\r
 379     LFMBezierCurve( size_t _order )\r
 380         : mob(_order)\r
 381     {\r
 382     }\r
 383 \r
 384     void feed( VectorView & coeff, double t ) const\r
 385     {\r
 386         mob.feed(coeff, t);\r
 387     }\r
 388 \r
 389     size_t size() const\r
 390     {\r
 391         return mob.size();\r
 392     }\r
 393 \r
 394     void instance(BezierCurve<N> & bc, ConstMatrixView const& raw_data) const\r
 395     {\r
 396         Bezier bx(size()-1);\r
 397         Bezier by(size()-1);\r
 398         mob.instance(bx, raw_data.column_const_view(X));\r
 399         mob.instance(by, raw_data.column_const_view(Y));\r
 400         bc = BezierCurve<N>(bx, by);\r
 401     }\r
 402 \r
 403   private:\r
 404     LFMBezier mob;\r
 405 };\r
 406 \r
 407 }  // end namespace NL\r
 408 }  // end namespace Geom\r
 409 \r
 410 \r
 411 #endif // _NL_FITTING_MODEL_H_\r
 412 \r
 413 \r
 414 /*\r
 415   Local Variables:\r
 416   mode:c++\r
 417   c-file-style:"stroustrup"\r
 418   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))\r
 419   indent-tabs-mode:nil\r
 420   fill-column:99\r
 421   End:\r
 422 */\r
 423 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :\r