area.java

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

/* Area.java -- represents a shape built by constructive area geometry
   Copyright (C) 2002, 2004 Free Software Foundation

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */

package java.awt.geom;

import java.awt.Rectangle;
import java.awt.Shape;
import java.util.Vector;


/**
 * The Area class represents any area for the purpose of
 * Constructive Area Geometry (CAG) manipulations. CAG manipulations
 * work as an area-wise form of boolean logic, where the basic operations are:
 * <P><li>Add (in boolean algebra: A <B>or</B> B)<BR>
 * <li>Subtract (in boolean algebra: A <B>and</B> (<B>not</B> B) )<BR>
 * <li>Intersect (in boolean algebra: A <B>and</B> B)<BR>
 * <li>Exclusive Or <BR>
 * <img src="doc-files/Area-1.png" width="342" height="302"
 * alt="Illustration of CAG operations" /><BR>
 * Above is an illustration of the CAG operations on two ring shapes.<P>
 *
 * The contains and intersects() methods are also more accurate than the
 * specification of #Shape requires.<P>
 *
 * Please note that constructing an Area can be slow
 * (Self-intersection resolving is proportional to the square of
 * the number of segments).<P>
 * @see #add(Area)
 * @see #subtract(Area)
 * @see #intersect(Area)
 * @see #exclusiveOr(Area)
 *
 * @author Sven de Marothy ([e-mail])
 *
 * @since 1.2
 * @status Works, but could be faster and more reliable.
 */
public class Area implements Shape, Cloneable
{
  /**
   * General numerical precision
   */
  private static final double EPSILON = 1E-11;

  /**
   * recursive subdivision epsilon - (see getRecursionDepth)
   */
  private static final double RS_EPSILON = 1E-13;

  /**
   * Snap distance - points within this distance are considered equal
   */
  private static final double PE_EPSILON = 1E-11;

  /**
   * Segment vectors containing solid areas and holes
   * This is package-private to avoid an accessor method.
   */
  Vector solids;

  /**
   * Segment vectors containing solid areas and holes
   * This is package-private to avoid an accessor method.
   */
  Vector holes;

  /**
   * Vector (temporary) storing curve-curve intersections
   */
  private Vector cc_intersections;

  /**
   * Winding rule WIND_NON_ZERO used, after construction,
   * this is irrelevant.
   */
  private int windingRule;

  /**
   * Constructs an empty Area
   */
  public Area()
  {
    solids = new Vector();
    holes = new Vector();
  }

  /**
   * Constructs an Area from any given Shape. <P>
   *
   * If the Shape is self-intersecting, the created Area will consist
   * of non-self-intersecting subpaths, and any inner paths which
   * are found redundant in accordance with the Shape's winding rule
   * will not be included.
   * 
   * @param s  the shape (<code>null</code> not permitted).
   * 
   * @throws NullPointerException if <code>s</code> is <code>null</code>.
   */
  public Area(Shape s)
  {
    this();

    Vector p = makeSegment(s);

    // empty path
    if (p == null)
      return;

    // delete empty paths
    for (int i = 0; i < p.size(); i++)
      if (((Segment) p.elementAt(i)).getSignedArea() == 0.0)
	p.remove(i--);

    /*
     * Resolve self intersecting paths into non-intersecting
     * solids and holes.
     * Algorithm is as follows:
     * 1: Create nodes at all self intersections
     * 2: Put all segments into a list
     * 3: Grab a segment, follow it, change direction at each node,
     *    removing segments from the list in the process
     * 4: Repeat (3) until no segments remain in the list
     * 5: Remove redundant paths and sort into solids and holes
     */
    Vector paths = new Vector();
    Segment v;

    for (int i = 0; i < p.size(); i++)
      {
	Segment path = (Segment) p.elementAt(i);
	createNodesSelf(path);
      }

    if (p.size() > 1)
      {
	for (int i = 0; i < p.size() - 1; i++)
	  for (int j = i + 1; j < p.size(); j++)
	    {
	      Segment path1 = (Segment) p.elementAt(i);
	      Segment path2 = (Segment) p.elementAt(j);
	      createNodes(path1, path2);
	    }
      }

    // we have intersecting points.
    Vector segments = new Vector();

    for (int i = 0; i < p.size(); i++)
      {
	Segment path = v = (Segment) p.elementAt(i);
	do
	  {
	    segments.add(v);
	    v = v.next;
	  }
	while (v != path);
      }

    paths = weilerAtherton(segments);
    deleteRedundantPaths(paths);
  }

