/usr/include/CGAL/Polynomial/Interpolator.h is in libcgal-dev 4.7-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | // Copyright (c) 2008 Max-Planck-Institute Saarbruecken (Germany)
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; either version 3 of the License,
// or (at your option) any later version.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL$
// $Id$
//
//
// Author(s) : Michael Hemmer <hemmer@informatik.uni-mainz.de>
#ifndef CGAL_POLYNOMIAL_INTERPOLATE_H
#define CGAL_POLYNOMIAL_INTERPOLATE_H
namespace CGAL {
namespace internal {
// Class for interpolation of univariate or multivariate polynomials.
// The template argument must be a model of concept Polynomial_d
//
//
template <class Polynomial_d_>
class Interpolator{
typedef CGAL::Polynomial_traits_d<Polynomial_d_> PT;
public:
typedef typename PT::Polynomial_d Polynomial_d;
typedef typename PT::Coefficient_type Coeff;
typedef typename PT::Innermost_coefficient_type IC;
private:
typedef typename CGAL::Coercion_traits<Coeff,IC>::Cast IC2Coeff;
typedef typename PT::Construct_polynomial Construct;
std::vector<IC> xvals;
std::vector<Coeff> yvals;
std::vector<Coeff> b;
bool valid;
Polynomial_d interpolant;
Coeff eval_newton(int n, IC z)
{
Coeff p(b[n]);
for (int i = n-1; i >=0; i--){
Coeff tmp(IC2Coeff()((z - xvals[i])));
p = p * tmp + b[i];
}
return p;
}
Polynomial_d eval_newton_poly(int n)
{
CGAL_precondition(n >=0);
Polynomial_d p(Construct()(b[n]));
for (int i = n-1; i >=0; i--) {
Polynomial_d tmp = Construct()(IC2Coeff()(-xvals[i]),Coeff(1));
p = (p * tmp) + b[i];
}
return p;
}
public:
Interpolator(){};
// constructor from an InputIterator range with value type std::pair<IC,Coeff>
template<class InputIterator>
Interpolator(InputIterator begin, InputIterator end){
for(InputIterator it = begin; it != end; it++){
add_interpolation_point(*it);
}
}
/*
Interpolator(std::vector<IC> xvals_, std::vector<Coeff> yvals_)
: valid(false) {
CGAL_precondition(xvals_.size() != 0);
CGAL_precondition(xvals_.size() == yvals_.size());
for(unsigned i = 0; i < xvals_.size(); i++){
add_interpolation_point(xvals_[i],yvals_[i]);
}
}
*/
// void add_interpolation_point(std::pair<IC,Coeff> point){
// add_interpolation_point(point.first, point.second);
// }
// void add_interpolation_point(IC xval, Coeff yval){
void add_interpolation_point(std::pair<IC,Coeff> point){
valid = false;
// CGAL_precondition(0 == std::count(xval, xvals.begin(), yvals.end()));
xvals.push_back(point.first);
yvals.push_back(point.second);
Coeff num, den;
int k = static_cast<int>(xvals.size()) - 1;
if(k == 0){
b.push_back(yvals[0]);
}else{
num = yvals[k] - eval_newton(k-1,xvals[k]);
den = Coeff(1);
for (int j = 0; j < k; j++) {
// (k-j) if xvals's are sequential
den *= (xvals[k] - xvals[j]);
}
b.push_back(num / den);
}
}
Polynomial_d get_interpolant(){
if (xvals.size() == 0) return Polynomial_d(0);
// TODO: compute new interpolant from old interpolant ?
if(!valid)
interpolant = eval_newton_poly(static_cast<int>(xvals.size())-1);
return interpolant;
}
};
} // namespace internal
} //namespace CGAL
#endif // CGAL_POLYNOMIAL_INTERPOLATE_H
|