area.java

linux下建立JAVA虚拟机的源码KAFFE

      return null;

    double x1 = P1.getX();
    double y1 = P1.getY();
    double rx = P2.getX() - x1;
    double ry = P2.getY() - y1;

    double x2 = P3.getX();
    double y2 = P3.getY();
    double sx = P4.getX() - x2;
    double sy = P4.getY() - y2;

    double determinant = sx * ry - sy * rx;
    double nom = (sx * (y2 - y1) + sy * (x1 - x2));

    // Parallel lines don't intersect. At least we pretend they don't.
    if (Math.abs(determinant) < EPSILON)
      return null;

    nom = nom / determinant;

    if (nom == 0.0)
      return null;
    if (nom == 1.0)
      return null;

    Point2D p = new Point2D.Double(x1 + nom * rx, y1 + nom * ry);

    return new Intersection(p, p.distance(P1) / P1.distance(P2),
                            p.distance(P3) / P3.distance(P4));
  }

  /**
   * Determines if two points are equal, within an error margin
   * 'snap distance'
   * This is package-private to avoid an accessor method.
   */
  boolean pointEquals(Point2D a, Point2D b)
  {
    return (a.equals(b) || a.distance(b) < PE_EPSILON);
  }

  /**
   * Helper method
   * Turns a shape into a Vector of Segments
   */
  private Vector makeSegment(Shape s)
  {
    Vector paths = new Vector();
    PathIterator pi = s.getPathIterator(null);
    double[] coords = new double[6];
    Segment subpath = null;
    Segment current = null;
    double cx;
    double cy;
    double subpathx;
    double subpathy;
    cx = cy = subpathx = subpathy = 0.0;

    this.windingRule = pi.getWindingRule();

    while (! pi.isDone())
      {
	Segment v;
	switch (pi.currentSegment(coords))
	  {
	  case PathIterator.SEG_MOVETO:
	    if (subpath != null)
	      { // close existing open path
		current.next = new LineSegment(cx, cy, subpathx, subpathy);
		current = current.next;
		current.next = subpath;
	      }
	    subpath = null;
	    subpathx = cx = coords[0];
	    subpathy = cy = coords[1];
	    break;

	  // replace 'close' with a line-to.
	  case PathIterator.SEG_CLOSE:
	    if (subpath != null && (subpathx != cx || subpathy != cy))
	      {
		current.next = new LineSegment(cx, cy, subpathx, subpathy);
		current = current.next;
		current.next = subpath;
		cx = subpathx;
		cy = subpathy;
		subpath = null;
	      }
	    else if (subpath != null)
	      {
		current.next = subpath;
		subpath = null;
	      }
	    break;
	  case PathIterator.SEG_LINETO:
	    if (cx != coords[0] || cy != coords[1])
	      {
		v = new LineSegment(cx, cy, coords[0], coords[1]);
		if (subpath == null)
		  {
		    subpath = current = v;
		    paths.add(subpath);
		  }
		else
		  {
		    current.next = v;
		    current = current.next;
		  }
		cx = coords[0];
		cy = coords[1];
	      }
	    break;
	  case PathIterator.SEG_QUADTO:
	    v = new QuadSegment(cx, cy, coords[0], coords[1], coords[2],
	                        coords[3]);
	    if (subpath == null)
	      {
		subpath = current = v;
		paths.add(subpath);
	      }
	    else
	      {
		current.next = v;
		current = current.next;
	      }
	    cx = coords[2];
	    cy = coords[3];
	    break;
	  case PathIterator.SEG_CUBICTO:
	    v = new CubicSegment(cx, cy, coords[0], coords[1], coords[2],
	                         coords[3], coords[4], coords[5]);
	    if (subpath == null)
	      {
		subpath = current = v;
		paths.add(subpath);
	      }
	    else
	      {
		current.next = v;
		current = current.next;
	      }

	    // check if the cubic is self-intersecting
	    double[] lpts = ((CubicSegment) v).getLoop();
	    if (lpts != null)
	      {
		// if it is, break off the loop into its own path.
		v.subdivideInsert(lpts[0]);
		v.next.subdivideInsert((lpts[1] - lpts[0]) / (1.0 - lpts[0]));

		CubicSegment loop = (CubicSegment) v.next;
		v.next = loop.next;
		loop.next = loop;

		v.P2 = v.next.P1 = loop.P2 = loop.P1; // snap points
		paths.add(loop);
		current = v.next;
	      }

	    cx = coords[4];
	    cy = coords[5];
	    break;
	  }
	pi.next();
      }

    if (subpath != null)
      { // close any open path
	if (subpathx != cx || subpathy != cy)
	  {
	    current.next = new LineSegment(cx, cy, subpathx, subpathy);
	    current = current.next;
	    current.next = subpath;
	  }
	else
	  current.next = subpath;
      }

    if (paths.size() == 0)
      return (null);

    return (paths);
  }

  /**
   * Find the intersections of two separate closed paths,
   * A and B, split the segments at the intersection points,
   * and create nodes pointing from one to the other
   */
  private int createNodes(Segment A, Segment B)
  {
    int nNodes = 0;

    Segment a = A;
    Segment b = B;

    do
      {
	do
	  {
	    nNodes += a.splitIntersections(b);
	    b = b.next;
	  }
	while (b != B);

	a = a.next; // move to the next segment
      }
    while (a != A); // until one wrap.

    return (nNodes);
  }

  /**
   * Find the intersections of a path with itself.
   * Splits the segments at the intersection points,
   * and create nodes pointing from one to the other.
   */
  private int createNodesSelf(Segment A)
  {
    int nNodes = 0;
    Segment a = A;

    if (A.next == A)
      return 0;

    do
      {
	Segment b = a.next;
	do
	  {
	    if (b != a) // necessary
	      nNodes += a.splitIntersections(b);
	    b = b.next;
	  }
	while (b != A);
	a = a.next; // move to the next segment
      }
    while (a != A); // until one wrap.

    return (nNodes);
  }

  /**
   * Deletes paths which are redundant from a list, (i.e. solid areas within
   * solid areas) Clears any nodes. Sorts the remaining paths into solids
   * and holes, sets their orientation and sets the solids and holes lists.
   */
  private void deleteRedundantPaths(Vector paths)
  {
    int npaths = paths.size();

    int[][] contains = new int[npaths][npaths];
    int[][] windingNumbers = new int[npaths][2];
    int neg;
    Rectangle2D[] bb = new Rectangle2D[npaths]; // path bounding boxes

    neg = ((windingRule == PathIterator.WIND_NON_ZERO) ? -1 : 1);

    for (int i = 0; i < npaths; i++)
      bb[i] = ((Segment) paths.elementAt(i)).getPathBounds();

    // Find which path contains which, assign winding numbers
    for (int i = 0; i < npaths; i++)
      {
	Segment pathA = (Segment) paths.elementAt(i);
	pathA.nullNodes(); // remove any now-redundant nodes, in case.
	int windingA = pathA.hasClockwiseOrientation() ? 1 : neg;

	for (int j = 0; j < npaths; j++)
	  if (i != j)
	    {
	      Segment pathB = (Segment) paths.elementAt(j);

	      // A contains B
	      if (bb[i].intersects(bb[j]))
	        {
		  Segment s = pathB.next;
		  while (s.P1.getY() == s.P2.getY() && s != pathB)
		    s = s.next;
		  Point2D p = s.getMidPoint();
		  if (pathA.contains(p.getX(), p.getY()))
		    contains[i][j] = windingA;
	        }
	      else
		// A does not contain B
		contains[i][j] = 0;
	    }
	  else
	    contains[i][j] = windingA; // i == j
      }

    for (int i = 0; i < npaths; i++)
      {
	windingNumbers[i][0] = 0;
	for (int j = 0; j < npaths; j++)
	  windingNumbers[i][0] += contains[j][i];
	windingNumbers[i][1] = contains[i][i];
      }

    Vector solids = new Vector();
    Vector holes = new Vector();

    if (windingRule == PathIterator.WIND_NON_ZERO)
      {
	for (int i = 0; i < npaths; i++)
	  {
	    if (windingNumbers[i][0] == 0)
	      holes.add(paths.elementAt(i));
	    else if (windingNumbers[i][0] - windingNumbers[i][1] == 0
	             && Math.abs(windingNumbers[i][0]) == 1)
	      solids.add(paths.elementAt(i));
	  }
      }
    else
      {
	windingRule = PathIterator.WIND_NON_ZERO;
	for (int i = 0; i < npaths; i++)
	  {
	    if ((windingNumbers[i][0] & 1) == 0)
	      holes.add(paths.elementAt(i));
	    else if ((windingNumbers[i][0] & 1) == 1)
	      solids.add(paths.elementAt(i));
	  }
      }

    setDirection(holes, false);
    setDirection(solids, true);
    this.holes = holes;
    this.solids = solids;
  }

  /**
   * Sets the winding direction of a Vector of paths
   * @param clockwise gives the direction,
   * true = clockwise, false = counter-clockwise
   */
  private void setDirection(Vector paths, boolean clockwise)
  {
    Segment v;
    for (int i = 0; i < paths.size(); i++)
      {
	v = (Segment) paths.elementAt(i);
	if (clockwise != v.hasClockwiseOrientation())
	  v.reverseAll();
      }
  }

  /**
   * Class representing a linked-list of vertices forming a closed polygon,
   * convex or concave, without holes.
   */
  private abstract class Segment implements Cloneable
  {
    // segment type, PathIterator segment types are used.
    Point2D P1;
    Point2D P2;
    Segment next;
    Segment node;

    Segment()
    {
      P1 = P2 = null;
      node = next = null;
    }

    /**
     * Reverses the direction of a single segment
     */
    abstract void reverseCoords();

    /**
     * Returns the segment's midpoint
     */
    abstract Point2D getMidPoint();

    /**
     * Returns the bounding box of this segment
     */
    abstract Rectangle2D getBounds();

    /**
     * Transforms a single segment
     */
    abstract void transform(AffineTransform at);

    /**
     * Returns the PathIterator type of a segment
     */
    abstract int getType();

    /**
     */
    abstract int splitIntersections(Segment b);

    /**
     * Returns the PathIterator coords of a segment
     */
    abstract int pathIteratorFormat(double[] coords);

    /**
     * Returns the number of intersections on the positive X axis,
     * with the origin at (x,y), used for contains()-testing
     *
     * (Although that could be done by the line-intersect methods,
     * a dedicated method is better to guarantee consitent handling
     * of endpoint-special-cases)
     */
    abstract int rayCrossing(double x, double y);

    /**
     * Subdivides the segment at parametric value t, inserting
     * the new segment into the linked list after this,
     * such that this becomes [0,t] and this.next becomes [t,1]
     */
    abstract void subdivideInsert(double t);

    /**
     * Returns twice the area of a curve, relative the P1-P2 line
     * Used for area calculations.
     */
    abstract double curveArea();

    /**
     * Compare two segments.
     */
    abstract boolean equals(Segment b);

    /**
     * Determines if this path of segments contains the point (x,y)
     */
    boolean contains(double x, double y)
    {
      Segment v = this;
      int crossings = 0;
      do
        {
	  int n = v.rayCrossing(x, y);
	  crossings += n;
	  v = v.next;
        }
      while (v != this);
      return ((crossings & 1) == 1);
    }

    /**
     * Nulls all nodes of the path. Clean up any 'hairs'.
     */
    void nullNodes()
    {
      Segment v = this;
      do
        {
	  v.node = null;
	  v = v.next;
        }
      while (v != this);
    }

    /**
     * Transforms each segment in the closed path
     */
    void transformSegmentList(AffineTransform at)
    {
      Segment v = this;
      do
        {
	  v.transform(at);
	  v = v.next;
        }
      while (v != this);
    }

    /**
     * Determines the winding direction of the path
     * By the sign of the area.
     */
    boolean hasClockwiseOrientation()
    {
      return (getSignedArea() > 0.0);
    }

    /**
     * Returns the bounds of this path
     */
    public Rectangle2D getPathBounds()
    {
      double xmin;
      double xmax;
      double ymin;
      double ymax;
      xmin = xmax = P1.getX();
      ymin = ymax = P1.getY();

      Segment v = this;
      do
        {
	  Rectangle2D r = v.getBounds();
	  xmin = Math.min(r.getMinX(), xmin);
	  ymin = Math.min(r.getMinY(), ymin);
	  xmax = Math.max(r.getMaxX(), xmax);
	  ymax = Math.max(r.getMaxY(), ymax);
	  v = v.next;
        }
      while (v != this);

      return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
    }

    /**
     * Calculates twice the signed area of the path;
     */
    double getSignedArea()
    {
      Segment s;
      double area = 0.0;

      s = this;
      do
        {
	  area += s.curveArea();

	  area += s.P1.getX() * s.next.P1.getY()
	  - s.P1.getY() * s.next.P1.getX();
	  s = s.next;
        }