GCC Code Coverage Report

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