Adding upstream version 1.3.upstream/1.3upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 521 insertions, 0 deletions

diff --git a/include/2geom/numeric/fitting-model.h b/include/2geom/numeric/fitting-model.h
new file mode 100644
index 0000000..0316f57
--- /dev/null
+++ b/include/2geom/numeric/fitting-model.h
@@ -0,0 +1,521 @@
+/*
+ * Fitting Models for Geom Types
+ *
+ * Authors:
+ *      Marco Cecchetti <mrcekets at gmail.com>
+ *
+ * Copyright 2008  authors
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+
+#ifndef _NL_FITTING_MODEL_H_
+#define _NL_FITTING_MODEL_H_
+
+
+#include <2geom/d2.h>
+#include <2geom/sbasis.h>
+#include <2geom/bezier.h>
+#include <2geom/bezier-curve.h>
+#include <2geom/polynomial.h>
+#include <2geom/ellipse.h>
+#include <2geom/circle.h>
+#include <2geom/utils.h>
+#include <2geom/conicsec.h>
+
+
+namespace Geom { namespace NL {
+
+/*
+ * A model is an abstraction for an expression dependent from a parameter where
+ * the coefficients of this expression are the unknowns of the fitting problem.
+ * For a ceratain number of parameter values we know the related values
+ * the expression evaluates to: from each parameter value we get a row of
+ * the matrix of the fitting problem, from each expression value we get
+ * the related constant term.
+ * Example: given the model a*x^2 + b*x + c = 0; from x = 1 we get
+ * the equation a + b + c = 0, in this example the constant term is always
+ * the same for each parameter value.
+ *
+ * A model is required to implement 3 methods:
+ *
+ *  - size : returns the number of unknown coefficients that appear in
+ *           the expression of the fitting problem;
+ *  - feed : its input is a parameter value and the related expression value,
+ *           it generates a matrix row and a new entry of the constant vector
+ *           of the fitting problem;
+ *  - instance : it has an input parameter represented by the raw vector
+ *               solution of the fitting problem and an output parameter
+ *               of type InstanceType that return a specific object that is
+ *               generated using the fitting problem solution, in the example
+ *               above the object could be a Poly type.
+ */
+
+/*
+ *   completely unknown models must inherit from this template class;
+ *   example: the model a*x^2 + b*x + c = 0 to be solved wrt a, b, c;
+ *   example: the model A(t) = known_sample_value_at(t) to be solved wrt
+ *       the coefficients of the curve A(t) expressed in S-Basis form;
+ *   parameter type: the type of x and t variable in the examples above;
+ *   value type:     the type of the known sample values (in the first example
+ *                   is constant )
+ *   instance type:  the type of the objects produced by using
+ *                   the fitting raw data solution
+ */
+
+
+
+
+template< typename ParameterType, typename ValueType, typename InstanceType >
+class LinearFittingModel
+{
+  public:
+    typedef ParameterType       parameter_type;
+    typedef ValueType           value_type;
+    typedef InstanceType        instance_type;
+
+    static const bool WITH_FIXED_TERMS = false;
+
+    /*
+     * a LinearFittingModel must implement the following methods:
+     *
+     * void feed( VectorView & vector,
+     *            parameter_type const& sample_parameter ) const;
+     *
+     * size_t size() const;
+     *
+     * void instance(instance_type &, raw_type const& raw_data) const;
+     *
+     */
+};
+
+
+/*
+ *   partially known models must inherit from this template class
+ *   example: the model a*x^2 + 2*x + c = 0 to be solved wrt a and c
+ */
+template< typename ParameterType, typename ValueType, typename InstanceType >
+class LinearFittingModelWithFixedTerms
+{
+  public:
+    typedef ParameterType       parameter_type;
+    typedef ValueType           value_type;
+    typedef InstanceType        instance_type;
+
+    static const bool WITH_FIXED_TERMS = true;
+
+    /*
+     * a LinearFittingModelWithFixedTerms must implement the following methods:
+     *
+     * void feed( VectorView & vector,
+     *            value_type & fixed_term,
+     *            parameter_type const& sample_parameter ) const;
+     *
+     * size_t size() const;
+     *
+     * void instance(instance_type &, raw_type const& raw_data) const;
+     *
+     */
+
+
+};
+
+
+// incomplete model, it can be inherited to make up different kinds of
+// instance type; the raw data is a vector of coefficients of a polynomial
+// represented in standard power basis
+template< typename InstanceType >
+class LFMPowerBasis
+    : public LinearFittingModel<double, double, InstanceType>
+{
+  public:
+    LFMPowerBasis(size_t degree)
+        : m_size(degree + 1)
+    {
+    }
+
+    void feed( VectorView & coeff, double sample_parameter ) const
+    {
+        coeff[0] = 1;
+        double x_i = 1;
+        for (size_t i = 1; i < coeff.size(); ++i)
+        {
+          x_i *= sample_parameter;
+          coeff[i] = x_i;
+        }
+    }
+
+    size_t size() const
+    {
+        return m_size;
+    }
+
+  private:
+    size_t m_size;
+};
+
+
+// this model generates Geom::Poly objects
+class LFMPoly
+    : public LFMPowerBasis<Poly>
+{
+  public:
+    LFMPoly(size_t degree)
+        : LFMPowerBasis<Poly>(degree)
+    {
+    }
+
+    void instance(Poly & poly, ConstVectorView const& raw_data) const
+    {
+        poly.clear();
+        poly.resize(size());
+        for (size_t i = 0; i < raw_data.size(); ++i)
+        {
+            poly[i] =  raw_data[i];
+        }
+    }
+};
+
+
+// incomplete model, it can be inherited to make up different kinds of
+// instance type; the raw data is a vector of coefficients of a polynomial
+// represented in standard power basis with leading term coefficient equal to 1
+template< typename InstanceType >
+class LFMNormalizedPowerBasis
+    : public LinearFittingModelWithFixedTerms<double, double, InstanceType>
+{
+  public:
+    LFMNormalizedPowerBasis(size_t _degree)
+        : m_model( _degree - 1)
+    {
+        assert(_degree > 0);
+    }
+
+
+    void feed( VectorView & coeff,
+               double & known_term,
+               double sample_parameter ) const
+    {
+        m_model.feed(coeff, sample_parameter);
+        known_term = coeff[m_model.size()-1] * sample_parameter;
+    }
+
+    size_t size() const
+    {
+        return m_model.size();
+    }
+
+  private:
+    LFMPowerBasis<InstanceType> m_model;
+};
+
+
+// incomplete model, it can be inherited to make up different kinds of
+// instance type; the raw data is a vector of coefficients of the equation
+// of an ellipse curve
+//template< typename InstanceType >
+//class LFMEllipseEquation
+//    : public LinearFittingModelWithFixedTerms<Point, double, InstanceType>
+//{
+//  public:
+//    void feed( VectorView & coeff, double & fixed_term, Point const& p ) const
+//    {
+//        coeff[0] = p[X] * p[Y];
+//        coeff[1] = p[Y] * p[Y];
+//        coeff[2] = p[X];
+//        coeff[3] = p[Y];
+//        coeff[4] = 1;
+//        fixed_term = p[X] * p[X];
+//    }
+//
+//    size_t size() const
+//    {
+//        return 5;
+//    }
+//};
+
+// incomplete model, it can be inherited to make up different kinds of
+// instance type; the raw data is a vector of coefficients of the equation
+// of a conic section
+template< typename InstanceType >
+class LFMConicEquation
+    : public LinearFittingModelWithFixedTerms<Point, double, InstanceType>
+{
+  public:
+    void feed( VectorView & coeff, double & fixed_term, Point const& p ) const
+    {
+        coeff[0] = p[X] * p[Y];
+        coeff[1] = p[Y] * p[Y];
+        coeff[2] = p[X];
+        coeff[3] = p[Y];
+        coeff[4] = 1;
+        fixed_term = p[X] * p[X];
+    }
+
+    size_t size() const
+    {
+        return 5;
+    }
+};
+
+// this model generates Ellipse curves
+class LFMConicSection
+    : public LFMConicEquation<xAx>
+{
+  public:
+    void instance(xAx & c, ConstVectorView const& coeff) const
+    {
+        c.set(1, coeff[0], coeff[1], coeff[2], coeff[3], coeff[4]);
+    }
+};
+
+// this model generates Ellipse curves
+class LFMEllipse
+    : public LFMConicEquation<Ellipse>
+{
+  public:
+    void instance(Ellipse & e, ConstVectorView const& coeff) const
+    {
+        e.setCoefficients(1, coeff[0], coeff[1], coeff[2], coeff[3], coeff[4]);
+    }
+};
+
+
+// incomplete model, it can be inherited to make up different kinds of
+// instance type; the raw data is a vector of coefficients of the equation
+// of a circle curve
+template< typename InstanceType >
+class LFMCircleEquation
+    : public LinearFittingModelWithFixedTerms<Point, double, InstanceType>
+{
+  public:
+    void feed( VectorView & coeff, double & fixed_term, Point const& p ) const
+    {
+        coeff[0] = p[X];
+        coeff[1] = p[Y];
+        coeff[2] = 1;
+        fixed_term = p[X] * p[X] + p[Y] * p[Y];
+    }
+
+    size_t size() const
+    {
+        return 3;
+    }
+};
+
+
+// this model generates Ellipse curves
+class LFMCircle
+    : public LFMCircleEquation<Circle>
+{
+  public:
+    void instance(Circle & c, ConstVectorView const& coeff) const
+    {
+        c.setCoefficients(1, coeff[0], coeff[1], coeff[2]);
+    }
+};
+
+
+// this model generates SBasis objects
+class LFMSBasis
+    : public LinearFittingModel<double, double, SBasis>
+{
+  public:
+    LFMSBasis( size_t _order )
+        : m_size( 2*(_order+1) ),
+          m_order(_order)
+    {
+    }
+
+    void feed( VectorView & coeff, double t ) const
+    {
+        double u0 = 1-t;
+        double u1 = t;
+        double s = u0 * u1;
+        coeff[0] = u0;
+        coeff[1] = u1;
+        for (size_t i = 2; i < size(); i+=2)
+        {
+            u0 *= s;
+            u1 *= s;
+            coeff[i] = u0;
+            coeff[i+1] = u1;
+        }
+    }
+
+    size_t size() const
+    {
+        return m_size;
+    }
+
+    void instance(SBasis & sb, ConstVectorView const& raw_data) const
+    {
+        sb.resize(m_order+1);
+        for (unsigned int i = 0, k = 0; i < raw_data.size(); i+=2, ++k)
+        {
+            sb[k][0] = raw_data[i];
+            sb[k][1] = raw_data[i+1];
+        }
+    }
+
+  private:
+    size_t m_size;
+    size_t m_order;
+};
+
+
+// this model generates D2<SBasis> objects
+class LFMD2SBasis
+    : public LinearFittingModel< double, Point, D2<SBasis> >
+{
+  public:
+    LFMD2SBasis( size_t _order )
+        : mosb(_order)
+    {
+    }
+
+    void feed( VectorView & coeff, double t ) const
+    {
+        mosb.feed(coeff, t);
+    }
+
+    size_t size() const
+    {
+        return mosb.size();
+    }
+
+    void instance(D2<SBasis> & d2sb, ConstMatrixView const& raw_data) const
+    {
+        mosb.instance(d2sb[X], raw_data.column_const_view(X));
+        mosb.instance(d2sb[Y], raw_data.column_const_view(Y));
+    }
+
+  private:
+    LFMSBasis mosb;
+};
+
+
+// this model generates Bezier objects
+class LFMBezier
+    : public LinearFittingModel<double, double, Bezier>
+{
+  public:
+    LFMBezier( size_t _order )
+        : m_size(_order + 1),
+          m_order(_order)
+    {
+        binomial_coefficients(m_bc, m_order);
+    }
+
+    void feed( VectorView & coeff, double t ) const
+    {
+        double s = 1;
+        for (size_t i = 0; i < size(); ++i)
+        {
+            coeff[i] = s * m_bc[i];
+            s *= t;
+        }
+        double u = 1-t;
+        s = 1;
+        for (size_t i = size()-1; i > 0; --i)
+        {
+            coeff[i] *= s;
+            s *= u;
+        }
+        coeff[0] *= s;
+    }
+
+    size_t size() const
+    {
+        return m_size;
+    }
+
+    void instance(Bezier & b, ConstVectorView const& raw_data) const
+    {
+        assert(b.size() == raw_data.size());
+        for (unsigned int i = 0; i < raw_data.size(); ++i)
+        {
+            b[i] = raw_data[i];
+        }
+    }
+
+  private:
+    size_t m_size;
+    size_t m_order;
+    std::vector<size_t> m_bc;
+};
+
+
+// this model generates Bezier curves
+template <unsigned degree>
+class LFMBezierCurveN
+    : public LinearFittingModel< double, Point, BezierCurveN<degree> >
+{
+  public:
+    LFMBezierCurveN()
+        : mob(degree+1)
+    {
+    }
+
+    void feed( VectorView & coeff, double t ) const
+    {
+        mob.feed(coeff, t);
+    }
+
+    size_t size() const
+    {
+        return mob.size();
+    }
+
+    void instance(BezierCurveN<degree> & bc, ConstMatrixView const& raw_data) const
+    {
+        Bezier bx(degree);
+        Bezier by(degree);
+        mob.instance(bx, raw_data.column_const_view(X));
+        mob.instance(by, raw_data.column_const_view(Y));
+        bc = BezierCurveN<degree>(bx, by);
+    }
+
+  private:
+    LFMBezier mob;
+};
+
+}  // end namespace NL
+}  // end namespace Geom
+
+
+#endif // _NL_FITTING_MODEL_H_
+
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :