area.java

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

      while (s != this);

      return area;
    }

    /**
     * Reverses the orientation of the whole polygon
     */
    void reverseAll()
    {
      reverseCoords();
      Segment v = next;
      Segment former = this;
      while (v != this)
        {
	  v.reverseCoords();
	  Segment vnext = v.next;
	  v.next = former;
	  former = v;
	  v = vnext;
        }
      next = former;
    }

    /**
     * Inserts a Segment after this one
     */
    void insert(Segment v)
    {
      Segment n = next;
      next = v;
      v.next = n;
    }

    /**
     * Returns if this segment path is polygonal
     */
    boolean isPolygonal()
    {
      Segment v = this;
      do
        {
	  if (! (v instanceof LineSegment))
	    return false;
	  v = v.next;
        }
      while (v != this);
      return true;
    }

    /**
     * Clones this path
     */
    Segment cloneSegmentList() throws CloneNotSupportedException
    {
      Vector list = new Vector();
      Segment v = next;

      while (v != this)
        {
	  list.add(v);
	  v = v.next;
        }

      Segment clone = (Segment) this.clone();
      v = clone;
      for (int i = 0; i < list.size(); i++)
        {
	  clone.next = (Segment) ((Segment) list.elementAt(i)).clone();
	  clone = clone.next;
        }
      clone.next = v;
      return v;
    }

    /**
     * Creates a node between this segment and segment b
     * at the given intersection
     * @return the number of nodes created (0 or 1)
     */
    int createNode(Segment b, Intersection i)
    {
      Point2D p = i.p;
      if ((pointEquals(P1, p) || pointEquals(P2, p))
          && (pointEquals(b.P1, p) || pointEquals(b.P2, p)))
	return 0;

      subdivideInsert(i.ta);
      b.subdivideInsert(i.tb);

      // snap points
      b.P2 = b.next.P1 = P2 = next.P1 = i.p;

      node = b.next;
      b.node = next;
      return 1;
    }

    /**
     * Creates multiple nodes from a list of intersections,
     * This must be done in the order of ascending parameters,
     * and the parameters must be recalculated in accordance
     * with each split.
     * @return the number of nodes created
     */
    protected int createNodes(Segment b, Intersection[] x)
    {
      Vector v = new Vector();
      for (int i = 0; i < x.length; i++)
        {
	  Point2D p = x[i].p;
	  if (! ((pointEquals(P1, p) || pointEquals(P2, p))
	      && (pointEquals(b.P1, p) || pointEquals(b.P2, p))))
	    v.add(x[i]);
        }

      int nNodes = v.size();
      Intersection[] A = new Intersection[nNodes];
      Intersection[] B = new Intersection[nNodes];
      for (int i = 0; i < nNodes; i++)
	A[i] = B[i] = (Intersection) v.elementAt(i);

      // Create two lists sorted by the parameter
      // Bubble sort, OK I suppose, since the number of intersections
      // cannot be larger than 9 (cubic-cubic worst case) anyway
      for (int i = 0; i < nNodes - 1; i++)
        {
	  for (int j = i + 1; j < nNodes; j++)
	    {
	      if (A[i].ta > A[j].ta)
	        {
		  Intersection swap = A[i];
		  A[i] = A[j];
		  A[j] = swap;
	        }
	      if (B[i].tb > B[j].tb)
	        {
		  Intersection swap = B[i];
		  B[i] = B[j];
		  B[j] = swap;
	        }
	    }
        }
      // subdivide a
      Segment s = this;
      for (int i = 0; i < nNodes; i++)
        {
	  s.subdivideInsert(A[i].ta);

	  // renormalize the parameters
	  for (int j = i + 1; j < nNodes; j++)
	    A[j].ta = (A[j].ta - A[i].ta) / (1.0 - A[i].ta);

	  A[i].seg = s;
	  s = s.next;
        }

      // subdivide b, set nodes
      s = b;
      for (int i = 0; i < nNodes; i++)
        {
	  s.subdivideInsert(B[i].tb);

	  for (int j = i + 1; j < nNodes; j++)
	    B[j].tb = (B[j].tb - B[i].tb) / (1.0 - B[i].tb);

	  // set nodes
	  B[i].seg.node = s.next; // node a -> b 
	  s.node = B[i].seg.next; // node b -> a 

	  // snap points
	  B[i].seg.P2 = B[i].seg.next.P1 = s.P2 = s.next.P1 = B[i].p;
	  s = s.next;
        }
      return nNodes;
    }

    /**
     * Determines if two paths are equal.
     * Colinear line segments are ignored in the comparison.
     */
    boolean pathEquals(Segment B)
    {
      if (! getPathBounds().equals(B.getPathBounds()))
	return false;

      Segment startA = getTopLeft();
      Segment startB = B.getTopLeft();
      Segment a = startA;
      Segment b = startB;
      do
        {
	  if (! a.equals(b))
	    return false;

	  if (a instanceof LineSegment)
	    a = ((LineSegment) a).lastCoLinear();
	  if (b instanceof LineSegment)
	    b = ((LineSegment) b).lastCoLinear();

	  a = a.next;
	  b = b.next;
        }
      while (a != startA && b != startB);
      return true;
    }

    /**
     * Return the segment with the top-leftmost first point
     */
    Segment getTopLeft()
    {
      Segment v = this;
      Segment tl = this;
      do
        {
	  if (v.P1.getY() < tl.P1.getY())
	    tl = v;
	  else if (v.P1.getY() == tl.P1.getY())
	    {
	      if (v.P1.getX() < tl.P1.getX())
		tl = v;
	    }
	  v = v.next;
        }
      while (v != this);
      return tl;
    }

    /**
     * Returns if the path has a segment outside a shape
     */
    boolean isSegmentOutside(Shape shape)
    {
      return ! shape.contains(getMidPoint());
    }
  } // class Segment

  private class LineSegment extends Segment
  {
    public LineSegment(double x1, double y1, double x2, double y2)
    {
      super();
      P1 = new Point2D.Double(x1, y1);
      P2 = new Point2D.Double(x2, y2);
    }

    public LineSegment(Point2D p1, Point2D p2)
    {
      super();
      P1 = (Point2D) p1.clone();
      P2 = (Point2D) p2.clone();
    }

    /**
     * Clones this segment
     */
    public Object clone()
    {
      return new LineSegment(P1, P2);
    }

    /**
     * Transforms the segment
     */
    void transform(AffineTransform at)
    {
      P1 = at.transform(P1, null);
      P2 = at.transform(P2, null);
    }

    /**
     * Swap start and end points
     */
    void reverseCoords()
    {
      Point2D p = P1;
      P1 = P2;
      P2 = p;
    }

    /**
     * Returns the segment's midpoint
     */
    Point2D getMidPoint()
    {
      return (new Point2D.Double(0.5 * (P1.getX() + P2.getX()),
                                 0.5 * (P1.getY() + P2.getY())));
    }

    /**
     * Returns twice the area of a curve, relative the P1-P2 line
     * Obviously, a line does not enclose any area besides the line
     */
    double curveArea()
    {
      return 0;
    }

    /**
     * Returns the PathIterator type of a segment
     */
    int getType()
    {
      return (PathIterator.SEG_LINETO);
    }

    /**
     * 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]
     */
    void subdivideInsert(double t)
    {
      Point2D p = new Point2D.Double((P2.getX() - P1.getX()) * t + P1.getX(),
                                     (P2.getY() - P1.getY()) * t + P1.getY());
      insert(new LineSegment(p, P2));
      P2 = p;
      next.node = node;
      node = null;
    }

    /**
     * Determines if two line segments are strictly colinear
     */
    boolean isCoLinear(LineSegment b)
    {
      double x1 = P1.getX();
      double y1 = P1.getY();
      double x2 = P2.getX();
      double y2 = P2.getY();
      double x3 = b.P1.getX();
      double y3 = b.P1.getY();
      double x4 = b.P2.getX();
      double y4 = b.P2.getY();

      if ((y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3) != 0.0)
	return false;

      return ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3) == 0.0);
    }

    /**
     * Return the last segment colinear with this one.
     * Used in comparing paths.
     */
    Segment lastCoLinear()
    {
      Segment prev = this;
      Segment v = next;

      while (v instanceof LineSegment)
        {
	  if (isCoLinear((LineSegment) v))
	    {
	      prev = v;
	      v = v.next;
	    }
	  else
	    return prev;
        }
      return prev;
    }

    /**
     * Compare two segments.
     * We must take into account that the lines may be broken into colinear
     * subsegments and ignore them.
     */
    boolean equals(Segment b)
    {
      if (! (b instanceof LineSegment))
	return false;
      Point2D p1 = P1;
      Point2D p3 = b.P1;

      if (! p1.equals(p3))
	return false;

      Point2D p2 = lastCoLinear().P2;
      Point2D p4 = ((LineSegment) b).lastCoLinear().P2;
      return (p2.equals(p4));
    }

    /**
     * Returns a line segment
     */
    int pathIteratorFormat(double[] coords)
    {
      coords[0] = P2.getX();
      coords[1] = P2.getY();
      return (PathIterator.SEG_LINETO);
    }

    /**
     * Returns if the line has intersections.
     */
    boolean hasIntersections(Segment b)
    {
      if (b instanceof LineSegment)
	return (linesIntersect(this, (LineSegment) b) != null);

      if (b instanceof QuadSegment)
	return (lineQuadIntersect(this, (QuadSegment) b) != null);

      if (b instanceof CubicSegment)
	return (lineCubicIntersect(this, (CubicSegment) b) != null);

      return false;
    }

    /**
     * Splits intersections into nodes,
     * This one handles line-line, line-quadratic, line-cubic
     */
    int splitIntersections(Segment b)
    {
      if (b instanceof LineSegment)
        {
	  Intersection i = linesIntersect(this, (LineSegment) b);

	  if (i == null)
	    return 0;

	  return createNode(b, i);
        }

      Intersection[] x = null;

      if (b instanceof QuadSegment)
	x = lineQuadIntersect(this, (QuadSegment) b);

      if (b instanceof CubicSegment)
	x = lineCubicIntersect(this, (CubicSegment) b);

      if (x == null)
	return 0;

      if (x.length == 1)
	return createNode(b, (Intersection) x[0]);

      return createNodes(b, x);
    }

    /**
     * Returns the bounding box of this segment
     */
    Rectangle2D getBounds()
    {
      return (new Rectangle2D.Double(Math.min(P1.getX(), P2.getX()),
                                     Math.min(P1.getY(), P2.getY()),
                                     Math.abs(P1.getX() - P2.getX()),
                                     Math.abs(P1.getY() - P2.getY())));
    }

    /**
     * Returns the number of intersections on the positive X axis,
     * with the origin at (x,y), used for contains()-testing
     */
    int rayCrossing(double x, double y)
    {
      double x0 = P1.getX() - x;
      double y0 = P1.getY() - y;
      double x1 = P2.getX() - x;
      double y1 = P2.getY() - y;

      if (y0 * y1 > 0)
	return 0;

      if (x0 < 0 && x1 < 0)
	return 0;

      if (y0 == 0.0)
	y0 -= EPSILON;

      if (y1 == 0.0)
	y1 -= EPSILON;

      if (Line2D.linesIntersect(x0, y0, x1, y1, 
				EPSILON, 0.0, Double.MAX_VALUE, 0.0))
	return 1;
      return 0;
    }
  } // class LineSegment

  /**
   * Quadratic Bezier curve segment
   *
   * Note: Most peers don't support quadratics directly, so it might make
   * sense to represent them as cubics internally and just be done with it.
   * I think we should be peer-agnostic, however, and stay faithful to the
   * input geometry types as far as possible.
   */
  private class QuadSegment extends Segment
  {
    Point2D cp; // control point

    /**
     * Constructor, takes the coordinates of the start, control,
     * and end point, respectively.
     */
    QuadSegment(double x1, double y1, double cx, double cy, double x2,
                double y2)
    {
      super();
      P1 = new Point2D.Double(x1, y1);
      P2 = new Point2D.Double(x2, y2);
      cp = new Point2D.Double(cx, cy);
    }

    /**
     * Clones this segment
     */
    public Object clone()
    {
      return new QuadSegment(P1.getX(), P1.getY(), cp.getX(), cp.getY(),
                             P2.getX(), P2.getY());
    }

    /**
     * Returns twice the area of a curve, relative the P1-P2 line
     *
     * The area formula can be derived