quadcurve2d.java

gcc的组建

    y1 = src[srcOff + 1];
    xc = src[srcOff + 2];
    yc = src[srcOff + 3];
    x2 = src[srcOff + 4];
    y2 = src[srcOff + 5];

    if (left != null)
      {
	left[leftOff] = x1;
	left[leftOff + 1] = y1;
      }

    if (right != null)
      {
	right[rightOff + 4] = x2;
	right[rightOff + 5] = y2;
      }

    x1 = (x1 + xc) / 2;
    x2 = (xc + x2) / 2;
    xc = (x1 + x2) / 2;
    y1 = (y1 + yc) / 2;
    y2 = (y2 + yc) / 2;
    yc = (y1 + y2) / 2;

    if (left != null)
      {
	left[leftOff + 2] = x1;
	left[leftOff + 3] = y1;
	left[leftOff + 4] = xc;
	left[leftOff + 5] = yc;
      }

    if (right != null)
      {
	right[rightOff] = xc;
	right[rightOff + 1] = yc;
	right[rightOff + 2] = x2;
	right[rightOff + 3] = y2;
      }
  }

  /**
   * Finds the non-complex roots of a quadratic equation, placing the
   * results into the same array as the equation coefficients. The
   * following equation is being solved:
   *
   * <blockquote><code>eqn[2]</code> &#xb7; <i>x</i><sup>2</sup>
   * + <code>eqn[1]</code> &#xb7; <i>x</i>
   * + <code>eqn[0]</code>
   * = 0
   * </blockquote>
   *
   * <p>For some background about solving quadratic equations, see the
   * article <a href=
   * "http://planetmath.org/encyclopedia/QuadraticFormula.html"
   * >&#x201c;Quadratic Formula&#x201d;</a> in <a href=
   * "http://planetmath.org/">PlanetMath</a>. For an extensive library
   * of numerical algorithms written in the C programming language,
   * see the <a href="http://www.gnu.org/software/gsl/">GNU Scientific
   * Library</a>.
   *
   * @see #solveQuadratic(double[], double[])
   * @see CubicCurve2D#solveCubic(double[], double[])
   *
   * @param eqn an array with the coefficients of the equation. When
   * this procedure has returned, <code>eqn</code> will contain the
   * non-complex solutions of the equation, in no particular order.
   *
   * @return the number of non-complex solutions. A result of 0
   * indicates that the equation has no non-complex solutions. A
   * result of -1 indicates that the equation is constant (i.e.,
   * always or never zero).
   *
   * @author Brian Gough ([e-mail])
   * (original C implementation in the <a href=
   * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>)
   *
   * @author Sascha Brawer ([e-mail])
   * (adaptation to Java)
   */
  public static int solveQuadratic(double[] eqn)
  {
    return solveQuadratic(eqn, eqn);
  }

  /**
   * Finds the non-complex roots of a quadratic equation. The
   * following equation is being solved:
   *
   * <blockquote><code>eqn[2]</code> &#xb7; <i>x</i><sup>2</sup>
   * + <code>eqn[1]</code> &#xb7; <i>x</i>
   * + <code>eqn[0]</code>
   * = 0
   * </blockquote>
   *
   * <p>For some background about solving quadratic equations, see the
   * article <a href=
   * "http://planetmath.org/encyclopedia/QuadraticFormula.html"
   * >&#x201c;Quadratic Formula&#x201d;</a> in <a href=
   * "http://planetmath.org/">PlanetMath</a>. For an extensive library
   * of numerical algorithms written in the C programming language,
   * see the <a href="http://www.gnu.org/software/gsl/">GNU Scientific
   * Library</a>.
   *
   * @see CubicCurve2D#solveCubic(double[],double[])
   *
   * @param eqn an array with the coefficients of the equation.
   *
   * @param res an array into which the non-complex roots will be
   * stored.  The results may be in an arbitrary order. It is safe to
   * pass the same array object reference for both <code>eqn</code>
   * and <code>res</code>.
   *
   * @return the number of non-complex solutions. A result of 0
   * indicates that the equation has no non-complex solutions. A
   * result of -1 indicates that the equation is constant (i.e.,
   * always or never zero).
   *
   * @author Brian Gough ([e-mail])
   * (original C implementation in the <a href=
   * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>)
   *
   * @author Sascha Brawer ([e-mail])
   * (adaptation to Java)
   */
  public static int solveQuadratic(double[] eqn, double[] res)
  {
    // Taken from poly/solve_quadratic.c in the GNU Scientific Library
    // (GSL), cvs revision 1.7 of 2003-07-26. For the original source,
    // see http://www.gnu.org/software/gsl/
    //
    // Brian Gough, the author of that code, has granted the
    // permission to use it in GNU Classpath under the GNU Classpath
    // license, and has assigned the copyright to the Free Software
    // Foundation.
    //
    // The Java implementation is very similar to the GSL code, but
    // not a strict one-to-one copy. For example, GSL would sort the
    // result.
    double a;
    double b;
    double c;
    double disc;

    c = eqn[0];
    b = eqn[1];
    a = eqn[2];

    // Check for linear or constant functions. This is not done by the
    // GNU Scientific Library.  Without this special check, we
    // wouldn't return -1 for constant functions, and 2 instead of 1
    // for linear functions.
    if (a == 0)
      {
	if (b == 0)
	  return -1;

	res[0] = -c / b;
	return 1;
      }

    disc = b * b - 4 * a * c;

    if (disc < 0)
      return 0;

    if (disc == 0)
      {
	// The GNU Scientific Library returns two identical results here.
	// We just return one.
	res[0] = -0.5 * b / a;
	return 1;
      }

    // disc > 0
    if (b == 0)
      {
	double r;

	r = Math.abs(0.5 * Math.sqrt(disc) / a);
	res[0] = -r;
	res[1] = r;
      }
    else
      {
	double sgnb;
	double temp;

	sgnb = (b > 0 ? 1 : -1);
	temp = -0.5 * (b + sgnb * Math.sqrt(disc));

	// The GNU Scientific Library sorts the result here. We don't.
	res[0] = temp / a;
	res[1] = c / temp;
      }
    return 2;
  }

  /**
   * Determines whether a point is inside the area bounded
   * by the curve and the straight line connecting its end points.
   *
   * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
   * alt="A drawing of the area spanned by the curve" />
   *
   * <p>The above drawing illustrates in which area points are
   * considered &#x201c;inside&#x201d; a QuadCurve2D.
   */
  public boolean contains(double x, double y)
  {
    if (! getBounds2D().contains(x, y))
      return false;

    return ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0);
  }

  /**
   * Determines whether a point is inside the area bounded
   * by the curve and the straight line connecting its end points.
   *
   * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
   * alt="A drawing of the area spanned by the curve" />
   *
   * <p>The above drawing illustrates in which area points are
   * considered &#x201c;inside&#x201d; a QuadCurve2D.
   */
  public boolean contains(Point2D p)
  {
    return contains(p.getX(), p.getY());
  }

  /**
   * Determines whether any part of a rectangle is inside the area bounded
   * by the curve and the straight line connecting its end points.
   *
   * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
   * alt="A drawing of the area spanned by the curve" />
   *
   * <p>The above drawing illustrates in which area points are
   * considered &#x201c;inside&#x201d; in a CubicCurve2D.
   */
  public boolean intersects(double x, double y, double w, double h)
  {
    if (! getBounds2D().contains(x, y, w, h))
      return false;

    /* Does any edge intersect? */
    if (getAxisIntersections(x, y, true, w) != 0 /* top */
        || getAxisIntersections(x, y + h, true, w) != 0 /* bottom */
        || getAxisIntersections(x + w, y, false, h) != 0 /* right */
        || getAxisIntersections(x, y, false, h) != 0) /* left */
      return true;

    /* No intersections, is any point inside? */
    if ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0)
      return true;

    return false;
  }

  /**
   * Determines whether any part of a Rectangle2D is inside the area bounded 
   * by the curve and the straight line connecting its end points.
   * @see #intersects(double, double, double, double)
   */
  public boolean intersects(Rectangle2D r)
  {
    return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  }

  /**
   * Determines whether a rectangle is entirely inside the area bounded
   * by the curve and the straight line connecting its end points.
   *
   * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180"
   * alt="A drawing of the area spanned by the curve" />
   *
   * <p>The above drawing illustrates in which area points are
   * considered &#x201c;inside&#x201d; a QuadCurve2D.
   * @see #contains(double, double)
   */
  public boolean contains(double x, double y, double w, double h)
  {
    if (! getBounds2D().intersects(x, y, w, h))
      return false;

    /* Does any edge intersect? */
    if (getAxisIntersections(x, y, true, w) != 0 /* top */
        || getAxisIntersections(x, y + h, true, w) != 0 /* bottom */
        || getAxisIntersections(x + w, y, false, h) != 0 /* right */
        || getAxisIntersections(x, y, false, h) != 0) /* left */
      return false;

    /* No intersections, is any point inside? */
    if ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0)
      return true;

    return false;
  }

  /**
   * Determines whether a Rectangle2D is entirely inside the area that is 
   * bounded by the curve and the straight line connecting its end points.
   * @see #contains(double, double, double, double)
   */
  public boolean contains(Rectangle2D r)
  {
    return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  }

  /**
   * Determines the smallest rectangle that encloses the
   * curve&#x2019;s start, end and control point. As the illustration
   * below shows, the invisible control point may cause the bounds to
   * be much larger than the area that is actually covered by the
   * curve.
   *
   * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180"
   * alt="An illustration of the bounds of a QuadCurve2D" />
   */
  public Rectangle getBounds()
  {
    return getBounds2D().getBounds();
  }

  public PathIterator getPathIterator(final AffineTransform at)
  {
    return new PathIterator()
      {
	/** Current coordinate. */
	private int current = 0;

	public int getWindingRule()
	{
	  return WIND_NON_ZERO;
	}

	public boolean isDone()
	{
	  return current >= 2;
	}

	public void next()
	{
	  current++;
	}

	public int currentSegment(float[] coords)
	{
	  int result;
	  switch (current)
	    {
	    case 0:
	      coords[0] = (float) getX1();
	      coords[1] = (float) getY1();
	      result = SEG_MOVETO;
	      break;
	    case 1:
	      coords[0] = (float) getCtrlX();
	      coords[1] = (float) getCtrlY();
	      coords[2] = (float) getX2();
	      coords[3] = (float) getY2();
	      result = SEG_QUADTO;
	      break;
	    default:
	      throw new NoSuchElementException("quad iterator out of bounds");
	    }
	  if (at != null)
	    at.transform(coords, 0, coords, 0, 2);
	  return result;
	}

	public int currentSegment(double[] coords)
	{
	  int result;
	  switch (current)
	    {
	    case 0:
	      coords[0] = getX1();
	      coords[1] = getY1();
	      result = SEG_MOVETO;
	      break;
	    case 1:
	      coords[0] = getCtrlX();
	      coords[1] = getCtrlY();
	      coords[2] = getX2();
	      coords[3] = getY2();
	      result = SEG_QUADTO;
	      break;
	    default:
	      throw new NoSuchElementException("quad iterator out of bounds");
	    }
	  if (at != null)
	    at.transform(coords, 0, coords, 0, 2);
	  return result;
	}
      };
  }

  public PathIterator getPathIterator(AffineTransform at, double flatness)
  {
    return new FlatteningPathIterator(getPathIterator(at), flatness);
  }

  /**
   * Creates a new curve with the same contents as this one.
   *
   * @return the clone.
   */
  public Object clone()
  {
    try
      {
	return super.clone();
      }
    catch (CloneNotSupportedException e)
      {
	throw (Error) new InternalError().initCause(e); // Impossible
      }
  }

  /**
   * Helper method used by contains() and intersects() methods
   * Return the number of curve/line intersections on a given axis
   * extending from a certain point. useYaxis is true for using the Y axis,
   * @param x x coordinate of the origin point
   * @param y y coordinate of the origin point
   * @param useYaxis axis to follow, if true the positive Y axis is used,
   * false uses the positive X axis.
   *
   * This is an implementation of the line-crossings algorithm,
   * Detailed in an article on Eric Haines' page:
   * http://www.acm.org/tog/editors/erich/ptinpoly/
   */
  private int getAxisIntersections(double x, double y, boolean useYaxis,
                                   double distance)
  {
    int nCrossings = 0;
    double a0;
    double a1;
    double a2;
    double b0;
    double b1;
    double b2;
    double[] r = new double[3];
    int nRoots;

    a0 = a2 = 0.0;

    if (useYaxis)
      {
	a0 = getY1() - y;
	a1 = getCtrlY() - y;
	a2 = getY2() - y;
	b0 = getX1() - x;
	b1 = getCtrlX() - x;
	b2 = getX2() - x;
      }
    else
      {
	a0 = getX1() - x;
	a1 = getCtrlX() - x;
	a2 = getX2() - x;
	b0 = getY1() - y;
	b1 = getCtrlY() - y;
	b2 = getY2() - y;
      }

    /* If the axis intersects a start/endpoint, shift it up by some small 
       amount to guarantee the line is 'inside'
       If this is not done,bad behaviour may result for points on that axis. */
    if (a0 == 0.0 || a2 == 0.0)
      {
	double small = getFlatness() * EPSILON;
	if (a0 == 0.0)
	  a0 -= small;

	if (a2 == 0.0)
	  a2 -= small;
      }

    r[0] = a0;
    r[1] = 2 * (a1 - a0);
    r[2] = (a2 - 2 * a1 + a0);

    nRoots = solveQuadratic(r);
    for (int i = 0; i < nRoots; i++)
      {
	double t = r[i];