android/util/Spline.java

/*
 * Copyright (C) 2012 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package android.util;

/**
 * Performs spline interpolation given a set of control points.
 * @hide
 */
public abstract class Spline {

    /**
     * Interpolates the value of Y = f(X) for given X.
     * Clamps X to the domain of the spline.
     *
     * @param x The X value.
     * @return The interpolated Y = f(X) value.
     */
    public abstract float interpolate(float x);

    /**
     * Creates an appropriate spline based on the properties of the control points.
     *
     * If the control points are monotonic then the resulting spline will preserve that and
     * otherwise optimize for error bounds.
     */
    public static Spline createSpline(float[] x, float[] y) {
        if (!isStrictlyIncreasing(x)) {
            throw new IllegalArgumentException("The control points must all have strictly "
                    + "increasing X values.");
        }

        if (isMonotonic(y)) {
            return createMonotoneCubicSpline(x, y);
        } else {
            return createLinearSpline(x, y);
        }
    }

    /**
     * Creates a monotone cubic spline from a given set of control points.
     *
     * The spline is guaranteed to pass through each control point exactly.
     * Moreover, assuming the control points are monotonic (Y is non-decreasing or
     * non-increasing) then the interpolated values will also be monotonic.
     *
     * This function uses the Fritsch-Carlson method for computing the spline parameters.
     * http://en.wikipedia.org/wiki/Monotone_cubic_interpolation
     *
     * @param x The X component of the control points, strictly increasing.
     * @param y The Y component of the control points, monotonic.
     * @return
     *
     * @throws IllegalArgumentException if the X or Y arrays are null, have
     * different lengths or have fewer than 2 values.
     * @throws IllegalArgumentException if the control points are not monotonic.
     */
    public static Spline createMonotoneCubicSpline(float[] x, float[] y) {
        return new MonotoneCubicSpline(x, y);
    }

    /**
     * Creates a linear spline from a given set of control points.
     *
     * Like a monotone cubic spline, the interpolated curve will be monotonic if the control points
     * are monotonic.
     *
     * @param x The X component of the control points, strictly increasing.
     * @param y The Y component of the control points.
     * @return
     *
     * @throws IllegalArgumentException if the X or Y arrays are null, have
     * different lengths or have fewer than 2 values.
     * @throws IllegalArgumentException if the X components of the control points are not strictly
     * increasing.
     */
    public static Spline createLinearSpline(float[] x, float[] y) {
        return new LinearSpline(x, y);
    }

    private static boolean isStrictlyIncreasing(float[] x) {
        if (x == null || x.length < 2) {
            throw new IllegalArgumentException("There must be at least two control points.");
        }
        float prev = x[0];
        for (int i = 1; i < x.length; i++) {
            float curr = x[i];
            if (curr <= prev) {
                return false;
            }
            prev = curr;
        }
        return true;
    }

    private static boolean isMonotonic(float[] x) {
        if (x == null || x.length < 2) {
            throw new IllegalArgumentException("There must be at least two control points.");
        }
        float prev = x[0];
        for (int i = 1; i < x.length; i++) {
            float curr = x[i];
            if (curr < prev) {
                return false;
            }
            prev = curr;
        }
        return true;
    }

    public static class MonotoneCubicSpline extends Spline {
        private float[] mX;
        private float[] mY;
        private float[] mM;