  /**
   * Performs an add (union) operation on this area with another Area.<BR>
   * @param area - the area to be unioned with this one
   */
  public void add(Area area)
  {
    if (equals(area))
      return;
    if (area.isEmpty())
      return;

    Area B = (Area) area.clone();

    Vector pathA = new Vector();
    Vector pathB = new Vector();
    pathA.addAll(solids);
    pathA.addAll(holes);
    pathB.addAll(B.solids);
    pathB.addAll(B.holes);

    int nNodes = 0;

    for (int i = 0; i < pathA.size(); i++)
      {
	Segment a = (Segment) pathA.elementAt(i);
	for (int j = 0; j < pathB.size(); j++)
	  {
	    Segment b = (Segment) pathB.elementAt(j);
	    nNodes += createNodes(a, b);
	  }
      }

    Vector paths = new Vector();
    Segment v;

    // we have intersecting points.
    Vector segments = new Vector();

    // In a union operation, we keep all
    // segments of A oustide B and all B outside A
    for (int i = 0; i < pathA.size(); i++)
      {
	v = (Segment) pathA.elementAt(i);
	Segment path = v;
	do
	  {
	    if (v.isSegmentOutside(area))
	      segments.add(v);
	    v = v.next;
	  }
	while (v != path);
      }

    for (int i = 0; i < pathB.size(); i++)
      {
	v = (Segment) pathB.elementAt(i);
	Segment path = v;
	do
	  {
	    if (v.isSegmentOutside(this))
	      segments.add(v);
	    v = v.next;
	  }
	while (v != path);
      }

    paths = weilerAtherton(segments);
    deleteRedundantPaths(paths);
  }

  /**
   * Performs a subtraction operation on this Area.<BR>
   * @param area the area to be subtracted from this area.
   * @throws NullPointerException if <code>area</code> is <code>null</code>.
   */
  public void subtract(Area area)
  {
    if (isEmpty() || area.isEmpty())
      return;

    if (equals(area))
      {
	reset();
	return;
      }

    Vector pathA = new Vector();
    Area B = (Area) area.clone();
    pathA.addAll(solids);
    pathA.addAll(holes);

    // reverse the directions of B paths.
    setDirection(B.holes, true);
    setDirection(B.solids, false);

    Vector pathB = new Vector();
    pathB.addAll(B.solids);
    pathB.addAll(B.holes);

    int nNodes = 0;

    // create nodes
    for (int i = 0; i < pathA.size(); i++)
      {
	Segment a = (Segment) pathA.elementAt(i);
	for (int j = 0; j < pathB.size(); j++)
	  {
	    Segment b = (Segment) pathB.elementAt(j);
	    nNodes += createNodes(a, b);
	  }
      }

    Vector paths = new Vector();

    // we have intersecting points.
    Vector segments = new Vector();

    // In a subtraction operation, we keep all
    // segments of A oustide B and all B within A
    // We outsideness-test only one segment in each path
    // and the segments before and after any node
    for (int i = 0; i < pathA.size(); i++)
      {
	Segment v = (Segment) pathA.elementAt(i);
	Segment path = v;
	if (v.isSegmentOutside(area) && v.node == null)
	  segments.add(v);
	boolean node = false;
	do
	  {
	    if ((v.node != null || node))
	      {
		node = (v.node != null);
		if (v.isSegmentOutside(area))
		  segments.add(v);
	      }
	    v = v.next;
	  }
	while (v != path);
      }

    for (int i = 0; i < pathB.size(); i++)
      {
	Segment v = (Segment) pathB.elementAt(i);
	Segment path = v;
	if (! v.isSegmentOutside(this) && v.node == null)
	  segments.add(v);
	v = v.next;
	boolean node = false;
	do
	  {
	    if ((v.node != null || node))
	      {
		node = (v.node != null);
		if (! v.isSegmentOutside(this))
		  segments.add(v);
	      }
	    v = v.next;
	  }
	while (v != path);
      }

    paths = weilerAtherton(segments);
    deleteRedundantPaths(paths);
  }

