1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
/*
* 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 final class Spline {
private final float[] mX;
private final float[] mY;
private final float[] mM;
private Spline(float[] x, float[] y, float[] m) {
mX = x;
mY = y;
mM = m;
}
/**
* 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) {
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 = FloatMath.hypot(a, b);
if (h > 9f) {
float t = 3f / h;
m[i] = t * a * d[i];
m[i + 1] = t * b * d[i];
}
}
}
return new Spline(x, y, m);
}
/**
* 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 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("[");
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();
}
}
|
