Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 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 | */ |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 23 | public abstract class Spline { |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 24 | |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 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 | } |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 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) { |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 72 | return new MonotoneCubicSpline(x, y); |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 73 | } |
| 74 | |
| 75 | /** |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 76 | * Creates a linear spline from a given set of control points. |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 77 | * |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 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. |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 89 | */ |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 90 | public static Spline createLinearSpline(float[] x, float[] y) { |
| 91 | return new LinearSpline(x, y); |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 92 | } |
| 93 | |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 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."); |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 97 | } |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 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 | } |
Nick Kralevich | bf96737 | 2014-10-18 13:29:04 -0700 | [diff] [blame] | 168 | float h = (float) Math.hypot(a, b); |
Michael Wright | 3e9a134 | 2014-08-28 17:42:16 -0700 | [diff] [blame] | 169 | if (h > 9f) { |
| 170 | float t = 3f / h; |
| 171 | m[i] = t * a * d[i]; |
| 172 | m[i + 1] = t * b * d[i]; |
| 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 | } |
Jeff Brown | 1a30b55 | 2012-08-16 01:31:11 -0700 | [diff] [blame] | 296 | } |
| 297 | } |