        public MonotoneCubicSpline(float[] x, float[] y) {
            if (x == null || y == null || x.length != y.length || x.length < 2) {
                throw new IllegalArgumentException("There must be at least two control "
                        + "points and the arrays must be of equal length.");
            }

            final int n = x.length;
            float[] d = new float[n - 1]; // could optimize this out
            float[] m = new float[n];

            // Compute slopes of secant lines between successive points.
            for (int i = 0; i < n - 1; i++) {
                float h = x[i + 1] - x[i];
                if (h <= 0f) {
                    throw new IllegalArgumentException("The control points must all "
                            + "have strictly increasing X values.");
                }
                d[i] = (y[i + 1] - y[i]) / h;
            }

            // Initialize the tangents as the average of the secants.
            m[0] = d[0];
            for (int i = 1; i < n - 1; i++) {
                m[i] = (d[i - 1] + d[i]) * 0.5f;
            }
            m[n - 1] = d[n - 2];

            // Update the tangents to preserve monotonicity.
            for (int i = 0; i < n - 1; i++) {
                if (d[i] == 0f) { // successive Y values are equal
                    m[i] = 0f;
                    m[i + 1] = 0f;
                } else {
                    float a = m[i] / d[i];
                    float b = m[i + 1] / d[i];
                    if (a < 0f || b < 0f) {
                        throw new IllegalArgumentException("The control points must have "
                                + "monotonic Y values.");
                    }
                    float h = (float) Math.hypot(a, b);
                    if (h > 3f) {
                        float t = 3f / h;
                        m[i] *= t;
                        m[i + 1] *= t;
                    }
                }
            }

            mX = x;
            mY = y;
            mM = m;
        }

        @Override
        public float interpolate(float x) {
            // Handle the boundary cases.
            final int n = mX.length;
            if (Float.isNaN(x)) {
                return x;
            }
            if (x <= mX[0]) {
                return mY[0];
            }
            if (x >= mX[n - 1]) {
                return mY[n - 1];
            }

            // Find the index 'i' of the last point with smaller X.
            // We know this will be within the spline due to the boundary tests.
            int i = 0;
            while (x >= mX[i + 1]) {
                i += 1;
                if (x == mX[i]) {
                    return mY[i];
                }
            }

            // Perform cubic Hermite spline interpolation.
            float h = mX[i + 1] - mX[i];
            float t = (x - mX[i]) / h;
            return (mY[i] * (1 + 2 * t) + h * mM[i] * t) * (1 - t) * (1 - t)
                    + (mY[i + 1] * (3 - 2 * t) + h * mM[i + 1] * (t - 1)) * t * t;
        }

        // For debugging.
        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            final int n = mX.length;
            str.append("MonotoneCubicSpline{[");
            for (int i = 0; i < n; i++) {
                if (i != 0) {
                    str.append(", ");
                }
                str.append("(").append(mX[i]);
                str.append(", ").append(mY[i]);
                str.append(": ").append(mM[i]).append(")");
            }
            str.append("]}");
            return str.toString();
        }
    }

    public static class LinearSpline extends Spline {
        private final float[] mX;
        private final float[] mY;
        private final float[] mM;

        public LinearSpline(float[] x, float[] y) {
            if (x == null || y == null || x.length != y.length || x.length < 2) {
                throw new IllegalArgumentException("There must be at least two control "
                        + "points and the arrays must be of equal length.");
            }
            final int N = x.length;
            mM = new float[N-1];
            for (int i = 0; i < N-1; i++) {
                mM[i] = (y[i+1] - y[i]) / (x[i+1] - x[i]);
            }
            mX = x;
            mY = y;
        }

        @Override
        public float interpolate(float x) {
            // Handle the boundary cases.
            final int n = mX.length;
            if (Float.isNaN(x)) {
                return x;
            }
            if (x <= mX[0]) {
                return mY[0];
            }
            if (x >= mX[n - 1]) {
                return mY[n - 1];
            }

            // Find the index 'i' of the last point with smaller X.
            // We know this will be within the spline due to the boundary tests.
            int i = 0;
            while (x >= mX[i + 1]) {
                i += 1;
                if (x == mX[i]) {
                    return mY[i];
                }
            }
            return mY[i] + mM[i] * (x - mX[i]);
        }

        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            final int n = mX.length;
            str.append("LinearSpline{[");
            for (int i = 0; i < n; i++) {
                if (i != 0) {
                    str.append(", ");
                }
                str.append("(").append(mX[i]);
                str.append(", ").append(mY[i]);
                if (i < n-1) {
                    str.append(": ").append(mM[i]);
                }
                str.append(")");
            }
            str.append("]}");
            return str.toString();
        }
    }
}