1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.util; 18 19 /** 20 * Performs spline interpolation given a set of control points. 21 * @hide 22 */ 23 public final class Spline { 24 private final float[] mX; 25 private final float[] mY; 26 private final float[] mM; 27 Spline(float[] x, float[] y, float[] m)28 private Spline(float[] x, float[] y, float[] m) { 29 mX = x; 30 mY = y; 31 mM = m; 32 } 33 34 /** 35 * Creates a monotone cubic spline from a given set of control points. 36 * 37 * The spline is guaranteed to pass through each control point exactly. 38 * Moreover, assuming the control points are monotonic (Y is non-decreasing or 39 * non-increasing) then the interpolated values will also be monotonic. 40 * 41 * This function uses the Fritsch-Carlson method for computing the spline parameters. 42 * http://en.wikipedia.org/wiki/Monotone_cubic_interpolation 43 * 44 * @param x The X component of the control points, strictly increasing. 45 * @param y The Y component of the control points, monotonic. 46 * @return 47 * 48 * @throws IllegalArgumentException if the X or Y arrays are null, have 49 * different lengths or have fewer than 2 values. 50 * @throws IllegalArgumentException if the control points are not monotonic. 51 */ createMonotoneCubicSpline(float[] x, float[] y)52 public static Spline createMonotoneCubicSpline(float[] x, float[] y) { 53 if (x == null || y == null || x.length != y.length || x.length < 2) { 54 throw new IllegalArgumentException("There must be at least two control " 55 + "points and the arrays must be of equal length."); 56 } 57 58 final int n = x.length; 59 float[] d = new float[n - 1]; // could optimize this out 60 float[] m = new float[n]; 61 62 // Compute slopes of secant lines between successive points. 63 for (int i = 0; i < n - 1; i++) { 64 float h = x[i + 1] - x[i]; 65 if (h <= 0f) { 66 throw new IllegalArgumentException("The control points must all " 67 + "have strictly increasing X values."); 68 } 69 d[i] = (y[i + 1] - y[i]) / h; 70 } 71 72 // Initialize the tangents as the average of the secants. 73 m[0] = d[0]; 74 for (int i = 1; i < n - 1; i++) { 75 m[i] = (d[i - 1] + d[i]) * 0.5f; 76 } 77 m[n - 1] = d[n - 2]; 78 79 // Update the tangents to preserve monotonicity. 80 for (int i = 0; i < n - 1; i++) { 81 if (d[i] == 0f) { // successive Y values are equal 82 m[i] = 0f; 83 m[i + 1] = 0f; 84 } else { 85 float a = m[i] / d[i]; 86 float b = m[i + 1] / d[i]; 87 if (a < 0f || b < 0f) { 88 throw new IllegalArgumentException("The control points must have " 89 + "monotonic Y values."); 90 } 91 float h = FloatMath.hypot(a, b); 92 if (h > 9f) { 93 float t = 3f / h; 94 m[i] = t * a * d[i]; 95 m[i + 1] = t * b * d[i]; 96 } 97 } 98 } 99 return new Spline(x, y, m); 100 } 101 102 /** 103 * Interpolates the value of Y = f(X) for given X. 104 * Clamps X to the domain of the spline. 105 * 106 * @param x The X value. 107 * @return The interpolated Y = f(X) value. 108 */ interpolate(float x)109 public float interpolate(float x) { 110 // Handle the boundary cases. 111 final int n = mX.length; 112 if (Float.isNaN(x)) { 113 return x; 114 } 115 if (x <= mX[0]) { 116 return mY[0]; 117 } 118 if (x >= mX[n - 1]) { 119 return mY[n - 1]; 120 } 121 122 // Find the index 'i' of the last point with smaller X. 123 // We know this will be within the spline due to the boundary tests. 124 int i = 0; 125 while (x >= mX[i + 1]) { 126 i += 1; 127 if (x == mX[i]) { 128 return mY[i]; 129 } 130 } 131 132 // Perform cubic Hermite spline interpolation. 133 float h = mX[i + 1] - mX[i]; 134 float t = (x - mX[i]) / h; 135 return (mY[i] * (1 + 2 * t) + h * mM[i] * t) * (1 - t) * (1 - t) 136 + (mY[i + 1] * (3 - 2 * t) + h * mM[i + 1] * (t - 1)) * t * t; 137 } 138 139 // For debugging. 140 @Override toString()141 public String toString() { 142 StringBuilder str = new StringBuilder(); 143 final int n = mX.length; 144 str.append("["); 145 for (int i = 0; i < n; i++) { 146 if (i != 0) { 147 str.append(", "); 148 } 149 str.append("(").append(mX[i]); 150 str.append(", ").append(mY[i]); 151 str.append(": ").append(mM[i]).append(")"); 152 } 153 str.append("]"); 154 return str.toString(); 155 } 156 } 157