001/* QuadCurve2D.java -- represents a parameterized quadratic curve in 2-D space
002   Copyright (C) 2002, 2003, 2004 Free Software Foundation
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038package java.awt.geom;
039
040import java.awt.Rectangle;
041import java.awt.Shape;
042import 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 */
058public 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}