1 package com.android.gallery3d.filtershow.filters; 2 3 4 public class SplineMath { 5 double[][] mPoints = new double[6][2]; 6 double[] mDerivatives; 7 SplineMath(int n) { 8 mPoints = new double[n][2]; 9 } 10 11 public void setPoint(int index, double x, double y) { 12 mPoints[index][0] = x; 13 mPoints[index][1] = y; 14 mDerivatives = null; 15 } 16 17 public float[][] calculatetCurve(int n) { 18 float[][] curve = new float[n][2]; 19 double[][] points = new double[mPoints.length][2]; 20 for (int i = 0; i < mPoints.length; i++) { 21 22 points[i][0] = mPoints[i][0]; 23 points[i][1] = mPoints[i][1]; 24 25 } 26 double[] derivatives = solveSystem(points); 27 float start = (float) points[0][0]; 28 float end = (float) (points[points.length - 1][0]); 29 30 curve[0][0] = (float) (points[0][0]); 31 curve[0][1] = (float) (points[0][1]); 32 int last = curve.length - 1; 33 curve[last][0] = (float) (points[points.length - 1][0]); 34 curve[last][1] = (float) (points[points.length - 1][1]); 35 36 for (int i = 0; i < curve.length; i++) { 37 38 double[] cur = null; 39 double[] next = null; 40 double x = start + i * (end - start) / (curve.length - 1); 41 int pivot = 0; 42 for (int j = 0; j < points.length - 1; j++) { 43 if (x >= points[j][0] && x <= points[j + 1][0]) { 44 pivot = j; 45 } 46 } 47 cur = points[pivot]; 48 next = points[pivot + 1]; 49 if (x <= next[0]) { 50 double x1 = cur[0]; 51 double x2 = next[0]; 52 double y1 = cur[1]; 53 double y2 = next[1]; 54 55 // Use the second derivatives to apply the cubic spline 56 // equation: 57 double delta = (x2 - x1); 58 double delta2 = delta * delta; 59 double b = (x - x1) / delta; 60 double a = 1 - b; 61 double ta = a * y1; 62 double tb = b * y2; 63 double tc = (a * a * a - a) * derivatives[pivot]; 64 double td = (b * b * b - b) * derivatives[pivot + 1]; 65 double y = ta + tb + (delta2 / 6) * (tc + td); 66 67 curve[i][0] = (float) (x); 68 curve[i][1] = (float) (y); 69 } else { 70 curve[i][0] = (float) (next[0]); 71 curve[i][1] = (float) (next[1]); 72 } 73 } 74 return curve; 75 } 76 77 public double getValue(double x) { 78 double[] cur = null; 79 double[] next = null; 80 if (mDerivatives == null) 81 mDerivatives = solveSystem(mPoints); 82 int pivot = 0; 83 for (int j = 0; j < mPoints.length - 1; j++) { 84 pivot = j; 85 if (x <= mPoints[j][0]) { 86 break; 87 } 88 } 89 cur = mPoints[pivot]; 90 next = mPoints[pivot + 1]; 91 double x1 = cur[0]; 92 double x2 = next[0]; 93 double y1 = cur[1]; 94 double y2 = next[1]; 95 96 // Use the second derivatives to apply the cubic spline 97 // equation: 98 double delta = (x2 - x1); 99 double delta2 = delta * delta; 100 double b = (x - x1) / delta; 101 double a = 1 - b; 102 double ta = a * y1; 103 double tb = b * y2; 104 double tc = (a * a * a - a) * mDerivatives[pivot]; 105 double td = (b * b * b - b) * mDerivatives[pivot + 1]; 106 double y = ta + tb + (delta2 / 6) * (tc + td); 107 108 return y; 109 110 } 111 112 double[] solveSystem(double[][] points) { 113 int n = points.length; 114 double[][] system = new double[n][3]; 115 double[] result = new double[n]; // d 116 double[] solution = new double[n]; // returned coefficients 117 system[0][1] = 1; 118 system[n - 1][1] = 1; 119 double d6 = 1.0 / 6.0; 120 double d3 = 1.0 / 3.0; 121 122 // let's create a tridiagonal matrix representing the 123 // system, and apply the TDMA algorithm to solve it 124 // (see http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm) 125 for (int i = 1; i < n - 1; i++) { 126 double deltaPrevX = points[i][0] - points[i - 1][0]; 127 double deltaX = points[i + 1][0] - points[i - 1][0]; 128 double deltaNextX = points[i + 1][0] - points[i][0]; 129 double deltaNextY = points[i + 1][1] - points[i][1]; 130 double deltaPrevY = points[i][1] - points[i - 1][1]; 131 system[i][0] = d6 * deltaPrevX; // a_i 132 system[i][1] = d3 * deltaX; // b_i 133 system[i][2] = d6 * deltaNextX; // c_i 134 result[i] = (deltaNextY / deltaNextX) - (deltaPrevY / deltaPrevX); // d_i 135 } 136 137 // Forward sweep 138 for (int i = 1; i < n; i++) { 139 // m = a_i/b_i-1 140 double m = system[i][0] / system[i - 1][1]; 141 // b_i = b_i - m(c_i-1) 142 system[i][1] = system[i][1] - m * system[i - 1][2]; 143 // d_i = d_i - m(d_i-1) 144 result[i] = result[i] - m * result[i - 1]; 145 } 146 147 // Back substitution 148 solution[n - 1] = result[n - 1] / system[n - 1][1]; 149 for (int i = n - 2; i >= 0; --i) { 150 solution[i] = (result[i] - system[i][2] * solution[i + 1]) / system[i][1]; 151 } 152 return solution; 153 } 154 155 public static void main(String[] args) { 156 SplineMath s = new SplineMath(10); 157 for (int i = 0; i < 10; i++) { 158 s.setPoint(i, i, i); 159 } 160 float[][] curve = s.calculatetCurve(40); 161 162 for (int j = 0; j < curve.length; j++) { 163 System.out.println(curve[j][0] + "," + curve[j][1]); 164 } 165 } 166 } 167
