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
17package android.util;
18
19/**
20 * Performs spline interpolation given a set of control points.
21 * @hide
22 */
23public 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 = FloatMath.hypot(a, b);
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        }
296    }
297}
298