001    /* QuadCurve2D.java -- represents a parameterized quadratic curve in 2-D space
002       Copyright (C) 2002, 2003, 2004 Free Software Foundation
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package java.awt.geom;
039    
040    import java.awt.Rectangle;
041    import java.awt.Shape;
042    import java.util.NoSuchElementException;
043    
044    /**
045     * A two-dimensional curve that is parameterized with a quadratic
046     * function.
047     *
048     * <p><img src="doc-files/QuadCurve2D-1.png" width="350" height="180"
049     * alt="A drawing of a QuadCurve2D" />
050     *
051     * @author Eric Blake (ebb9@email.byu.edu)
052     * @author Graydon Hoare (graydon@redhat.com)
053     * @author Sascha Brawer (brawer@dandelis.ch)
054     * @author Sven de Marothy (sven@physto.se)
055     *
056     * @since 1.2
057     */
058    public abstract class QuadCurve2D implements Shape, Cloneable
059    {
060      private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
061      private static final double EPSILON = 1E-10;
062    
063      /**
064       * Constructs a new QuadCurve2D. Typical users will want to
065       * construct instances of a subclass, such as {@link
066       * QuadCurve2D.Float} or {@link QuadCurve2D.Double}.
067       */
068      protected QuadCurve2D()
069      {
070      }
071    
072      /**
073       * Returns the <i>x</i> coordinate of the curve&#x2019;s start
074       * point.
075       */
076      public abstract double getX1();
077    
078      /**
079       * Returns the <i>y</i> coordinate of the curve&#x2019;s start
080       * point.
081       */
082      public abstract double getY1();
083    
084      /**
085       * Returns the curve&#x2019;s start point.
086       */
087      public abstract Point2D getP1();
088    
089      /**
090       * Returns the <i>x</i> coordinate of the curve&#x2019;s control
091       * point.
092       */
093      public abstract double getCtrlX();
094    
095      /**
096       * Returns the <i>y</i> coordinate of the curve&#x2019;s control
097       * point.
098       */
099      public abstract double getCtrlY();
100    
101      /**
102       * Returns the curve&#x2019;s control point.
103       */
104      public abstract Point2D getCtrlPt();
105    
106      /**
107       * Returns the <i>x</i> coordinate of the curve&#x2019;s end
108       * point.
109       */
110      public abstract double getX2();
111    
112      /**
113       * Returns the <i>y</i> coordinate of the curve&#x2019;s end
114       * point.
115       */
116      public abstract double getY2();
117    
118      /**
119       * Returns the curve&#x2019;s end point.
120       */
121      public abstract Point2D getP2();
122    
123      /**
124       * Changes the curve geometry, separately specifying each coordinate
125       * value.
126       *
127       * @param x1 the <i>x</i> coordinate of the curve&#x2019;s new start
128       * point.
129       *
130       * @param y1 the <i>y</i> coordinate of the curve&#x2019;s new start
131       * point.
132       *
133       * @param cx the <i>x</i> coordinate of the curve&#x2019;s new
134       * control point.
135       *
136       * @param cy the <i>y</i> coordinate of the curve&#x2019;s new
137       * control point.
138       *
139       * @param x2 the <i>x</i> coordinate of the curve&#x2019;s new end
140       * point.
141       *
142       * @param y2 the <i>y</i> coordinate of the curve&#x2019;s new end
143       * point.
144       */
145      public abstract void setCurve(double x1, double y1, double cx, double cy,
146                                    double x2, double y2);
147    
148      /**
149       * Changes the curve geometry, passing coordinate values in an
150       * array.
151       *
152       * @param coords an array containing the new coordinate values.  The
153       * <i>x</i> coordinate of the new start point is located at
154       * <code>coords[offset]</code>, its <i>y</i> coordinate at
155       * <code>coords[offset + 1]</code>.  The <i>x</i> coordinate of the
156       * new control point is located at <code>coords[offset + 2]</code>,
157       * its <i>y</i> coordinate at <code>coords[offset + 3]</code>. The
158       * <i>x</i> coordinate of the new end point is located at
159       * <code>coords[offset + 4]</code>, its <i>y</i> coordinate at
160       * <code>coords[offset + 5]</code>.
161       *
162       * @param offset the offset of the first coordinate value in
163       * <code>coords</code>.
164       */
165      public void setCurve(double[] coords, int offset)
166      {
167        setCurve(coords[offset++], coords[offset++], coords[offset++],
168                 coords[offset++], coords[offset++], coords[offset++]);
169      }
170    
171      /**
172       * Changes the curve geometry, specifying coordinate values in
173       * separate Point objects.
174       *
175       * <p><img src="doc-files/QuadCurve2D-1.png" width="350" height="180"
176       * alt="A drawing of a QuadCurve2D" />
177       *
178       * <p>The curve does not keep any reference to the passed point
179       * objects. Therefore, a later change to <code>p1</code>,
180       * <code>c</code> <code>p2</code> will not affect the curve
181       * geometry.
182       *
183       * @param p1 the new start point.
184       * @param c the new control point.
185       * @param p2 the new end point.
186       */
187      public void setCurve(Point2D p1, Point2D c, Point2D p2)
188      {
189        setCurve(p1.getX(), p1.getY(), c.getX(), c.getY(), p2.getX(), p2.getY());
190      }
191    
192      /**
193       * Changes the curve geometry, specifying coordinate values in an
194       * array of Point objects.
195       *
196       * <p><img src="doc-files/QuadCurve2D-1.png" width="350" height="180"
197       * alt="A drawing of a QuadCurve2D" />
198       *
199       * <p>The curve does not keep references to the passed point
200       * objects. Therefore, a later change to the <code>pts</code> array
201       * or any of its elements will not affect the curve geometry.
202       *
203       * @param pts an array containing the points. The new start point
204       * is located at <code>pts[offset]</code>, the new control
205       * point at <code>pts[offset + 1]</code>, and the new end point
206       * at <code>pts[offset + 2]</code>.
207       *
208       * @param offset the offset of the start point in <code>pts</code>.
209       */
210      public void setCurve(Point2D[] pts, int offset)
211      {
212        setCurve(pts[offset].getX(), pts[offset].getY(), pts[offset + 1].getX(),
213                 pts[offset + 1].getY(), pts[offset + 2].getX(),
214                 pts[offset + 2].getY());
215      }
216    
217      /**
218       * Changes the geometry of the curve to that of another curve.
219       *
220       * @param c the curve whose coordinates will be copied.
221       */
222      public void setCurve(QuadCurve2D c)
223      {
224        setCurve(c.getX1(), c.getY1(), c.getCtrlX(), c.getCtrlY(), c.getX2(),
225                 c.getY2());
226      }
227    
228      /**
229       * Calculates the squared flatness of a quadratic curve, directly
230       * specifying each coordinate value. The flatness is the distance of
231       * the control point to the line between start and end point.
232       *
233       * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180"
234       * alt="A drawing that illustrates the flatness" />
235       *
236       * <p>In the above drawing, the straight line connecting start point
237       * P1 and end point P2 is depicted in gray.  The result will be the
238       * the square of the distance between C and the gray line, i.e.
239       * the squared length of the red line.
240       *
241       * @param x1 the <i>x</i> coordinate of the start point P1.
242       * @param y1 the <i>y</i> coordinate of the start point P1.
243       * @param cx the <i>x</i> coordinate of the control point C.
244       * @param cy the <i>y</i> coordinate of the control point C.
245       * @param x2 the <i>x</i> coordinate of the end point P2.
246       * @param y2 the <i>y</i> coordinate of the end point P2.
247       */
248      public static double getFlatnessSq(double x1, double y1, double cx,
249                                         double cy, double x2, double y2)
250      {
251        return Line2D.ptSegDistSq(x1, y1, x2, y2, cx, cy);
252      }
253    
254      /**
255       * Calculates the flatness of a quadratic curve, directly specifying
256       * each coordinate value. The flatness is the distance of the
257       * control point to the line between start and end point.
258       *
259       * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180"
260       * alt="A drawing that illustrates the flatness" />
261       *
262       * <p>In the above drawing, the straight line connecting start point
263       * P1 and end point P2 is depicted in gray.  The result will be the
264       * the distance between C and the gray line, i.e. the length of
265       * the red line.
266       *
267       * @param x1 the <i>x</i> coordinate of the start point P1.
268       * @param y1 the <i>y</i> coordinate of the start point P1.
269       * @param cx the <i>x</i> coordinate of the control point C.
270       * @param cy the <i>y</i> coordinate of the control point C.
271       * @param x2 the <i>x</i> coordinate of the end point P2.
272       * @param y2 the <i>y</i> coordinate of the end point P2.
273       */
274      public static double getFlatness(double x1, double y1, double cx, double cy,
275                                       double x2, double y2)
276      {
277        return Line2D.ptSegDist(x1, y1, x2, y2, cx, cy);
278      }
279    
280      /**
281       * Calculates the squared flatness of a quadratic curve, specifying
282       * the coordinate values in an array. The flatness is the distance
283       * of the control point to the line between start and end point.
284       *
285       * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180"
286       * alt="A drawing that illustrates the flatness" />
287       *
288       * <p>In the above drawing, the straight line connecting start point
289       * P1 and end point P2 is depicted in gray.  The result will be the
290       * the square of the distance between C and the gray line, i.e.
291       * the squared length of the red line.
292       *
293       * @param coords an array containing the coordinate values.  The
294       * <i>x</i> coordinate of the start point P1 is located at
295       * <code>coords[offset]</code>, its <i>y</i> coordinate at
296       * <code>coords[offset + 1]</code>.  The <i>x</i> coordinate of the
297       * control point C is located at <code>coords[offset + 2]</code>,
298       * its <i>y</i> coordinate at <code>coords[offset + 3]</code>. The
299       * <i>x</i> coordinate of the end point P2 is located at
300       * <code>coords[offset + 4]</code>, its <i>y</i> coordinate at
301       * <code>coords[offset + 5]</code>.
302       *
303       * @param offset the offset of the first coordinate value in
304       * <code>coords</code>.
305       */
306      public static double getFlatnessSq(double[] coords, int offset)
307      {
308        return Line2D.ptSegDistSq(coords[offset], coords[offset + 1],
309                                  coords[offset + 4], coords[offset + 5],
310                                  coords[offset + 2], coords[offset + 3]);
311      }
312    
313      /**
314       * Calculates the flatness of a quadratic curve, specifying the
315       * coordinate values in an array. The flatness is the distance of
316       * the control point to the line between start and end point.
317       *
318       * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180"
319       * alt="A drawing that illustrates the flatness" />
320       *
321       * <p>In the above drawing, the straight line connecting start point
322       * P1 and end point P2 is depicted in gray.  The result will be the
323       * the the distance between C and the gray line, i.e.  the length of
324       * the red line.
325       *
326       * @param coords an array containing the coordinate values.  The
327       * <i>x</i> coordinate of the start point P1 is located at
328       * <code>coords[offset]</code>, its <i>y</i> coordinate at
329       * <code>coords[offset + 1]</code>.  The <i>x</i> coordinate of the
330       * control point C is located at <code>coords[offset + 2]</code>,
331       * its <i>y</i> coordinate at <code>coords[offset + 3]</code>. The
332       * <i>x</i> coordinate of the end point P2 is located at
333       * <code>coords[offset + 4]</code>, its <i>y</i> coordinate at
334       * <code>coords[offset + 5]</code>.
335       *
336       * @param offset the offset of the first coordinate value in
337       * <code>coords</code>.
338       */
339      public static double getFlatness(double[] coords, int offset)
340      {
341        return Line2D.ptSegDist(coords[offset], coords[offset + 1],
342                                coords[offset + 4], coords[offset + 5],
343                                coords[offset + 2], coords[offset + 3]);
344      }
345    
346      /**
347       * Calculates the squared flatness of this curve. The flatness is
348       * the distance of the control point to the line between start and
349       * end point.
350       *
351       * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180"
352       * alt="A drawing that illustrates the flatness" />
353       *
354       * <p>In the above drawing, the straight line connecting start point
355       * P1 and end point P2 is depicted in gray.  The result will be the
356       * the square of the distance between C and the gray line, i.e. the
357       * squared length of the red line.
358       */
359      public double getFlatnessSq()
360      {
361        return Line2D.ptSegDistSq(getX1(), getY1(), getX2(), getY2(), getCtrlX(),
362                                  getCtrlY());
363      }
364    
365      /**
366       * Calculates the flatness of this curve. The flatness is the
367       * distance of the control point to the line between start and end
368       * point.
369       *
370       * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180"
371       * alt="A drawing that illustrates the flatness" />
372       *
373       * <p>In the above drawing, the straight line connecting start point
374       * P1 and end point P2 is depicted in gray.  The result will be the
375       * the distance between C and the gray line, i.e.  the length of the
376       * red line.
377       */
378      public double getFlatness()
379      {
380        return Line2D.ptSegDist(getX1(), getY1(), getX2(), getY2(), getCtrlX(),
381                                getCtrlY());
382      }
383    
384      /**
385       * Subdivides this curve into two halves.
386       *
387       * <p><img src="doc-files/QuadCurve2D-3.png" width="700"
388       * height="180" alt="A drawing that illustrates the effects of
389       * subdividing a QuadCurve2D" />
390       *
391       * @param left a curve whose geometry will be set to the left half
392       * of this curve, or <code>null</code> if the caller is not
393       * interested in the left half.
394       *
395       * @param right a curve whose geometry will be set to the right half
396       * of this curve, or <code>null</code> if the caller is not
397       * interested in the right half.
398       */
399      public void subdivide(QuadCurve2D left, QuadCurve2D right)
400      {
401        // Use empty slots at end to share single array.
402        double[] d = new double[]
403                     {
404                       getX1(), getY1(), getCtrlX(), getCtrlY(), getX2(), getY2(),
405                       0, 0, 0, 0
406                     };
407        subdivide(d, 0, d, 0, d, 4);
408        if (left != null)
409          left.setCurve(d, 0);
410        if (right != null)
411          right.setCurve(d, 4);
412      }
413    
414      /**
415       * Subdivides a quadratic curve into two halves.
416       *
417       * <p><img src="doc-files/QuadCurve2D-3.png" width="700"
418       * height="180" alt="A drawing that illustrates the effects of
419       * subdividing a QuadCurve2D" />
420       *
421       * @param src the curve to be subdivided.
422       *
423       * @param left a curve whose geometry will be set to the left half
424       * of <code>src</code>, or <code>null</code> if the caller is not
425       * interested in the left half.
426       *
427       * @param right a curve whose geometry will be set to the right half
428       * of <code>src</code>, or <code>null</code> if the caller is not
429       * interested in the right half.
430       */
431      public static void subdivide(QuadCurve2D src, QuadCurve2D left,
432                                   QuadCurve2D right)
433      {
434        src.subdivide(left, right);
435      }
436    
437      /**
438       * Subdivides a quadratic curve into two halves, passing all
439       * coordinates in an array.
440       *
441       * <p><img src="doc-files/QuadCurve2D-3.png" width="700"
442       * height="180" alt="A drawing that illustrates the effects of
443       * subdividing a QuadCurve2D" />
444       *
445       * <p>The left end point and the right start point will always be
446       * identical. Memory-concious programmers thus may want to pass the
447       * same array for both <code>left</code> and <code>right</code>, and
448       * set <code>rightOff</code> to <code>leftOff + 4</code>.
449       *
450       * @param src an array containing the coordinates of the curve to be
451       * subdivided.  The <i>x</i> coordinate of the start point is
452       * located at <code>src[srcOff]</code>, its <i>y</i> at
453       * <code>src[srcOff + 1]</code>.  The <i>x</i> coordinate of the
454       * control point is located at <code>src[srcOff + 2]</code>, its
455       * <i>y</i> at <code>src[srcOff + 3]</code>.  The <i>x</i>
456       * coordinate of the end point is located at <code>src[srcOff +
457       * 4]</code>, its <i>y</i> at <code>src[srcOff + 5]</code>.
458       *
459       * @param srcOff an offset into <code>src</code>, specifying
460       * the index of the start point&#x2019;s <i>x</i> coordinate.
461       *
462       * @param left an array that will receive the coordinates of the
463       * left half of <code>src</code>. It is acceptable to pass
464       * <code>src</code>. A caller who is not interested in the left half
465       * can pass <code>null</code>.
466       *
467       * @param leftOff an offset into <code>left</code>, specifying the
468       * index where the start point&#x2019;s <i>x</i> coordinate will be
469       * stored.
470       *
471       * @param right an array that will receive the coordinates of the
472       * right half of <code>src</code>. It is acceptable to pass
473       * <code>src</code> or <code>left</code>. A caller who is not
474       * interested in the right half can pass <code>null</code>.
475       *
476       * @param rightOff an offset into <code>right</code>, specifying the
477       * index where the start point&#x2019;s <i>x</i> coordinate will be
478       * stored.
479       */
480      public static void subdivide(double[] src, int srcOff, double[] left,
481                                   int leftOff, double[] right, int rightOff)
482      {
483        double x1;
484        double y1;
485        double xc;
486        double yc;
487        double x2;
488        double y2;
489    
490        x1 = src[srcOff];
491        y1 = src[srcOff + 1];
492        xc = src[srcOff + 2];
493        yc = src[srcOff + 3];
494        x2 = src[srcOff + 4];
495        y2 = src[srcOff + 5];
496    
497        if (left != null)
498          {
499            left[leftOff] = x1;
500            left[leftOff + 1] = y1;
501          }
502    
503        if (right != null)
504          {
505            right[rightOff + 4] = x2;
506            right[rightOff + 5] = y2;
507          }
508    
509        x1 = (x1 + xc) / 2;
510        x2 = (xc + x2) / 2;
511        xc = (x1 + x2) / 2;
512        y1 = (y1 + yc) / 2;
513        y2 = (y2 + yc) / 2;
514        yc = (y1 + y2) / 2;
515    
516        if (left != null)
517          {
518            left[leftOff + 2] = x1;
519            left[leftOff + 3] = y1;
520            left[leftOff + 4] = xc;
521            left[leftOff + 5] = yc;
522          }
523    
524        if (right != null)
525          {
526            right[rightOff] = xc;
527            right[rightOff + 1] = yc;
528            right[rightOff + 2] = x2;
529            right[rightOff + 3] = y2;
530          }
531      }
532    
533      /**
534       * Finds the non-complex roots of a quadratic equation, placing the
535       * results into the same array as the equation coefficients. The
536       * following equation is being solved:
537       *
538       * <blockquote><code>eqn[2]</code> &#xb7; <i>x</i><sup>2</sup>
539       * + <code>eqn[1]</code> &#xb7; <i>x</i>
540       * + <code>eqn[0]</code>
541       * = 0
542       * </blockquote>
543       *
544       * <p>For some background about solving quadratic equations, see the
545       * article <a href=
546       * "http://planetmath.org/encyclopedia/QuadraticFormula.html"
547       * >&#x201c;Quadratic Formula&#x201d;</a> in <a href=
548       * "http://planetmath.org/">PlanetMath</a>. For an extensive library
549       * of numerical algorithms written in the C programming language,
550       * see the <a href="http://www.gnu.org/software/gsl/">GNU Scientific
551       * Library</a>.
552       *
553       * @see #solveQuadratic(double[], double[])
554       * @see CubicCurve2D#solveCubic(double[], double[])
555       *
556       * @param eqn an array with the coefficients of the equation. When
557       * this procedure has returned, <code>eqn</code> will contain the
558       * non-complex solutions of the equation, in no particular order.
559       *
560       * @return the number of non-complex solutions. A result of 0
561       * indicates that the equation has no non-complex solutions. A
562       * result of -1 indicates that the equation is constant (i.e.,
563       * always or never zero).
564       *
565       * @author Brian Gough (bjg@network-theory.com)
566       * (original C implementation in the <a href=
567       * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>)
568       *
569       * @author Sascha Brawer (brawer@dandelis.ch)
570       * (adaptation to Java)
571       */
572      public static int solveQuadratic(double[] eqn)
573      {
574        return solveQuadratic(eqn, eqn);
575      }
576    
577      /**
578       * Finds the non-complex roots of a quadratic equation. The
579       * following equation is being solved:
580       *
581       * <blockquote><code>eqn[2]</code> &#xb7; <i>x</i><sup>2</sup>
582       * + <code>eqn[1]</code> &#xb7; <i>x</i>
583       * + <code>eqn[0]</code>
584       * = 0
585       * </blockquote>
586       *
587       * <p>For some background about solving quadratic equations, see the
588       * article <a href=
589       * "http://planetmath.org/encyclopedia/QuadraticFormula.html"
590       * >&#x201c;Quadratic Formula&#x201d;</a> in <a href=
591       * "http://planetmath.org/">PlanetMath</a>. For an extensive library
592       * of numerical algorithms written in the C programming language,
593       * see the <a href="http://www.gnu.org/software/gsl/">GNU Scientific
594       * Library</a>.
595       *
596       * @see CubicCurve2D#solveCubic(double[],double[])
597       *
598       * @param eqn an array with the coefficients of the equation.
599       *
600       * @param res an array into which the non-complex roots will be
601       * stored.  The results may be in an arbitrary order. It is safe to
602       * pass the same array object reference for both <code>eqn</code>
603       * and <code>res</code>.
604       *
605       * @return the number of non-complex solutions. A result of 0
606       * indicates that the equation has no non-complex solutions. A
607       * result of -1 indicates that the equation is constant (i.e.,
608       * always or never zero).
609       *
610       * @author Brian Gough (bjg@network-theory.com)
611       * (original C implementation in the <a href=
612       * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>)
613       *
614       * @author Sascha Brawer (brawer@dandelis.ch)
615       * (adaptation to Java)
616       */
617      public static int solveQuadratic(double[] eqn, double[] res)
618      {
619        // Taken from poly/solve_quadratic.c in the GNU Scientific Library
620        // (GSL), cvs revision 1.7 of 2003-07-26. For the original source,
621        // see http://www.gnu.org/software/gsl/
622        //
623        // Brian Gough, the author of that code, has granted the
624        // permission to use it in GNU Classpath under the GNU Classpath
625        // license, and has assigned the copyright to the Free Software
626        // Foundation.
627        //
628        // The Java implementation is very similar to the GSL code, but
629        // not a strict one-to-one copy. For example, GSL would sort the
630        // result.
631        double a;
632        double b;
633        double c;
634        double disc;
635    
636        c = eqn[0];
637        b = eqn[1];
638        a = eqn[2];
639    
640        // Check for linear or constant functions. This is not done by the
641        // GNU Scientific Library.  Without this special check, we
642        // wouldn't return -1 for constant functions, and 2 instead of 1
643        // for linear functions.
644        if (a == 0)
645          {
646            if (b == 0)
647              return -1;
648    
649            res[0] = -c / b;
650            return 1;
651          }
652    
653        disc = b * b - 4 * a * c;
654    
655        if (disc < 0)
656          return 0;
657    
658        if (disc == 0)
659          {
660            // The GNU Scientific Library returns two identical results here.
661            // We just return one.
662            res[0] = -0.5 * b / a;
663            return 1;
664          }
665    
666        // disc > 0
667        if (b == 0)
668          {
669            double r;
670    
671            r = Math.abs(0.5 * Math.sqrt(disc) / a);
672            res[0] = -r;
673            res[1] = r;
674          }
675        else
676          {
677            double sgnb;
678            double temp;
679    
680            sgnb = (b > 0 ? 1 : -1);
681            temp = -0.5 * (b + sgnb * Math.sqrt(disc));
682    
683            // The GNU Scientific Library sorts the result here. We don't.
684            res[0] = temp / a;
685            res[1] = c / temp;
686          }
687        return 2;
688      }
689    
690      /**
691       * Determines whether a point is inside the area bounded
692       * by the curve and the straight line connecting its end points.
693       *
694       * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
695       * alt="A drawing of the area spanned by the curve" />
696       *
697       * <p>The above drawing illustrates in which area points are
698       * considered &#x201c;inside&#x201d; a QuadCurve2D.
699       */
700      public boolean contains(double x, double y)
701      {
702        if (! getBounds2D().contains(x, y))
703          return false;
704    
705        return ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0);
706      }
707    
708      /**
709       * Determines whether a point is inside the area bounded
710       * by the curve and the straight line connecting its end points.
711       *
712       * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
713       * alt="A drawing of the area spanned by the curve" />
714       *
715       * <p>The above drawing illustrates in which area points are
716       * considered &#x201c;inside&#x201d; a QuadCurve2D.
717       */
718      public boolean contains(Point2D p)
719      {
720        return contains(p.getX(), p.getY());
721      }
722    
723      /**
724       * Determines whether any part of a rectangle is inside the area bounded
725       * by the curve and the straight line connecting its end points.
726       *
727       * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
728       * alt="A drawing of the area spanned by the curve" />
729       *
730       * <p>The above drawing illustrates in which area points are
731       * considered &#x201c;inside&#x201d; in a CubicCurve2D.
732       */
733      public boolean intersects(double x, double y, double w, double h)
734      {
735        if (! getBounds2D().contains(x, y, w, h))
736          return false;
737    
738        /* Does any edge intersect? */
739        if (getAxisIntersections(x, y, true, w) != 0 /* top */
740            || getAxisIntersections(x, y + h, true, w) != 0 /* bottom */
741            || getAxisIntersections(x + w, y, false, h) != 0 /* right */
742            || getAxisIntersections(x, y, false, h) != 0) /* left */
743          return true;
744    
745        /* No intersections, is any point inside? */
746        if ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0)
747          return true;
748    
749        return false;
750      }
751    
752      /**
753       * Determines whether any part of a Rectangle2D is inside the area bounded 
754       * by the curve and the straight line connecting its end points.
755       * @see #intersects(double, double, double, double)
756       */
757      public boolean intersects(Rectangle2D r)
758      {
759        return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
760      }
761    
762      /**
763       * Determines whether a rectangle is entirely inside the area bounded
764       * by the curve and the straight line connecting its end points.
765       *
766       * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
767       * alt="A drawing of the area spanned by the curve" />
768       *
769       * <p>The above drawing illustrates in which area points are
770       * considered &#x201c;inside&#x201d; a QuadCurve2D.
771       * @see #contains(double, double)
772       */
773      public boolean contains(double x, double y, double w, double h)
774      {
775        if (! getBounds2D().intersects(x, y, w, h))
776          return false;
777    
778        /* Does any edge intersect? */
779        if (getAxisIntersections(x, y, true, w) != 0 /* top */
780            || getAxisIntersections(x, y + h, true, w) != 0 /* bottom */
781            || getAxisIntersections(x + w, y, false, h) != 0 /* right */
782            || getAxisIntersections(x, y, false, h) != 0) /* left */
783          return false;
784    
785        /* No intersections, is any point inside? */
786        if ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0)
787          return true;
788    
789        return false;
790      }
791    
792      /**
793       * Determines whether a Rectangle2D is entirely inside the area that is 
794       * bounded by the curve and the straight line connecting its end points.
795       * @see #contains(double, double, double, double)
796       */
797      public boolean contains(Rectangle2D r)
798      {
799        return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
800      }
801    
802      /**
803       * Determines the smallest rectangle that encloses the
804       * curve&#x2019;s start, end and control point. As the illustration
805       * below shows, the invisible control point may cause the bounds to
806       * be much larger than the area that is actually covered by the
807       * curve.
808       *
809       * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180"
810       * alt="An illustration of the bounds of a QuadCurve2D" />
811       */
812      public Rectangle getBounds()
813      {
814        return getBounds2D().getBounds();
815      }
816    
817      public PathIterator getPathIterator(final AffineTransform at)
818      {
819        return new PathIterator()
820          {
821            /** Current coordinate. */
822            private int current = 0;
823    
824            public int getWindingRule()
825            {
826              return WIND_NON_ZERO;
827            }
828    
829            public boolean isDone()
830            {
831              return current >= 2;
832            }
833    
834            public void next()
835            {
836              current++;
837            }
838    
839            public int currentSegment(float[] coords)
840            {
841              int result;
842              switch (current)
843                {
844                case 0:
845                  coords[0] = (float) getX1();
846                  coords[1] = (float) getY1();
847                  result = SEG_MOVETO;
848                  break;
849                case 1:
850                  coords[0] = (float) getCtrlX();
851                  coords[1] = (float) getCtrlY();
852                  coords[2] = (float) getX2();
853                  coords[3] = (float) getY2();
854                  result = SEG_QUADTO;
855                  break;
856                default:
857                  throw new NoSuchElementException("quad iterator out of bounds");
858                }
859              if (at != null)
860                at.transform(coords, 0, coords, 0, 2);
861              return result;
862            }
863    
864            public int currentSegment(double[] coords)
865            {
866              int result;
867              switch (current)
868                {
869                case 0:
870                  coords[0] = getX1();
871                  coords[1] = getY1();
872                  result = SEG_MOVETO;
873                  break;
874                case 1:
875                  coords[0] = getCtrlX();
876                  coords[1] = getCtrlY();
877                  coords[2] = getX2();
878                  coords[3] = getY2();
879                  result = SEG_QUADTO;
880                  break;
881                default:
882                  throw new NoSuchElementException("quad iterator out of bounds");
883                }
884              if (at != null)
885                at.transform(coords, 0, coords, 0, 2);
886              return result;
887            }
888          };
889      }
890    
891      public PathIterator getPathIterator(AffineTransform at, double flatness)
892      {
893        return new FlatteningPathIterator(getPathIterator(at), flatness);
894      }
895    
896      /**
897       * Creates a new curve with the same contents as this one.
898       *
899       * @return the clone.
900       */
901      public Object clone()
902      {
903        try
904          {
905            return super.clone();
906          }
907        catch (CloneNotSupportedException e)
908          {
909            throw (Error) new InternalError().initCause(e); // Impossible
910          }
911      }
912    
913      /**
914       * Helper method used by contains() and intersects() methods
915       * Return the number of curve/line intersections on a given axis
916       * extending from a certain point. useYaxis is true for using the Y axis,
917       * @param x x coordinate of the origin point
918       * @param y y coordinate of the origin point
919       * @param useYaxis axis to follow, if true the positive Y axis is used,
920       * false uses the positive X axis.
921       *
922       * This is an implementation of the line-crossings algorithm,
923       * Detailed in an article on Eric Haines' page:
924       * http://www.acm.org/tog/editors/erich/ptinpoly/
925       */
926      private int getAxisIntersections(double x, double y, boolean useYaxis,
927                                       double distance)
928      {
929        int nCrossings = 0;
930        double a0;
931        double a1;
932        double a2;
933        double b0;
934        double b1;
935        double b2;
936        double[] r = new double[3];
937        int nRoots;
938    
939        a0 = a2 = 0.0;
940    
941        if (useYaxis)
942          {
943            a0 = getY1() - y;
944            a1 = getCtrlY() - y;
945            a2 = getY2() - y;
946            b0 = getX1() - x;
947            b1 = getCtrlX() - x;
948            b2 = getX2() - x;
949          }
950        else
951          {
952            a0 = getX1() - x;
953            a1 = getCtrlX() - x;
954            a2 = getX2() - x;
955            b0 = getY1() - y;
956            b1 = getCtrlY() - y;
957            b2 = getY2() - y;
958          }
959    
960        /* If the axis intersects a start/endpoint, shift it up by some small 
961           amount to guarantee the line is 'inside'
962           If this is not done,bad behaviour may result for points on that axis. */
963        if (a0 == 0.0 || a2 == 0.0)
964          {
965            double small = getFlatness() * EPSILON;
966            if (a0 == 0.0)
967              a0 -= small;
968    
969            if (a2 == 0.0)
970              a2 -= small;
971          }
972    
973        r[0] = a0;
974        r[1] = 2 * (a1 - a0);
975        r[2] = (a2 - 2 * a1 + a0);
976    
977        nRoots = solveQuadratic(r);
978        for (int i = 0; i < nRoots; i++)
979          {
980            double t = r[i];
981            if (t >= 0.0 && t <= 1.0)
982              {
983                double crossing = t * t * (b2 - 2 * b1 + b0) + 2 * t * (b1 - b0)
984                                  + b0;
985                /* single root is always doubly degenerate in quads */
986                if (crossing > 0 && crossing < distance)
987                  nCrossings += (nRoots == 1) ? 2 : 1;
988              }
989          }
990    
991        if (useYaxis)
992          {
993            if (Line2D.linesIntersect(b0, a0, b2, a2, EPSILON, 0.0, distance, 0.0))
994              nCrossings++;
995          }
996        else
997          {
998            if (Line2D.linesIntersect(a0, b0, a2, b2, 0.0, EPSILON, 0.0, distance))
999              nCrossings++;
1000          }
1001    
1002        return (nCrossings);
1003      }
1004    
1005      /**
1006       * A two-dimensional curve that is parameterized with a quadratic
1007       * function and stores coordinate values in double-precision
1008       * floating-point format.
1009       *
1010       * @see QuadCurve2D.Float
1011       *
1012       * @author Eric Blake (ebb9@email.byu.edu)
1013       * @author Sascha Brawer (brawer@dandelis.ch)
1014       */
1015      public static class Double extends QuadCurve2D
1016      {
1017        /**
1018         * The <i>x</i> coordinate of the curve&#x2019;s start point.
1019         */
1020        public double x1;
1021    
1022        /**
1023         * The <i>y</i> coordinate of the curve&#x2019;s start point.
1024         */
1025        public double y1;
1026    
1027        /**
1028         * The <i>x</i> coordinate of the curve&#x2019;s control point.
1029         */
1030        public double ctrlx;
1031    
1032        /**
1033         * The <i>y</i> coordinate of the curve&#x2019;s control point.
1034         */
1035        public double ctrly;
1036    
1037        /**
1038         * The <i>x</i> coordinate of the curve&#x2019;s end point.
1039         */
1040        public double x2;
1041    
1042        /**
1043         * The <i>y</i> coordinate of the curve&#x2019;s end point.
1044         */
1045        public double y2;
1046    
1047        /**
1048         * Constructs a new QuadCurve2D that stores its coordinate values
1049         * in double-precision floating-point format. All points are
1050         * initially at position (0, 0).
1051         */
1052        public Double()
1053        {
1054        }
1055    
1056        /**
1057         * Constructs a new QuadCurve2D that stores its coordinate values
1058         * in double-precision floating-point format, specifying the
1059         * initial position of each point.
1060         *
1061         * @param x1 the <i>x</i> coordinate of the curve&#x2019;s start
1062         * point.
1063         *
1064         * @param y1 the <i>y</i> coordinate of the curve&#x2019;s start
1065         * point.
1066         *
1067         * @param cx the <i>x</i> coordinate of the curve&#x2019;s control
1068         * point.
1069         *
1070         * @param cy the <i>y</i> coordinate of the curve&#x2019;s control
1071         * point.
1072         *
1073         * @param x2 the <i>x</i> coordinate of the curve&#x2019;s end
1074         * point.
1075         *
1076         * @param y2 the <i>y</i> coordinate of the curve&#x2019;s end
1077         * point.
1078         */
1079        public Double(double x1, double y1, double cx, double cy, double x2,
1080                      double y2)
1081        {
1082          this.x1 = x1;
1083          this.y1 = y1;
1084          ctrlx = cx;
1085          ctrly = cy;
1086          this.x2 = x2;
1087          this.y2 = y2;
1088        }
1089    
1090        /**
1091         * Returns the <i>x</i> coordinate of the curve&#x2019;s start
1092         * point.
1093         */
1094        public double getX1()
1095        {
1096          return x1;
1097        }
1098    
1099        /**
1100         * Returns the <i>y</i> coordinate of the curve&#x2019;s start
1101         * point.
1102         */
1103        public double getY1()
1104        {
1105          return y1;
1106        }
1107    
1108        /**
1109         * Returns the curve&#x2019;s start point.
1110         */
1111        public Point2D getP1()
1112        {
1113          return new Point2D.Double(x1, y1);
1114        }
1115    
1116        /**
1117         * Returns the <i>x</i> coordinate of the curve&#x2019;s control
1118         * point.
1119         */
1120        public double getCtrlX()
1121        {
1122          return ctrlx;
1123        }
1124    
1125        /**
1126         * Returns the <i>y</i> coordinate of the curve&#x2019;s control
1127         * point.
1128         */
1129        public double getCtrlY()
1130        {
1131          return ctrly;
1132        }
1133    
1134        /**
1135         * Returns the curve&#x2019;s control point.
1136         */
1137        public Point2D getCtrlPt()
1138        {
1139          return new Point2D.Double(ctrlx, ctrly);
1140        }
1141    
1142        /**
1143         * Returns the <i>x</i> coordinate of the curve&#x2019;s end
1144         * point.
1145         */
1146        public double getX2()
1147        {
1148          return x2;
1149        }
1150    
1151        /**
1152         * Returns the <i>y</i> coordinate of the curve&#x2019;s end
1153         * point.
1154         */
1155        public double getY2()
1156        {
1157          return y2;
1158        }
1159    
1160        /**
1161         * Returns the curve&#x2019;s end point.
1162         */
1163        public Point2D getP2()
1164        {
1165          return new Point2D.Double(x2, y2);
1166        }
1167    
1168        /**
1169         * Changes the geometry of the curve.
1170         *
1171         * @param x1 the <i>x</i> coordinate of the curve&#x2019;s new
1172         * start point.
1173         *
1174         * @param y1 the <i>y</i> coordinate of the curve&#x2019;s new
1175         * start point.
1176         *
1177         * @param cx the <i>x</i> coordinate of the curve&#x2019;s new
1178         * control point.
1179         *
1180         * @param cy the <i>y</i> coordinate of the curve&#x2019;s new
1181         * control point.
1182         *
1183         * @param x2 the <i>x</i> coordinate of the curve&#x2019;s new
1184         * end point.
1185         *
1186         * @param y2 the <i>y</i> coordinate of the curve&#x2019;s new
1187         * end point.
1188         */
1189        public void setCurve(double x1, double y1, double cx, double cy,
1190                             double x2, double y2)
1191        {
1192          this.x1 = x1;
1193          this.y1 = y1;
1194          ctrlx = cx;
1195          ctrly = cy;
1196          this.x2 = x2;
1197          this.y2 = y2;
1198        }
1199    
1200        /**
1201         * Determines the smallest rectangle that encloses the
1202         * curve&#x2019;s start, end and control point. As the
1203         * illustration below shows, the invisible control point may cause
1204         * the bounds to be much larger than the area that is actually
1205         * covered by the curve.
1206         *
1207         * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180"
1208         * alt="An illustration of the bounds of a QuadCurve2D" />
1209         */
1210        public Rectangle2D getBounds2D()
1211        {
1212          double nx1 = Math.min(Math.min(x1, ctrlx), x2);
1213          double ny1 = Math.min(Math.min(y1, ctrly), y2);
1214          double nx2 = Math.max(Math.max(x1, ctrlx), x2);
1215          double ny2 = Math.max(Math.max(y1, ctrly), y2);
1216          return new Rectangle2D.Double(nx1, ny1, nx2 - nx1, ny2 - ny1);
1217        }
1218      }
1219    
1220      /**
1221       * A two-dimensional curve that is parameterized with a quadratic
1222       * function and stores coordinate values in single-precision
1223       * floating-point format.
1224       *
1225       * @see QuadCurve2D.Double
1226       *
1227       * @author Eric Blake (ebb9@email.byu.edu)
1228       * @author Sascha Brawer (brawer@dandelis.ch)
1229       */
1230      public static class Float extends QuadCurve2D
1231      {
1232        /**
1233         * The <i>x</i> coordinate of the curve&#x2019;s start point.
1234         */
1235        public float x1;
1236    
1237        /**
1238         * The <i>y</i> coordinate of the curve&#x2019;s start point.
1239         */
1240        public float y1;
1241    
1242        /**
1243         * The <i>x</i> coordinate of the curve&#x2019;s control point.
1244         */
1245        public float ctrlx;
1246    
1247        /**
1248         * The <i>y</i> coordinate of the curve&#x2019;s control point.
1249         */
1250        public float ctrly;
1251    
1252        /**
1253         * The <i>x</i> coordinate of the curve&#x2019;s end point.
1254         */
1255        public float x2;
1256    
1257        /**
1258         * The <i>y</i> coordinate of the curve&#x2019;s end point.
1259         */
1260        public float y2;
1261    
1262        /**
1263         * Constructs a new QuadCurve2D that stores its coordinate values
1264         * in single-precision floating-point format. All points are
1265         * initially at position (0, 0).
1266         */
1267        public Float()
1268        {
1269        }
1270    
1271        /**
1272         * Constructs a new QuadCurve2D that stores its coordinate values
1273         * in single-precision floating-point format, specifying the
1274         * initial position of each point.
1275         *
1276         * @param x1 the <i>x</i> coordinate of the curve&#x2019;s start
1277         * point.
1278         *
1279         * @param y1 the <i>y</i> coordinate of the curve&#x2019;s start
1280         * point.
1281         *
1282         * @param cx the <i>x</i> coordinate of the curve&#x2019;s control
1283         * point.
1284         *
1285         * @param cy the <i>y</i> coordinate of the curve&#x2019;s control
1286         * point.
1287         *
1288         * @param x2 the <i>x</i> coordinate of the curve&#x2019;s end
1289         * point.
1290         *
1291         * @param y2 the <i>y</i> coordinate of the curve&#x2019;s end
1292         * point.
1293         */
1294        public Float(float x1, float y1, float cx, float cy, float x2, float y2)
1295        {
1296          this.x1 = x1;
1297          this.y1 = y1;
1298          ctrlx = cx;
1299          ctrly = cy;
1300          this.x2 = x2;
1301          this.y2 = y2;
1302        }
1303    
1304        /**
1305         * Returns the <i>x</i> coordinate of the curve&#x2019;s start
1306         * point.
1307         */
1308        public double getX1()
1309        {
1310          return x1;
1311        }
1312    
1313        /**
1314         * Returns the <i>y</i> coordinate of the curve&#x2019;s start
1315         * point.
1316         */
1317        public double getY1()
1318        {
1319          return y1;
1320        }
1321    
1322        /**
1323         * Returns the curve&#x2019;s start point.
1324         */
1325        public Point2D getP1()
1326        {
1327          return new Point2D.Float(x1, y1);
1328        }
1329    
1330        /**
1331         * Returns the <i>x</i> coordinate of the curve&#x2019;s control
1332         * point.
1333         */
1334        public double getCtrlX()
1335        {
1336          return ctrlx;
1337        }
1338    
1339        /**
1340         * Returns the <i>y</i> coordinate of the curve&#x2019;s control
1341         * point.
1342         */
1343        public double getCtrlY()
1344        {
1345          return ctrly;
1346        }
1347    
1348        /**
1349         * Returns the curve&#x2019;s control point.
1350         */
1351        public Point2D getCtrlPt()
1352        {
1353          return new Point2D.Float(ctrlx, ctrly);
1354        }
1355    
1356        /**
1357         * Returns the <i>x</i> coordinate of the curve&#x2019;s end
1358         * point.
1359         */
1360        public double getX2()
1361        {
1362          return x2;
1363        }
1364    
1365        /**
1366         * Returns the <i>y</i> coordinate of the curve&#x2019;s end
1367         * point.
1368         */
1369        public double getY2()
1370        {
1371          return y2;
1372        }
1373    
1374        /**
1375         * Returns the curve&#x2019;s end point.
1376         */
1377        public Point2D getP2()
1378        {
1379          return new Point2D.Float(x2, y2);
1380        }
1381    
1382        /**
1383         * Changes the geometry of the curve, specifying coordinate values
1384         * as double-precision floating-point numbers.
1385         *
1386         * @param x1 the <i>x</i> coordinate of the curve&#x2019;s new
1387         * start point.
1388         *
1389         * @param y1 the <i>y</i> coordinate of the curve&#x2019;s new
1390         * start point.
1391         *
1392         * @param cx the <i>x</i> coordinate of the curve&#x2019;s new
1393         * control point.
1394         *
1395         * @param cy the <i>y</i> coordinate of the curve&#x2019;s new
1396         * control point.
1397         *
1398         * @param x2 the <i>x</i> coordinate of the curve&#x2019;s new
1399         * end point.
1400         *
1401         * @param y2 the <i>y</i> coordinate of the curve&#x2019;s new
1402         * end point.
1403         */
1404        public void setCurve(double x1, double y1, double cx, double cy,
1405                             double x2, double y2)
1406        {
1407          this.x1 = (float) x1;
1408          this.y1 = (float) y1;
1409          ctrlx = (float) cx;
1410          ctrly = (float) cy;
1411          this.x2 = (float) x2;
1412          this.y2 = (float) y2;
1413        }
1414    
1415        /**
1416         * Changes the geometry of the curve, specifying coordinate values
1417         * as single-precision floating-point numbers.
1418         *
1419         * @param x1 the <i>x</i> coordinate of the curve&#x2019;s new
1420         * start point.
1421         *
1422         * @param y1 the <i>y</i> coordinate of the curve&#x2019;s new
1423         * start point.
1424         *
1425         * @param cx the <i>x</i> coordinate of the curve&#x2019;s new
1426         * control point.
1427         *
1428         * @param cy the <i>y</i> coordinate of the curve&#x2019;s new
1429         * control point.
1430         *
1431         * @param x2 the <i>x</i> coordinate of the curve&#x2019;s new
1432         * end point.
1433         *
1434         * @param y2 the <i>y</i> coordinate of the curve&#x2019;s new
1435         * end point.
1436         */
1437        public void setCurve(float x1, float y1, float cx, float cy, float x2,
1438                             float y2)
1439        {
1440          this.x1 = x1;
1441          this.y1 = y1;
1442          ctrlx = cx;
1443          ctrly = cy;
1444          this.x2 = x2;
1445          this.y2 = y2;
1446        }
1447    
1448        /**
1449         * Determines the smallest rectangle that encloses the
1450         * curve&#x2019;s start, end and control point. As the
1451         * illustration below shows, the invisible control point may cause
1452         * the bounds to be much larger than the area that is actually
1453         * covered by the curve.
1454         *
1455         * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180"
1456         * alt="An illustration of the bounds of a QuadCurve2D" />
1457         */
1458        public Rectangle2D getBounds2D()
1459        {
1460          float nx1 = Math.min(Math.min(x1, ctrlx), x2);
1461          float ny1 = Math.min(Math.min(y1, ctrly), y2);
1462          float nx2 = Math.max(Math.max(x1, ctrlx), x2);
1463          float ny2 = Math.max(Math.max(y1, ctrly), y2);
1464          return new Rectangle2D.Float(nx1, ny1, nx2 - nx1, ny2 - ny1);
1465        }
1466      }
1467    }