001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: *
017: */
018:
019: package org.apache.jmeter.visualizers;
020:
021: import org.apache.jorphan.logging.LoggingManager;
022: import org.apache.log.Logger;
023:
024: /*
025: * TODO : - implement ImageProducer interface - suggestions ;-)
026: */
027:
028: /**
029: * This class implements the representation of an interpolated Spline curve.
030: * <P>
031: * The curve described by such an object interpolates an arbitrary number of
032: * fixed points called <I>nodes</I>. The distance between two nodes should
033: * currently be constant. This is about to change in a later version but it can
034: * last a while as it's not really needed. Nevertheless, if you need the
035: * feature, just <a href="mailto:norguet@bigfoot.com?subject=Spline3eq">write me
036: * a note</a> and I'll write it asap.
037: * <P>
038: * The interpolated Spline curve can't be described by an polynomial analytic
039: * equation, the degree of which would be as high as the number of nodes, which
040: * would cause extreme oscillations of the curve on the edges.
041: * <P>
042: * The solution is to split the curve accross a lot of little <I>intervals</I> :
043: * an interval starts at one node and ends at the next one. Then, the
044: * interpolation is done on each interval, according to the following conditions :
045: * <OL>
046: * <LI>the interpolated curve is degree 3 : it's a cubic curve ;
047: * <LI>the interpolated curve contains the two points delimiting the interval.
048: * This condition obviously implies the curve is continuous ;
049: * <LI>the interpolated curve has a smooth slope : the curvature has to be the
050: * same on the left and the right sides of each node ;
051: * <LI>the curvature of the global curve is 0 at both edges.
052: * </OL>
053: * Every part of the global curve is represented by a cubic (degree-3)
054: * polynomial, the coefficients of which have to be computed in order to meet
055: * the above conditions.
056: * <P>
057: * This leads to a n-unknow n-equation system to resolve. One can resolve an
058: * equation system by several manners ; this class uses the Jacobi iterative
059: * method, particularly well adapted to this situation, as the diagonal of the
060: * system matrix is strong compared to the other elements. This implies the
061: * algorithm always converges ! This is not the case of the Gauss-Seidel
062: * algorithm, which is quite faster (it uses intermediate results of each
063: * iteration to speed up the convergence) but it doesn't converge in all the
064: * cases or it converges to a wrong value. This is not acceptable and that's why
065: * the Jacobi method is safer. Anyway, the gain of speed is about a factor of 3
066: * but, for a 100x100 system, it means 10 ms instead of 30 ms, which is a pretty
067: * good reason not to explore the question any further :)
068: * <P>
069: * Here is a little piece of code showing how to use this class :
070: *
071: * <PRE> // ... float[] nodes = {3F, 2F, 4F, 1F, 2.5F, 5F, 3F}; Spline3 curve =
072: * new Spline3(nodes); // ... public void paint(Graphics g) { int[] plot =
073: * curve.getPlots(); for (int i = 1; i < n; i++) { g.drawLine(i - 1, plot[i -
074: * 1], i, plot[i]); } } // ...
075: *
076: * </PRE>
077: *
078: * Have fun with it !<BR>
079: * Any comments, feedback, bug reports or suggestions will be <a
080: * href="mailto:norguet@bigfoot.com?subject=Spline3">appreciated</a>.
081: *
082: * @author <a href="norguet@bigfoot.com">Jean-Pierre Norguet</a>
083: * @version $Revison$ updated $Date: 2007-01-07 17:09:09 +0000 (Sun, 07 Jan 2007) $
084: */
085: public class Spline3 {
086: private static final Logger log = LoggingManager
087: .getLoggerForClass();
088:
089: protected float[][] _coefficients;
090:
091: protected float[][] _A;
092:
093: protected float[] _B;
094:
095: protected float[] _r;
096:
097: protected float[] _rS;
098:
099: protected int _m; // number of nodes
100:
101: protected int _n; // number of non extreme nodes (_m-2)
102:
103: final static protected float DEFAULT_PRECISION = (float) 1E-1;
104:
105: final static protected int DEFAULT_MAX_ITERATIONS = 100;
106:
107: protected float _minPrecision = DEFAULT_PRECISION;
108:
109: protected int _maxIterations = DEFAULT_MAX_ITERATIONS;
110:
111: /**
112: * Creates a new Spline curve by calculating the coefficients of each part
113: * of the curve, i.e. by resolving the equation system implied by the
114: * interpolation condition on every interval.
115: *
116: * @param r
117: * an array of float containing the vertical coordinates of the
118: * nodes to interpolate ; the vertical coordinates start at 0 and
119: * are equidistant with a step of 1.
120: */
121: public Spline3(float[] r) {
122: int n = r.length;
123:
124: // the number of nodes is defined by the length of r
125: this ._m = n;
126: // grab the nodes
127: this ._r = new float[n];
128: for (int i = 0; i < n; i++) {
129: _r[i] = r[i];
130: }
131: // the number of non extreme nodes is the number of intervals
132: // minus 1, i.e. the length of r minus 2
133: this ._n = n - 2;
134: // computes interpolation coefficients
135: try {
136: long startTime = System.currentTimeMillis();
137:
138: this .interpolation();
139: if (log.isDebugEnabled()) {
140: long endTime = System.currentTimeMillis();
141: long elapsedTime = endTime - startTime;
142:
143: log.debug("New Spline curve interpolated in ");
144: log.debug(elapsedTime + " ms");
145: }
146: } catch (Exception e) {
147: log.error("Error when interpolating : ", e);
148: }
149:
150: }
151:
152: /**
153: * Computes the coefficients of the Spline interpolated curve, on each
154: * interval. The matrix system to resolve is <CODE>AX=B</CODE>
155: */
156: protected void interpolation() {
157: // creation of the interpolation structure
158: _rS = new float[_m];
159: _B = new float[_n];
160: _A = new float[_n][_n];
161: _coefficients = new float[_n + 1][4];
162: // local variables
163: int i = 0, j = 0;
164:
165: // initialize system structures (just to be safe)
166: for (i = 0; i < _n; i++) {
167: _B[i] = 0;
168: for (j = 0; j < _n; j++) {
169: _A[i][j] = 0;
170: }
171: for (j = 0; j < 4; j++) {
172: _coefficients[i][j] = 0;
173: }
174: }
175: for (i = 0; i < _n; i++) {
176: _rS[i] = 0;
177: }
178: // initialize the diagonal of the system matrix (A) to 4
179: for (i = 0; i < _n; i++) {
180: _A[i][i] = 4;
181: }
182: // initialize the two minor diagonals of A to 1
183: for (i = 1; i < _n; i++) {
184: _A[i][i - 1] = 1;
185: _A[i - 1][i] = 1;
186: }
187: // initialize B
188: for (i = 0; i < _n; i++) {
189: _B[i] = 6 * (_r[i + 2] - 2 * _r[i + 1] + _r[i]);
190: }
191: // Jacobi system resolving
192: this .jacobi(); // results are stored in _rS
193: // computes the coefficients (di, ci, bi, ai) from the results
194: for (i = 0; i < _n + 1; i++) {
195: // di (degree 0)
196: _coefficients[i][0] = _r[i];
197: // ci (degree 1)
198: _coefficients[i][1] = _r[i + 1] - _r[i]
199: - (_rS[i + 1] + 2 * _rS[i]) / 6;
200: // bi (degree 2)
201: _coefficients[i][2] = _rS[i] / 2;
202: // ai (degree 3)
203: _coefficients[i][3] = (_rS[i + 1] - _rS[i]) / 6;
204: }
205: }
206:
207: /**
208: * Resolves the equation system by a Jacobi algorithm. The use of the slower
209: * Jacobi algorithm instead of Gauss-Seidel is choosen here because Jacobi
210: * is assured of to be convergent for this particular equation system, as
211: * the system matrix has a strong diagonal.
212: */
213: protected void jacobi() {
214: // local variables
215: int i = 0, j = 0, iterations = 0;
216: // intermediate arrays
217: float[] newX = new float[_n];
218: float[] oldX = new float[_n];
219:
220: // Jacobi convergence test
221: if (!converge()) {
222: if (log.isDebugEnabled()) {
223: log
224: .debug("Warning : equation system resolving is unstable");
225: }
226: }
227: // init newX and oldX arrays to 0
228: for (i = 0; i < _n; i++) {
229: newX[i] = 0;
230: oldX[i] = 0;
231: }
232: // main iteration
233: while ((this .precision(oldX, newX) > this ._minPrecision)
234: && (iterations < this ._maxIterations)) {
235: for (i = 0; i < _n; i++) {
236: oldX[i] = newX[i];
237: }
238: for (i = 0; i < _n; i++) {
239: newX[i] = _B[i];
240: for (j = 0; j < i; j++) {
241: newX[i] = newX[i] - (_A[i][j] * oldX[j]);
242: }
243: for (j = i + 1; j < _n; j++) {
244: newX[i] = newX[i] - (_A[i][j] * oldX[j]);
245: }
246: newX[i] = newX[i] / _A[i][i];
247: }
248: iterations++;
249: }
250: if (this .precision(oldX, newX) < this ._minPrecision) {
251: if (log.isDebugEnabled()) {
252: log.debug("Minimal precision (");
253: log.debug(this ._minPrecision + ") reached after ");
254: log.debug(iterations + " iterations");
255: }
256: } else if (iterations > this ._maxIterations) {
257: if (log.isDebugEnabled()) {
258: log.debug("Maximal number of iterations (");
259: log.debug(this ._maxIterations + ") reached");
260: log.debug("Warning : precision is only ");
261: log.debug("" + this .precision(oldX, newX));
262: log.debug(", divergence is possible");
263: }
264: }
265: for (i = 0; i < _n; i++) {
266: _rS[i + 1] = newX[i];
267: }
268: }
269:
270: /**
271: * Test if the Jacobi resolution of the equation system converges. It's OK
272: * if A has a strong diagonal.
273: */
274: protected boolean converge() {
275: boolean converge = true;
276: int i = 0, j = 0;
277: float lineSum = 0F;
278:
279: for (i = 0; i < _n; i++) {
280: if (converge) {
281: lineSum = 0;
282: for (j = 0; j < _n; j++) {
283: lineSum = lineSum + Math.abs(_A[i][j]);
284: }
285: lineSum = lineSum - Math.abs(_A[i][i]);
286: if (lineSum > Math.abs(_A[i][i])) {
287: converge = false;
288: }
289: }
290: }
291: return converge;
292: }
293:
294: /**
295: * Computes the current precision reached.
296: */
297: protected float precision(float[] oldX, float[] newX) {
298: float N = 0F, D = 0F, erreur = 0F;
299: int i = 0;
300:
301: for (i = 0; i < _n; i++) {
302: N = N + Math.abs(newX[i] - oldX[i]);
303: D = D + Math.abs(newX[i]);
304: }
305: if (D != 0F) {
306: erreur = N / D;
307: } else {
308: erreur = Float.MAX_VALUE;
309: }
310: return erreur;
311: }
312:
313: /**
314: * Computes a (vertical) Y-axis value of the global curve.
315: *
316: * @param t
317: * abscissa
318: * @return computed ordinate
319: */
320: public float value(float t) {
321: int i = 0, splineNumber = 0;
322: float abscissa = 0F, result = 0F;
323:
324: // verify t belongs to the curve (range [0, _m-1])
325: if ((t < 0) || (t > (_m - 1))) {
326: if (log.isDebugEnabled()) {
327: log.debug("Warning : abscissa " + t
328: + " out of bounds [0, " + (_m - 1) + "]");
329: }
330: // silent error, consider the curve is constant outside its range
331: if (t < 0) {
332: t = 0;
333: } else {
334: t = _m - 1;
335: }
336: }
337: // seek the good interval for t and get the piece of curve on it
338: splineNumber = (int) Math.floor(t);
339: if (t == (_m - 1)) {
340: // the upper limit of the curve range belongs by definition
341: // to the last interval
342: splineNumber--;
343: }
344: // computes the value of the curve at the pecified abscissa
345: // and relative to the beginning of the right piece of Spline curve
346: abscissa = t - splineNumber;
347: // the polynomial calculation is done by the (fast) Euler method
348: for (i = 0; i < 4; i++) {
349: result = result * abscissa;
350: result = result + _coefficients[splineNumber][3 - i];
351: }
352: return result;
353: }
354:
355: /**
356: * Manual check of the curve at the interpolated points.
357: */
358: public void debugCheck() {
359: int i = 0;
360:
361: for (i = 0; i < _m; i++) {
362: log.info("Point " + i + " : ");
363: log.info(_r[i] + " =? " + value(i));
364: }
365: }
366:
367: /**
368: * Computes drawable plots from the curve for a given draw space. The values
369: * returned are drawable vertically and from the <B>bottom</B> of a Panel.
370: *
371: * @param width
372: * width within the plots have to be computed
373: * @param height
374: * height within the plots are expected to be drawed
375: * @return drawable plots within the limits defined, in an array of int (as
376: * many int as the value of the <CODE>width</CODE> parameter)
377: */
378: public int[] getPlots(int width, int height) {
379: int[] plot = new int[width];
380: // computes auto-scaling and absolute plots
381: float[] y = new float[width];
382: float max = java.lang.Integer.MIN_VALUE;
383: float min = java.lang.Integer.MAX_VALUE;
384:
385: for (int i = 0; i < width; i++) {
386: y[i] = value(((float) i) * (_m - 1) / width);
387: if (y[i] < min) {
388: min = y[i];
389: }
390:
391: if (y[i] > max) {
392: max = y[i];
393: }
394: }
395: if (min < 0) {
396: min = 0; // shouldn't draw negative values
397: }
398: // computes relative auto-scaled plots to fit in the specified area
399: for (int i = 0; i < width; i++) {
400: plot[i] = Math.round(((y[i] - min) * (height - 1))
401: / (max - min));
402: }
403: return plot;
404: }
405:
406: public void setPrecision(float precision) {
407: this ._minPrecision = precision;
408: }
409:
410: public float getPrecision() {
411: return this ._minPrecision;
412: }
413:
414: public void setToDefaultPrecision() {
415: this ._minPrecision = DEFAULT_PRECISION;
416: }
417:
418: public float getDefaultPrecision() {
419: return DEFAULT_PRECISION;
420: }
421:
422: public void setMaxIterations(int iterations) {
423: this ._maxIterations = iterations;
424: }
425:
426: public int getMaxIterations() {
427: return this ._maxIterations;
428: }
429:
430: public void setToDefaultMaxIterations() {
431: this ._maxIterations = DEFAULT_MAX_ITERATIONS;
432: }
433:
434: public int getDefaultMaxIterations() {
435: return DEFAULT_MAX_ITERATIONS;
436: }
437:
438: }
|