  /**
   * Performs an intersection operation on this Area.<BR>
   * @param area - the area to be intersected with this area.
   * @throws NullPointerException if <code>area</code> is <code>null</code>.
   */
  public void intersect(Area area)
  {
    if (isEmpty() || area.isEmpty())
      {
	reset();
	return;
      }
    if (equals(area))
      return;

    Vector pathA = new Vector();
    Area B = (Area) area.clone();
    pathA.addAll(solids);
    pathA.addAll(holes);

    Vector pathB = new Vector();
    pathB.addAll(B.solids);
    pathB.addAll(B.holes);

    int nNodes = 0;

    // create nodes
    for (int i = 0; i < pathA.size(); i++)
      {
	Segment a = (Segment) pathA.elementAt(i);
	for (int j = 0; j < pathB.size(); j++)
	  {
	    Segment b = (Segment) pathB.elementAt(j);
	    nNodes += createNodes(a, b);
	  }
      }

    Vector paths = new Vector();

    // we have intersecting points.
    Vector segments = new Vector();

    // In an intersection operation, we keep all
    // segments of A within B and all B within A
    // (The rest must be redundant)
    // We outsideness-test only one segment in each path
    // and the segments before and after any node
    for (int i = 0; i < pathA.size(); i++)
      {
	Segment v = (Segment) pathA.elementAt(i);
	Segment path = v;
	if (! v.isSegmentOutside(area) && v.node == null)
	  segments.add(v);
	boolean node = false;
	do
	  {
	    if ((v.node != null || node))
	      {
		node = (v.node != null);
		if (! v.isSegmentOutside(area))
		  segments.add(v);
	      }
	    v = v.next;
	  }
	while (v != path);
      }

    for (int i = 0; i < pathB.size(); i++)
      {
	Segment v = (Segment) pathB.elementAt(i);
	Segment path = v;
	if (! v.isSegmentOutside(this) && v.node == null)
	  segments.add(v);
	v = v.next;
	boolean node = false;
	do
	  {
	    if ((v.node != null || node))
	      {
		node = (v.node != null);
		if (! v.isSegmentOutside(this))
		  segments.add(v);
	      }
	    v = v.next;
	  }
	while (v != path);
      }

    paths = weilerAtherton(segments);
    deleteRedundantPaths(paths);
  }

  /**
   * Performs an exclusive-or operation on this Area.<BR>
   * @param area - the area to be XORed with this area.
   * @throws NullPointerException if <code>area</code> is <code>null</code>.
   */
  public void exclusiveOr(Area area)
  {
    if (area.isEmpty())
      return;

    if (isEmpty())
      {
	Area B = (Area) area.clone();
	solids = B.solids;
	holes = B.holes;
	return;
      }
    if (equals(area))
      {
	reset();
	return;
      }

    Vector pathA = new Vector();

    Area B = (Area) area.clone();
    Vector pathB = new Vector();
    pathA.addAll(solids);
    pathA.addAll(holes);

    // reverse the directions of B paths.
    setDirection(B.holes, true);
    setDirection(B.solids, false);
    pathB.addAll(B.solids);
    pathB.addAll(B.holes);

    int nNodes = 0;

    for (int i = 0; i < pathA.size(); i++)
      {
	Segment a = (Segment) pathA.elementAt(i);
	for (int j = 0; j < pathB.size(); j++)
	  {
	    Segment b = (Segment) pathB.elementAt(j);
	    nNodes += createNodes(a, b);
	  }
      }

    Vector paths = new Vector();
    Segment v;

    // we have intersecting points.
    Vector segments = new Vector();

    // In an XOR operation, we operate on all segments
    for (int i = 0; i < pathA.size(); i++)
      {
	v = (Segment) pathA.elementAt(i);
	Segment path = v;
	do
	  {
	    segments.add(v);
	    v = v.next;
	  }
	while (v != path);
      }

    for (int i = 0; i < pathB.size(); i++)
      {
	v = (Segment) pathB.elementAt(i);
	Segment path = v;