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

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.

Answer 2

you can use apache commons-math interpolation functions, such as SplineInterpolator

Answer 3

I know this is an old answer, but it's the first google hit when searching for Java interpolation. The accepted answer provides some helpful links, but JMSL must be purchased, and the JSpline+ website looks sketchy.

Apache Commons Math has implementations of linear and spline interpolations that appear simple, functional, and trustworthy.

http://commons.apache.org/proper/commons-math/

Answer 4

Designed for ONE Dimension data array

import java.util.ArrayList;

public class Interpolator {

public static Float CosineInterpolate(Float y1,Float y2,Float mu)
{
    double mu2;

    mu2 = (1.0f-Math.cos(mu*Math.PI))/2.0f;
    Float f_mu2 = new Float(mu2);
    return(y1*(1.0f-f_mu2)+y2*f_mu2);
}

public static Float LinearInterpolate(Float y1,Float y2,Float mu)
{
    return(y1*(1-mu)+y2*mu);
}


public static Float[] Interpolate(Float[] a, String mode) {

    // Check that have at least the very first and very last values non-null
    if (!(a[0] != null && a[a.length-1] != null)) return null;

    ArrayList<Integer> non_null_idx = new ArrayList<Integer>();
    ArrayList<Integer> steps = new ArrayList<Integer>();

    int step_cnt = 0;
    for (int i=0; i<a.length; i++)
    {
        if (a[i] != null)
        {
            non_null_idx.add(i);
            if (step_cnt != 0) {
                steps.add(step_cnt);
                System.err.println("aDDed step >> " + step_cnt);
            }
            step_cnt = 0;
        }
        else
        {
            step_cnt++;
        }
    }

    Float f_start = null;
    Float f_end = null;
    Float f_step = null;
    Float f_mu = null;

    int i = 0;
    while (i < a.length - 1) // Don't do anything for the very last element (which should never be null)
    {
        if (a[i] != null && non_null_idx.size() > 1 && steps.size() > 0)
        {
            f_start = a[non_null_idx.get(0)];
            f_end = a[non_null_idx.get(1)];
            f_step = new Float(1.0) / new Float(steps.get(0) + 1);
            f_mu = f_step;
            non_null_idx.remove(0);
            steps.remove(0);
        }
        else if (a[i] == null)
        {
            if (mode.equalsIgnoreCase("cosine"))
                a[i] = CosineInterpolate(f_start, f_end, f_mu);
            else
                a[i] = LinearInterpolate(f_start, f_end, f_mu);
            f_mu += f_step;
        }
        i++;
    }

    return a;
}
}

Don't know if it helps... It is very fast coded, so if anyone has a nicer / more performing way to do the same, thank for contributing.

USAGE:

input : Float[] a = {1.0f, null, null, 2.0f, null, null, null, 15.0f};

call : Interpolator.Interpolate(a, "Linear");

output : 1.0|1.3333333|1.6666667|2.0|5.25|8.5|11.75|15.0

Answer 5

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 6

be very careful with spline-fits and polynomial fits. These two can give nonsensical behavior that can derail many uses of (what is believed to be a representation of) the data.

Anything that uses derivatives (slopes) of data can be totally derailed.

Best thing you can do is plot the data, understand what it's doing, and only then fit (linear, polynomial, log-log) regression; once you've done that you should plot your fit over the original data and make sure you see reasonable agreement. Skipping this comparison-step is a very bad idea.

Certain data-sets will not yield to fitting of polynomials, log-log etc..; if your data-points are appropriately distributed over the range of data there's nothing wrong with piecewise-interpolation (linear or polynomial etc.). To beat a dead horse, if you use piecewise interpolation avoid anything that uses derivatives/slopes of your piecewise interpolation because it will have discontinuities and will cause things to behave badly.