core/vnl/vnl_real_polynomial.cxx
Go to the documentation of this file.
00001 // This is core/vnl/vnl_real_polynomial.cxx
00002 #ifdef VCL_NEEDS_PRAGMA_INTERFACE
00003 #pragma implementation
00004 #endif
00005 //:
00006 // \file
00007 // \brief Evaluation of real polynomials - the implementation
00008 // \author Andrew W. Fitzgibbon, Oxford RRG 23 Aug 96
00009 //
00010 // Modifications
00011 // IMS (Manchester) 14/03/2001: Added Manchester IO scheme
00012 
00013 #include "vnl_real_polynomial.h"
00014 #include <vcl_iostream.h>
00015 #include <vcl_complex.h>
00016 #include <vcl_cmath.h>
00017 
00018 // This is replacing a member template...
00019 template <class T>
00020 T vnl_real_polynomial_evaluate(double const *a, int n, T const& x)
00021 {
00022   --n;
00023   T acc = a[n];
00024   T xn = x;
00025   while (n) {
00026     acc += a[--n] * xn;
00027     xn *= x;
00028   } ;
00029 
00030   return acc;
00031 }
00032 
00033 // The following code confuses doxygen, causing it to link every
00034 // mention of double to vnl_real_polynomial::evaluate
00035 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00036 # ifdef VCL_WIN32
00037 #  define SELECT(T) <T >
00038 # else
00039 #  define SELECT(T)
00040 # endif
00041 
00042 //: Instantiate templates before use
00043 template double vnl_real_polynomial_evaluate SELECT(double )
00044       (double const*,int,double const&);
00045 template vcl_complex<double> vnl_real_polynomial_evaluate SELECT(vcl_complex<double>)
00046       (double const*,int,vcl_complex<double> const&);
00047 
00048 //: Evaluate polynomial at value x
00049 double vnl_real_polynomial::evaluate(double x) const
00050 {
00051   return vnl_real_polynomial_evaluate SELECT(double)(coeffs_.data_block(), coeffs_.size(), x);
00052 }
00053 
00054 
00055 //: Evaluate polynomial at complex value x
00056 vcl_complex<double> vnl_real_polynomial::evaluate(vcl_complex<double> const& x) const
00057 {
00058   return vnl_real_polynomial_evaluate SELECT(vcl_complex<double>)
00059      (coeffs_.data_block(), coeffs_.size(), x);
00060 }
00061 #endif // DOXYGEN_SHOULD_SKIP_THIS
00062 
00063 //: Evaluate derivative at value x.
00064 double vnl_real_polynomial::devaluate(double x) const
00065 {
00066   return derivative().evaluate(x);
00067 }
00068 
00069 
00070 //: Evaluate derivative at complex value x. Not implemented.
00071 vcl_complex<double> vnl_real_polynomial::devaluate(vcl_complex<double> const& x) const
00072 {
00073   return derivative().evaluate(x);
00074 }
00075 
00076 //: Evaluate integral at x (assuming constant of integration is zero)
00077 double vnl_real_polynomial::evaluate_integral(double x) const
00078 {
00079   int d = coeffs_.size()-1;
00080   const double* f = coeffs_.data_block();
00081   double sum = 0.0;
00082   int di=1;
00083   double xi=x;
00084   for (int i=d;i>=0;--i)
00085   {
00086     sum += f[i]*xi/di;
00087     xi*=x;
00088     di++;
00089   }
00090 
00091   return sum;
00092 }
00093 
00094 //: Evaluate integral between x1 and x2
00095 double vnl_real_polynomial::evaluate_integral(double x1, double x2) const
00096 {
00097   return evaluate_integral(x2)-evaluate_integral(x1);
00098 }
00099 
00100 //: Returns sum of two polynomials f1(x)+f2(x)
00101 vnl_real_polynomial operator+(const vnl_real_polynomial& f1, const vnl_real_polynomial& f2)
00102 {
00103   // Degree of result is highest of the two inputs
00104   int d1=f1.degree();
00105   int d2=f2.degree();
00106   int d = d1;
00107   if (d2>d) d=d2;
00108 
00109   vnl_real_polynomial sum(d);
00110 
00111   // Coefficients are stored such that f(i) is coef. on x^(d-i)
00112   for (int i=0;i<=d;++i)
00113   {
00114     sum[d-i]=0.0;
00115     if (i<=d1) sum[d-i]+=f1[d1-i];
00116     if (i<=d2) sum[d-i]+=f2[d2-i];
00117   }
00118 
00119   return sum;
00120 }
00121 
00122 //: Returns sum of two polynomials f1(x)-f2(x)
00123 vnl_real_polynomial operator-(const vnl_real_polynomial& f1, const vnl_real_polynomial& f2)
00124 {
00125   // Degree of result is highest of the two inputs
00126   int d1=f1.degree();
00127   int d2=f2.degree();
00128   int d = d1;
00129   if (d2>d) d=d2;
00130 
00131   vnl_real_polynomial diff(d);
00132 
00133   // Coefficients are stored such that f(i) is coef. on x^(d-i)
00134   for (int i=0;i<=d;++i)
00135   {
00136     diff[d-i]=0.0;
00137     if (i<=d1) diff[d-i]+=f1[d1-i];
00138     if (i<=d2) diff[d-i]-=f2[d2-i];
00139   }
00140 
00141   return diff;
00142 }
00143 
00144 //: Returns polynomial which is product of two polynomials f1(x)*f2(x)
00145 vnl_real_polynomial operator*(const vnl_real_polynomial& f1, const vnl_real_polynomial& f2)
00146 {
00147   int d1=f1.degree();
00148   int d2=f2.degree();
00149   int d = d1+d2;
00150 
00151   vnl_real_polynomial prod(d);
00152   prod.coefficients().fill(0.0);
00153 
00154   for (int i=0;i<=d1;++i)
00155     for (int j=0;j<=d2;++j)
00156       prod[d-(i+j)] += f1[d1-i]*f2[d2-j];
00157 
00158   return prod;
00159 }
00160 //: Add rhs to this and return *this
00161 vnl_real_polynomial& vnl_real_polynomial::operator+=(vnl_real_polynomial const& rhs){
00162   *this = (*this) + rhs;
00163   return *this;
00164 }
00165 
00166 //: Subtract rhs from this and return *this
00167 vnl_real_polynomial& vnl_real_polynomial::operator-=(vnl_real_polynomial const& rhs){
00168   *this = (*this) - rhs;
00169   return *this;
00170 }
00171 
00172 //: multiply rhs with this and return *this
00173 vnl_real_polynomial& vnl_real_polynomial::operator*=(vnl_real_polynomial const& rhs){
00174   *this = (*this) * rhs;
00175   return *this;
00176 }
00177 
00178 //: Returns RMS difference between f1 and f2 over range [x1,x2]
00179 // $\frac1{\sqrt{|x_2-x_1|}}\,\sqrt{\int_{x_1}^{x_2}\left(f_1(x)-f_2(x)\right)^2\,dx}$
00180 double vnl_rms_difference(const vnl_real_polynomial& f1, const vnl_real_polynomial& f2,
00181                           double x1, double x2)
00182 {
00183   double dx = vcl_fabs(x2-x1);
00184   if (dx==0.0) return 0;
00185 
00186   vnl_real_polynomial df = f2-f1;
00187   vnl_real_polynomial df2 = df*df;
00188   double area = vcl_fabs(df2.evaluate_integral(x1,x2));
00189   return vcl_sqrt(area/dx);
00190 }
00191 
00192 //: Return derivative of this polynomial
00193 vnl_real_polynomial vnl_real_polynomial::derivative() const
00194 {
00195   int d = degree();
00196   vnl_vector<double> cd (d);
00197   for (int i=d-1,di=1; i>=0; --i,++di)
00198     cd[i] = coeffs_[i] * di;
00199   return vnl_real_polynomial(cd);
00200 }
00201 
00202 //: Return primitive function (inverse derivative) of this polynomial
00203 // Since a primitive function is not unique, the one with constant = 0 is returned
00204 vnl_real_polynomial vnl_real_polynomial::primitive() const
00205 {
00206   int d = coeffs_.size(); // degree+1
00207   vnl_vector<double> cd (d+1);
00208   cd[d] = 0.0; // constant term
00209   for (int i=d-1,di=1; i>=0; --i,++di)
00210     cd[i] = coeffs_[i] / di;
00211   return vnl_real_polynomial(cd);
00212 }
00213 
00214 void vnl_real_polynomial::print(vcl_ostream& os) const
00215 {
00216   int d = degree();
00217   bool first_coeff = true; // to avoid '+' in front of equation
00218 
00219   for (int i = 0; i <= d; ++i) {
00220     if (coeffs_[i] == 0.0) continue;
00221     os << ' ';
00222     if (coeffs_[i] > 0.0 && !first_coeff) os << '+';
00223     if (i==d)                           os << coeffs_[i]; // the 0-degree coeff should always be output if not zero
00224     else if (coeffs_[i] == -1.0)        os << '-';
00225     else if (coeffs_[i] != 1.0)         os << coeffs_[i] << ' ';
00226 
00227     if (i < d-1)                        os << "X^" << d-i;
00228     else if (i == d-1)                  os << 'X';
00229     first_coeff = false;
00230   }
00231   if (first_coeff) os << " 0";
00232 }