Interpolation over an array (or two)

Question

I'm looking for a java library or some help to write my own interpolation function. That is I have two arrays of doubles which are potentially different sizes, but are ordered. I need to be able to make an estimate of intermediate values, and insert so that both arrays become the same size. In fact the total number of points appearing in the interpolation is the sum of the 2 array sizes minus 1. The range of each array must stay the same however, so there is no extrapolation needed.

eg. a1 = [1, 4, 9, 16, 25, 36] and a2 = [6, 9, 14, 30]

the results could be eg.

a1 = [1, 2.25, 4, 6.25, 9, 12.25, 16, 25, 36] and a2 = [6, 6.5625, 7.25, 9, 10.0625, 11.25, 14, 25.25, 30]

these examples are f(x) = x^2 and g(x) = x^2 + 5, however could easily have been any polynomial - the point is to be able to estimate/approximate the function from the dataset well enough to provide decent enough interpolation. Here the x value is just the index of the input array. In the output only the y values are important.

Answer 1

Simple linear interpolation can be calculated using something like:

Point2D interp1_lin(Point2D p1, Point2D p2, double x) {
 //Pre conditions
assert p1.x<x;
assert x<p2.x;
//Calculate slope from p1 to p2
double m = (p2.x-p1.x)/(p2.y-p1.y);
//Calculate y position of x
double y = (x-p1.x)*m+p1.y;
//create new point
return new Point2D.Double(x,y);
}

Does this help?

Answer 2

public static double[][] interp ( double[] a1, double[] a2 ) {
    double[][] ret = new double[2][a1.length + a2.length];
    // assuming a1 and a2 are sorted
    double part = (a1[a1.length - 1] - a1[0])/(ret[0].length - 1);

    for( int i = 0; i < ret[0].length; i++ ) {
      ret[0][i] = a1[0] + (part * i);
    }
    part = (a2[a2.length - 1] - a2[0])/(ret[1].length - 1);
    for( int i = 0; i < ret[1].length; i++ ) {
      ret[1][i] = a2[0] + (part * i);
    }
    return ret;
  }

Answer 3

You need to get the x-values corresponding to the y-values. Otherwise no algorithm will be able to determine whether [1, 16, 81] is x^2 for [1, 4, 9] or x^4 for [1, 2, 3]. Would you interpolate six values or none?

And then, when you're given the x-values, you can use some sort of interpolation (linear, kubic spline, you name it) to approximate the missing values.

Answer 4

The other answers give you linear interpolations -- these don't really work for complex, nonlinear data. You want a spline fit, (spline interpolation) I believe.

Spline fits describe regions of the data using a set of control points from the data, then apply a polynomial interpolation between control points. More control points gives you a more accurate fit, less a more general fit. Splines are much more accurate than linear fits, faster to use than a general regression fit, better than a high-order polynomial because it won't do crazy things between control points.

I can't remember names off the top of my head, but there are some excellent fitting libraries in Java -- I suggest you look for one rather than writing your own function.

---

**EDIT: Libraries that might be useful: **

• JMSL
• JSpline+
• Curfitting library (hope you can read German)

** Theory/code that may be useful: **

• Spline applets with code: link
• Arkan spline fitting for poly-lines to bezier splines
• Theory of splines, and some math for fitting. More math, less code, might help if the libraries don't.