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 final class Spline {
24    private final float[] mX;
25    private final float[] mY;
26    private final float[] mM;
27
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     */
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     */
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
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