/*
* 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
/**
* 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.
Params: - x – The X value.
Returns: The interpolated Y = f(X) value.
/**
* 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.
/**
* 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
Params: - x – The X component of the control points, strictly increasing.
- y – The Y component of the control points, monotonic.
Throws: - IllegalArgumentException – if the X or Y arrays are null, have
different lengths or have fewer than 2 values.
- IllegalArgumentException – if the control points are not monotonic.
Returns:
/**
* 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.
Params: - x – The X component of the control points, strictly increasing.
- y – The Y component of the control points.
Throws: - IllegalArgumentException – if the X or Y arrays are null, have
different lengths or have fewer than 2 values.
- IllegalArgumentException – if the X components of the control points are not strictly
increasing.
Returns:
/**
* 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();
}
}
}