Interpolation over an array (or two)

Question

I am looking for a java library or some help for writing my own interpolation function. That is, I have two arrays of doubles, which can be of different sizes, but ordered. I need to evaluate the intermediate values ​​and insert so that both arrays become the same size. In fact, the total number of points that appear in the interpolation is the sum of the two sizes of the array minus 1. The range of each array must remain unchanged, so there is no need for extrapolation.

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

results may be for example

a1 = [1, 2.25, 4, 6.25, 9, 12.25, 16, 25, 36] and also 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, they could easily be any polynomial - the point should be able to evaluate / approximate the function from the data set well enough to provide enough interpolation. Here, the value of x is only the index of the input array. The output y values ​​are important.

Answer 1

Other answers give you linear interpolations - they really don't work for complex non-linear data. You want a spline fit , (spline interpolation) I think.

A spline is suitable for describing data areas using a set of control points from the data, then applies polynomial interpolation between the control points. More control points gives you a more accurate fit, less general shape. Splines are much more accurate than linear ones, faster to use than general regression, better than a high-order polynomial, because it won’t do crazy things between control points.

I can't remember the names above, but Java has great libraries to fit - I suggest you look for one rather than write your own function.

---

** EDIT: Libraries that may be useful: **

• Jmsl
• JSpline +
• Correction library (I hope you can read German)

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

• Spline applets with code: link
• Arkan spline fitting for multilinear splines splines
• Spline theory and some math to fit. More math, less code, can help if libraries are down.

Answer 2

Designed for ONE Dimension Dataset

 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; } } 

I don’t know if this helps ... This is very quickly encoded, so if someone has a nicer / more efficient way to do the same, thanks for the contribution.

APPLICATION:

 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 3

I know this is an old answer, but this is Google's first hit when looking for Java interpolation. The accepted answer contains useful links, but JMSL needs to be purchased, and the JSpline + website looks fragmentary.

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

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

Answer 4

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 it help?

Answer 5

You need to get the x values ​​corresponding to the y values. Otherwise, no algorithm can determine whether [1, 16, 81] is x ^ 2 for [1, 4, 9] or x ^ 4 for [1, 2, 3]. Do you interpolate six values ​​or not?

And then, when you are assigned x values, you can use some interpolation (linear, cubic spline, you name it) to approximate the missing values.

Answer 6

Light version of a linear interpolator of a one-dimensional array:

 public static float[] interpolate(float[] data) { int startIdx = -1; float startValue = 0f; float element; for (int i = 0; i < data.length - 1; i++) { element = data[i]; if (element != 0f) { if (startIdx != -1) { doInterpolate(startValue, element, startIdx + 1, i - startIdx - 1, data); } startValue = element; startIdx = i; } } return data; } private static void doInterpolate(float start, float end, int startIdx, int count, float[] data) { float delta = (end - start) / (count + 1); for (int i = startIdx; i < startIdx + count; i++) { data[i] = start + delta * (i - startIdx + 1); } } 

Answer 7

Be very careful with splines and polynomial adjustments. These two can give meaningless behavior that can disrupt many uses (which are considered to be presentations) of data.

Everything that uses the derivatives (slopes) of the data can be completely destroyed.

The best thing you can do is build the data, understand what they are doing, and only then substitute (linear, polynomial, logarithmic) regression; as soon as you do this, you should build your own command over the source data and make sure that you see reasonable agreement. Skipping this comparative step is a very bad idea.

Some datasets do not lend themselves to fitting polynomials, log-log, etc .; if your data points are appropriately distributed over a data range, there is nothing wrong with piecewise interpolation (linear or polynomial, etc.). To defeat a dead horse if you use piecewise interpolation, avoid anything that uses the derivatives / tilts of your piecewise interpolation, because it will have gaps and cause things to behave badly.

Answer 8

you can use apache commons-math function interpolation like SplineInterpolator