Inkscape
Vector Graphics Editor
Loading...
Searching...
No Matches
fitting-model.h
Go to the documentation of this file.
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
49namespace 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
91template< typename ParameterType, typename ValueType, typename InstanceType >
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 */
119template< typename ParameterType, typename ValueType, typename InstanceType >
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
149template< typename InstanceType >
151 : public LinearFittingModel<double, double, InstanceType>
152{
153 public:
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
182 : public LFMPowerBasis<Poly>
183{
184 public:
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
205template< typename InstanceType >
207 : public LinearFittingModelWithFixedTerms<double, double, InstanceType>
208{
209 public:
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:
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
262template< typename InstanceType >
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
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
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
309template< typename InstanceType >
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
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
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
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:
417};
418
419
420// this model generates Bezier objects
422 : public LinearFittingModel<double, double, Bezier>
423{
424 public:
425 LFMBezier( size_t _order )
426 : m_size(_order + 1),
427 m_order(_order)
428 {
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
472template <unsigned degree>
474 : public LinearFittingModel< double, Point, BezierCurveN<degree> >
475{
476 public:
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:
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 :
Various utility functions.
Bezier curve.
Bernstein-Bezier polynomial.
Circle shape.
Bezier curve with compile-time specified order.
Polynomial in Bernstein-Bezier basis.
Definition bezier.h:126
unsigned size() const
Definition bezier.h:147
Set of all points at a fixed distance from the center.
Definition circle.h:55
Adaptor that creates 2D functions from 1D ones.
Definition d2.h:55
Set of points with a constant sum of distances from two foci.
Definition ellipse.h:68
void setCoefficients(double A, double B, double C, double D, double E, double F)
Set an ellipse by solving its implicit equation.
Definition ellipse.cpp:48
void feed(VectorView &coeff, double t) const
void instance(BezierCurveN< degree > &bc, ConstMatrixView const &raw_data) const
size_t size() const
LFMBezier(size_t _order)
void feed(VectorView &coeff, double t) const
std::vector< size_t > m_bc
void instance(Bezier &b, ConstVectorView const &raw_data) const
void feed(VectorView &coeff, double &fixed_term, Point const &p) const
void instance(Circle &c, ConstVectorView const &coeff) const
void feed(VectorView &coeff, double &fixed_term, Point const &p) const
void instance(xAx &c, ConstVectorView const &coeff) const
void instance(D2< SBasis > &d2sb, ConstMatrixView const &raw_data) const
LFMD2SBasis(size_t _order)
void feed(VectorView &coeff, double t) const
void instance(Ellipse &e, ConstVectorView const &coeff) const
LFMPowerBasis< InstanceType > m_model
void feed(VectorView &coeff, double &known_term, double sample_parameter) const
LFMPoly(size_t degree)
void instance(Poly &poly, ConstVectorView const &raw_data) const
void feed(VectorView &coeff, double sample_parameter) const
LFMPowerBasis(size_t degree)
void instance(SBasis &sb, ConstVectorView const &raw_data) const
LFMSBasis(size_t _order)
void feed(VectorView &coeff, double t) const
size_t size() const
static const bool WITH_FIXED_TERMS
ConstVectorView column_const_view(size_t i) const
Definition matrix.h:70
Two-dimensional point that doubles as a vector.
Definition point.h:66
Polynomial in canonical (monomial) basis.
Definition polynomial.h:50
Polynomial in symmetric power basis.
Definition sbasis.h:70
void resize(unsigned n)
Definition sbasis.h:98
Conic Section.
double c[8][4]
Lifts one dimensional objects into 2D.
Ellipse shape.
@ Y
Definition coord.h:48
@ X
Definition coord.h:48
Various utility functions.
Definition affine.h:22
void binomial_coefficients(std::vector< size_t > &bc, std::size_t n)
Definition utils.cpp:40
Polynomial in canonical (monomial) basis.
Polynomial in symmetric power basis (S-basis)
size_t degree