KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > jmeter > visualizers > Spline3


1 // $Header: /home/cvs/jakarta-jmeter/src/components/org/apache/jmeter/visualizers/Spline3.java,v 1.8 2004/02/13 01:48:46 sebb Exp $
2 /*
3  * Copyright 2001-2004 The Apache Software Foundation.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17 */
18
19 package org.apache.jmeter.visualizers;
20
21 import org.apache.jorphan.logging.LoggingManager;
22 import org.apache.log.Logger;
23
24
25 /*
26  * TODO :
27  * - implement ImageProducer interface
28  * - suggestions ;-)
29  */
30
31 /**
32  * This class implements the representation of an interpolated Spline curve.
33  * <P>
34  * The curve described by such an object interpolates an arbitrary number
35  * of fixed points called <I>nodes</I>. The distance between two nodes
36  * should currently be constant. This is about to change in a later version
37  * but it can last a while as it's not really needed.
38  * Nevertheless, if you need the feature, just
39  * <a HREF="mailto:norguet@bigfoot.com?subject=Spline3eq">write me a note</a>
40  * and I'll write it asap.
41  * <P>
42  * The interpolated Spline curve can't be described by an polynomial analytic
43  * equation, the degree of which would be as high as the number of nodes,
44  * which would cause extreme oscillations of the curve on the edges.
45  * <P>
46  * The solution is to split the curve accross a lot of little
47  * <I>intervals</I> : an interval starts at one node
48  * and ends at the next one. Then, the interpolation is done on each
49  * interval, according to the following conditions :
50  * <OL>
51  * <LI>the interpolated curve is degree 3 : it's a cubic curve ;
52  * <LI>the interpolated curve contains the two points delimiting
53  * the interval. This condition obviously implies the curve is continuous ;
54  * <LI>the interpolated curve has a smooth slope : the curvature has
55  * to be the same on the left and the right sides of each node ;
56  * <LI>the curvature of the global curve is 0 at both edges.
57  * </OL>
58  * Every part of the global curve is represented by a cubic (degree-3)
59  * polynomial, the coefficients of which have to be computed in order
60  * to meet the above conditions.
61  * <P>
62  * This leads to a n-unknow n-equation system to resolve.
63  * One can resolve an equation system by several manners ;
64  * this class uses the Jacobi iterative method, particularly well
65  * adapted to this situation, as the diagonal of the system matrix
66  * is strong compared to the other elements. This implies the algorithm
67  * always converges ! This is not the case of the Gauss-Seidel algorithm,
68  * which is quite faster (it uses intermediate results of each iteration
69  * to speed up the convergence) but it doesn't converge in all the cases
70  * or it converges to a wrong value. This is not acceptable and
71  * that's why the Jacobi method is safer. Anyway, the gain of speed
72  * is about a factor of 3 but, for a 100x100 system, it means 10 ms
73  * instead of 30 ms, which is a pretty good reason not to explore the question
74  * any further :)
75  * <P>
76  * Here is a little piece of code showing how to use this class :
77  * <PRE>
78  * // ...
79  * float[] nodes = {3F, 2F, 4F, 1F, 2.5F, 5F, 3F};
80  * Spline3 curve = new Spline3(nodes);
81  * // ...
82  * public void paint(Graphics g) {
83  * int[] plot = curve.getPlots();
84  * for (int i = 1; i < n; i++) {
85  * g.drawLine(i - 1, plot[i - 1], i, plot[i]);
86  * }
87  * }
88  * // ...
89  * </PRE>
90  * Have fun with it !<BR>
91  * Any comments, feedback, bug reports or suggestions will be
92  * <a HREF="mailto:norguet@bigfoot.com?subject=Spline3">appreciated</a>.
93  *
94  * @author <a HREF="norguet@bigfoot.com">Jean-Pierre Norguet</a>
95  * @version $Revison$ updated $Date: 2004/02/13 01:48:46 $
96  */
97 public class Spline3
98 {
99     transient private static Logger log = LoggingManager.getLoggerForClass();
100
101     protected float[][] _coefficients;
102     protected float[][] _A;
103     protected float[] _B;
104     protected float[] _r;
105     protected float[] _rS;
106     protected int _m; // number of nodes
107 protected int _n; // number of non extreme nodes (_m-2)
108 final static protected float DEFAULT_PRECISION = (float) 1E-1;
109     final static protected int DEFAULT_MAX_ITERATIONS = 100;
110     protected float _minPrecision = DEFAULT_PRECISION;
111     protected int _maxIterations = DEFAULT_MAX_ITERATIONS;
112
113     /**
114      * Creates a new Spline curve by calculating the coefficients of
115      * each part of the curve, i.e. by resolving the equation system
116      * implied by the interpolation condition on every interval.
117      * @param r an array of float containing the vertical coordinates
118      * of the nodes to interpolate ; the vertical coordinates start at 0
119      * and are equidistant with a step of 1.
120      */
121     public Spline3(float[] r)
122     {
123         int n = r.length;
124
125         // the number of nodes is defined by the length of r
126 this._m = n;
127         // grab the nodes
128 this._r = new float[n];
129         for (int i = 0; i < n; i++)
130         {
131             _r[i] = r[i];
132         }
133         // the number of non extreme nodes is the number of intervals
134 // minus 1, i.e. the length of r minus 2
135 this._n = n - 2;
136         // computes interpolation coefficients
137 try
138         {
139             long startTime = System.currentTimeMillis();
140
141             this.interpolation();
142             if (log.isDebugEnabled())
143             {
144                 long endTime = System.currentTimeMillis();
145                 long elapsedTime = endTime - startTime;
146
147                 log.debug("New Spline curve interpolated in ");
148                 log.debug(elapsedTime + " ms");
149             }
150         }
151         catch (Exception JavaDoc e)
152         {
153             log.error("Error when interpolating : ", e);
154         }
155
156     }
157
158     /**
159      * Computes the coefficients of the Spline interpolated curve,
160      * on each interval. The matrix system to resolve is <CODE>AX=B</CODE>
161      */
162     protected void interpolation()
163     {
164         // creation of the interpolation structure
165 _rS = new float[_m];
166         _B = new float[_n];
167         _A = new float[_n][_n];
168         _coefficients = new float[_n + 1][4];
169         // local variables
170 int i = 0, j = 0;
171
172         // initialize system structures (just to be safe)
173 for (i = 0; i < _n; i++)
174         {
175             _B[i] = 0;
176             for (j = 0; j < _n; j++)
177             {
178                 _A[i][j] = 0;
179             }
180             for (j = 0; j < 4; j++)
181             {
182                 _coefficients[i][j] = 0;
183             }
184         }
185         for (i = 0; i < _n; i++)
186         {
187             _rS[i] = 0;
188         }
189         // initialize the diagonal of the system matrix (A) to 4
190 for (i = 0; i < _n; i++)
191         {
192             _A[i][i] = 4;
193         }
194         // initialize the two minor diagonals of A to 1
195 for (i = 1; i < _n; i++)
196         {
197             _A[i][i - 1] = 1;
198             _A[i - 1][i] = 1;
199         }
200         // initialize B
201 for (i = 0; i < _n; i++)
202         {
203             _B[i] = 6 * (_r[i + 2] - 2 * _r[i + 1] + _r[i]);
204         }
205         // Jacobi system resolving
206 this.jacobi(); // results are stored in _rS
207 // computes the coefficients (di, ci, bi, ai) from the results
208 for (i = 0; i < _n + 1; i++)
209         {
210             // di (degree 0)
211 _coefficients[i][0] = _r[i];
212             // ci (degree 1)
213 _coefficients[i][1] = _r[i + 1] - _r[i]
214                     - (_rS[i + 1] + 2 * _rS[i]) / 6;
215             // bi (degree 2)
216 _coefficients[i][2] = _rS[i] / 2;
217             // ai (degree 3)
218 _coefficients[i][3] = (_rS[i + 1] - _rS[i]) / 6;
219         }
220     }
221
222     /**
223      * Resolves the equation system by a Jacobi algorithm.
224      * The use of the slower Jacobi algorithm instead of Gauss-Seidel is
225      * choosen here because Jacobi is assured of to be convergent
226      * for this particular equation system, as the system matrix
227      * has a strong diagonal.
228      */
229     protected void jacobi()
230     {
231         // local variables
232 int i = 0, j = 0, iterations = 0;
233         // intermediate arrays
234 float[] newX = new float[_n];
235         float[] oldX = new float[_n];
236
237         // Jacobi convergence test
238 if (!converge())
239         {
240             if (log.isDebugEnabled())
241             {
242                 log.debug(
243                     "Warning : equation system resolving is unstable");
244             }
245         }
246         // init newX and oldX arrays to 0
247 for (i = 0; i < _n; i++)
248         {
249             newX[i] = 0;
250             oldX[i] = 0;
251         }
252         // main iteration
253 while ((this.precision(oldX, newX) > this._minPrecision)
254                 && (iterations < this._maxIterations))
255         {
256             for (i = 0; i < _n; i++)
257             {
258                 oldX[i] = newX[i];
259             }
260             for (i = 0; i < _n; i++)
261             {
262                 newX[i] = _B[i];
263                 for (j = 0; j < i; j++)
264                 {
265                     newX[i] = newX[i] - (_A[i][j] * oldX[j]);
266                 }
267                 for (j = i + 1; j < _n; j++)
268                 {
269                     newX[i] = newX[i] - (_A[i][j] * oldX[j]);
270                 }
271                 newX[i] = newX[i] / _A[i][i];
272             }
273             iterations++;
274         }
275         if (this.precision(oldX, newX) < this._minPrecision)
276         {
277             if (log.isDebugEnabled())
278             {
279                 log.debug("Minimal precision (");
280                 log.debug(this._minPrecision + ") reached after ");
281                 log.debug(iterations + " iterations");
282             }
283         }
284         else if (iterations > this._maxIterations)
285         {
286             if (log.isDebugEnabled())
287             {
288                 log.debug("Maximal number of iterations (");
289                 log.debug(this._maxIterations + ") reached");
290                 log.debug("Warning : precision is only ");
291                 log.debug("" + this.precision(oldX, newX));
292                 log.debug(", divergence is possible");
293             }
294         }
295         for (i = 0; i < _n; i++)
296         {
297             _rS[i + 1] = newX[i];
298         }
299     }
300
301     /**
302      * Test if the Jacobi resolution of the equation system converges.
303      * It's OK if A has a strong diagonal.
304      */
305     protected boolean converge()
306     {
307         boolean converge = true;
308         int i = 0, j = 0;
309         float lineSum = 0F;
310
311         for (i = 0; i < _n; i++)
312         {
313             if (converge)
314             {
315                 lineSum = 0;
316                 for (j = 0; j < _n; j++)
317                 {
318                     lineSum = lineSum + Math.abs(_A[i][j]);
319                 }
320                 lineSum = lineSum - Math.abs(_A[i][i]);
321                 if (lineSum > Math.abs(_A[i][i]))
322                 {
323                     converge = false;
324                 }
325             }
326         }
327         return converge;
328     }
329
330     /**
331      * Computes the current precision reached.
332      */
333     protected float precision(float[] oldX, float[] newX)
334     {
335         float N = 0F, D = 0F, erreur = 0F;
336         int i = 0;
337
338         for (i = 0; i < _n; i++)
339         {
340             N = N + Math.abs(newX[i] - oldX[i]);
341             D = D + Math.abs(newX[i]);
342         }
343         if (D != 0F)
344         {
345             erreur = N / D;
346         }
347         else
348         {
349             erreur = Float.MAX_VALUE;
350         }
351         return erreur;
352     }
353
354     /**
355      * Computes a (vertical) Y-axis value of the global curve.
356      * @param t abscissa
357      * @return computed ordinate
358      */
359     public float value(float t)
360     {
361         int i = 0, splineNumber = 0;
362         float abscissa = 0F, result = 0F;
363
364         // verify t belongs to the curve (range [0, _m-1])
365 if ((t < 0) || (t > (_m - 1)))
366         {
367             if (log.isDebugEnabled())
368             {
369                 log.debug(
370                     "Warning : abscissa "
371                         + t
372                         + " out of bounds [0, "
373                         + (_m - 1)
374                         + "]");
375             }
376             // silent error, consider the curve is constant outside its range
377 if (t < 0)
378             {
379                 t = 0;
380             }
381             else
382             {
383                 t = _m - 1;
384             }
385         }
386         // seek the good interval for t and get the piece of curve on it
387 splineNumber = (int) Math.floor(t);
388         if (t == (_m - 1))
389         {
390             // the upper limit of the curve range belongs by definition
391 // to the last interval
392 splineNumber--;
393         }
394         // computes the value of the curve at the pecified abscissa
395 // and relative to the beginning of the right piece of Spline curve
396 abscissa = t - splineNumber;
397         // the polynomial calculation is done by the (fast) Euler method
398 for (i = 0; i < 4; i++)
399         {
400             result = result * abscissa;
401             result = result + _coefficients[splineNumber][3 - i];
402         }
403         return result;
404     }
405
406     /**
407      * Manual check of the curve at the interpolated points.
408      */
409     public void debugCheck()
410     {
411         int i = 0;
412
413         for (i = 0; i < _m; i++)
414         {
415             log.info("Point " + i + " : ");
416             log.info(_r[i] + " =? " + value(i));
417         }
418     }
419
420     /**
421      * Computes drawable plots from the curve for a given draw space.
422      * The values returned are drawable vertically and from the
423      * <B>bottom</B> of a Panel.
424      * @param width width within the plots have to be computed
425      * @param height height within the plots are expected to be drawed
426      * @return drawable plots within the limits defined, in an array of
427      * int (as many int as the value of the <CODE>width</CODE> parameter)
428      */
429     public int[] getPlots(int width, int height)
430     {
431         int[] plot = new int[width];
432         // computes auto-scaling and absolute plots
433 float[] y = new float[width];
434         float max = java.lang.Integer.MIN_VALUE;
435         float min = java.lang.Integer.MAX_VALUE;
436
437         for (int i = 0; i < width; i++)
438         {
439             y[i] = value(((float) i) * (_m - 1) / width);
440             if (y[i] < min)
441             {
442                 min = y[i];
443             }
444              
445             if (y[i] > max)
446             {
447                 max = y[i];
448             }
449         }
450         if (min < 0)
451         {
452             min = 0; // shouldn't draw negative values
453 }
454         // computes relative auto-scaled plots to fit in the specified area
455 for (int i = 0; i < width; i++)
456         {
457             plot[i] =
458                 (int) Math.round(((y[i] - min) * (height - 1)) / (max - min));
459         }
460         return plot;
461     }
462
463     public void setPrecision(float precision)
464     {
465         this._minPrecision = precision;
466     }
467
468     public float getPrecision()
469     {
470         return this._minPrecision;
471     }
472
473     public void setToDefaultPrecision()
474     {
475         this._minPrecision = DEFAULT_PRECISION;
476     }
477
478     public float getDefaultPrecision()
479     {
480         return DEFAULT_PRECISION;
481     }
482
483     public void setMaxIterations(int iterations)
484     {
485         this._maxIterations = iterations;
486     }
487
488     public int getMaxIterations()
489     {
490         return this._maxIterations;
491     }
492
493     public void setToDefaultMaxIterations()
494     {
495         this._maxIterations = DEFAULT_MAX_ITERATIONS;
496     }
497
498     public int getDefaultMaxIterations()
499     {
500         return DEFAULT_MAX_ITERATIONS;
501     }
502
503 }
504
505
Popular Tags