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 abstract class Spline { 24 25 /** 26 * Interpolates the value of Y = f(X) for given X. 27 * Clamps X to the domain of the spline. 28 * 29 * @param x The X value. 30 * @return The interpolated Y = f(X) value. 31 */ 32 public abstract float interpolate(float x); 33 34 /** 35 * Creates an appropriate spline based on the properties of the control points. 36 * 37 * If the control points are monotonic then the resulting spline will preserve that and 38 * otherwise optimize for error bounds. 39 */ 40 public static Spline createSpline(float[] x, float[] y) { 41 if (!isStrictlyIncreasing(x)) { 42 throw new IllegalArgumentException("The control points must all have strictly " 43 + "increasing X values."); 44 } 45 46 if (isMonotonic(y)) { 47 return createMonotoneCubicSpline(x, y); 48 } else { 49 return createLinearSpline(x, y); 50 } 51 } 52 53 /** 54 * Creates a monotone cubic spline from a given set of control points. 55 * 56 * The spline is guaranteed to pass through each control point exactly. 57 * Moreover, assuming the control points are monotonic (Y is non-decreasing or 58 * non-increasing) then the interpolated values will also be monotonic. 59 * 60 * This function uses the Fritsch-Carlson method for computing the spline parameters. 61 * http://en.wikipedia.org/wiki/Monotone_cubic_interpolation 62 * 63 * @param x The X component of the control points, strictly increasing. 64 * @param y The Y component of the control points, monotonic. 65 * @return 66 * 67 * @throws IllegalArgumentException if the X or Y arrays are null, have 68 * different lengths or have fewer than 2 values. 69 * @throws IllegalArgumentException if the control points are not monotonic. 70 */ 71 public static Spline createMonotoneCubicSpline(float[] x, float[] y) { 72 return new MonotoneCubicSpline(x, y); 73 } 74 75 /** 76 * Creates a linear spline from a given set of control points. 77 * 78 * Like a monotone cubic spline, the interpolated curve will be monotonic if the control points 79 * are monotonic. 80 * 81 * @param x The X component of the control points, strictly increasing. 82 * @param y The Y component of the control points. 83 * @return 84 * 85 * @throws IllegalArgumentException if the X or Y arrays are null, have 86 * different lengths or have fewer than 2 values. 87 * @throws IllegalArgumentException if the X components of the control points are not strictly 88 * increasing. 89 */ 90 public static Spline createLinearSpline(float[] x, float[] y) { 91 return new LinearSpline(x, y); 92 } 93 94 private static boolean isStrictlyIncreasing(float[] x) { 95 if (x == null || x.length < 2) { 96 throw new IllegalArgumentException("There must be at least two control points."); 97 } 98 float prev = x[0]; 99 for (int i = 1; i < x.length; i++) { 100 float curr = x[i]; 101 if (curr <= prev) { 102 return false; 103 } 104 prev = curr; 105 } 106 return true; 107 } 108 109 private static boolean isMonotonic(float[] x) { 110 if (x == null || x.length < 2) { 111 throw new IllegalArgumentException("There must be at least two control points."); 112 } 113 float prev = x[0]; 114 for (int i = 1; i < x.length; i++) { 115 float curr = x[i]; 116 if (curr < prev) { 117 return false; 118 } 119 prev = curr; 120 } 121 return true; 122 } 123 124 public static class MonotoneCubicSpline extends Spline { 125 private float[] mX; 126 private float[] mY; 127 private float[] mM; 128 129 public MonotoneCubicSpline(float[] x, float[] y) { 130 if (x == null || y == null || x.length != y.length || x.length < 2) { 131 throw new IllegalArgumentException("There must be at least two control " 132 + "points and the arrays must be of equal length."); 133 } 134 135 final int n = x.length; 136 float[] d = new float[n - 1]; // could optimize this out 137 float[] m = new float[n]; 138 139 // Compute slopes of secant lines between successive points. 140 for (int i = 0; i < n - 1; i++) { 141 float h = x[i + 1] - x[i]; 142 if (h <= 0f) { 143 throw new IllegalArgumentException("The control points must all " 144 + "have strictly increasing X values."); 145 } 146 d[i] = (y[i + 1] - y[i]) / h; 147 } 148 149 // Initialize the tangents as the average of the secants. 150 m[0] = d[0]; 151 for (int i = 1; i < n - 1; i++) { 152 m[i] = (d[i - 1] + d[i]) * 0.5f; 153 } 154 m[n - 1] = d[n - 2]; 155 156 // Update the tangents to preserve monotonicity. 157 for (int i = 0; i < n - 1; i++) { 158 if (d[i] == 0f) { // successive Y values are equal 159 m[i] = 0f; 160 m[i + 1] = 0f; 161 } else { 162 float a = m[i] / d[i]; 163 float b = m[i + 1] / d[i]; 164 if (a < 0f || b < 0f) { 165 throw new IllegalArgumentException("The control points must have " 166 + "monotonic Y values."); 167 } 168 float h = (float) Math.hypot(a, b); 169 if (h > 3f) { 170 float t = 3f / h; 171 m[i] *= t; 172 m[i + 1] *= t; 173 } 174 } 175 } 176 177 mX = x; 178 mY = y; 179 mM = m; 180 } 181 182 @Override 183 public float interpolate(float x) { 184 // Handle the boundary cases. 185 final int n = mX.length; 186 if (Float.isNaN(x)) { 187 return x; 188 } 189 if (x <= mX[0]) { 190 return mY[0]; 191 } 192 if (x >= mX[n - 1]) { 193 return mY[n - 1]; 194 } 195 196 // Find the index 'i' of the last point with smaller X. 197 // We know this will be within the spline due to the boundary tests. 198 int i = 0; 199 while (x >= mX[i + 1]) { 200 i += 1; 201 if (x == mX[i]) { 202 return mY[i]; 203 } 204 } 205 206 // Perform cubic Hermite spline interpolation. 207 float h = mX[i + 1] - mX[i]; 208 float t = (x - mX[i]) / h; 209 return (mY[i] * (1 + 2 * t) + h * mM[i] * t) * (1 - t) * (1 - t) 210 + (mY[i + 1] * (3 - 2 * t) + h * mM[i + 1] * (t - 1)) * t * t; 211 } 212 213 // For debugging. 214 @Override 215 public String toString() { 216 StringBuilder str = new StringBuilder(); 217 final int n = mX.length; 218 str.append("MonotoneCubicSpline{["); 219 for (int i = 0; i < n; i++) { 220 if (i != 0) { 221 str.append(", "); 222 } 223 str.append("(").append(mX[i]); 224 str.append(", ").append(mY[i]); 225 str.append(": ").append(mM[i]).append(")"); 226 } 227 str.append("]}"); 228 return str.toString(); 229 } 230 } 231 232 public static class LinearSpline extends Spline { 233 private final float[] mX; 234 private final float[] mY; 235 private final float[] mM; 236 237 public LinearSpline(float[] x, float[] y) { 238 if (x == null || y == null || x.length != y.length || x.length < 2) { 239 throw new IllegalArgumentException("There must be at least two control " 240 + "points and the arrays must be of equal length."); 241 } 242 final int N = x.length; 243 mM = new float[N-1]; 244 for (int i = 0; i < N-1; i++) { 245 mM[i] = (y[i+1] - y[i]) / (x[i+1] - x[i]); 246 } 247 mX = x; 248 mY = y; 249 } 250 251 @Override 252 public float interpolate(float x) { 253 // Handle the boundary cases. 254 final int n = mX.length; 255 if (Float.isNaN(x)) { 256 return x; 257 } 258 if (x <= mX[0]) { 259 return mY[0]; 260 } 261 if (x >= mX[n - 1]) { 262 return mY[n - 1]; 263 } 264 265 // Find the index 'i' of the last point with smaller X. 266 // We know this will be within the spline due to the boundary tests. 267 int i = 0; 268 while (x >= mX[i + 1]) { 269 i += 1; 270 if (x == mX[i]) { 271 return mY[i]; 272 } 273 } 274 return mY[i] + mM[i] * (x - mX[i]); 275 } 276 277 @Override 278 public String toString() { 279 StringBuilder str = new StringBuilder(); 280 final int n = mX.length; 281 str.append("LinearSpline{["); 282 for (int i = 0; i < n; i++) { 283 if (i != 0) { 284 str.append(", "); 285 } 286 str.append("(").append(mX[i]); 287 str.append(", ").append(mY[i]); 288 if (i < n-1) { 289 str.append(": ").append(mM[i]); 290 } 291 str.append(")"); 292 } 293 str.append("]}"); 294 return str.toString(); 295 } 296 } 297 } 298
