region.java

use Java code to draw on pad canvas

package no.geosoft.cc.geometry;



/**
 * A <em>Region</em> is simply an area, as the name implies, and is
 * implemented as a so called "y-x-banded" array of rectangles; Each Region
 * is made up of a certain number of rectangles sorted by y coordinate first,
 * and then by x coordinate.
 * <p>
 * Furthermore, the rectangles are banded such that every rectangle with a
 * given upper-left y coordinate (y1) will have the same lower-right y
 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band,
 * it will span the entire vertical distance of the band. This means that
 * some areas that could be merged into a taller rectangle will be represented
 * as several shorter rectangles to account for shorter rectangles to its
 * left or right but within its "vertical scope".
 * <p>
 * An added constraint on the rectangles is that they must cover as much
 * horizontal area as possible. E.g. no two rectangles in a band are allowed
 * to touch. Whenever possible, bands will be merged together to cover a
 * greater vertical distance (and thus reduce the number of rectangles).
 * Two bands can be merged only if the bottom of one touches the top of the
 * other and they have rectangles in the same places (of the same width, of
 * course). This maintains the y-x-banding.
 * <p>
 * Region operations includes add (union), subtract, intersect, and
 * exclusive-or.
 * <p>
 * This class corresponds to Region.c of the X11 distribution and the
 * implemntation is based on it.
 * <p>
 * The <em>Region</em> is essentially equivalent to an AWT <em>Area</em>
 * but with different back-end implementation. Becnhmarking proves it more
 * than 100 times faster than AWT Area for binary CAG operations,
 * <p>
 * Thanks to:
 * <ul>
 * <li>Bryan Lin @ China Minmetals Corporation - for identifying
 *     synchronization errors when run on the MS WindowsXP platform.
 * </ul>
 *
 * @author <a href="mailto:[e-mail]">Jacob Dreyer</a>
 */   
public class Region
  implements Cloneable
{
  private static final int OPERATION_UNION        = 0;
  private static final int OPERATION_INTERSECTION = 1;
  private static final int OPERATION_SUBTRACTION  = 2;
  private static final int OPERATION_XOR          = 3;      

  private static final int INITIAL_SIZE = 40; // 10 rectangles
  
  // Temporary working area common for all regions for maximum performance
  private static int       gRectangles_[] = new int[INITIAL_SIZE];
  private static int       gNRectangles_  = 0;
  private static boolean   isLocked_      = false;

  private Box              extent_;
  private int              rectangles_[]; // y0,y1,x0,x1,.....
  private int              nRectangles_;

  
  
  /**
   * Create an empty region. Corresponds to XCreateRegion of X11.
   */
  public Region()
  {
    extent_      = new Box (0, 0, 0, 0);
    rectangles_  = new int[INITIAL_SIZE];  
    nRectangles_ = 0;
  }

  
  
  /**
   * Create the region covering the (possibly complex) polygon specified
   * by the x and y parameters.
   * Corresponds to XPolygonRegion of X11.
   * 
   * @param x  X values of polygon vertices.
   * @param y  Y values of polygon vertices.
   */
  public Region (int x[], int y[])  
  {
    // TODO. See PolyReg.c of X11.
  }


  
  /**
   * Create a region constituting of a single rectangle as specified.
   * 
   * @param rectangle  Rectangle to create region from.
   */
  public Region (Rect rectangle)
  {
    this();
    set (rectangle);
  }
  

  
  /**
   * Create a region consisting of one rectangle as specified.
   * 
   * @param x       X position of upper left corner of rectangle.
   * @param y       Y position of upper left corner of rectangle.
   * @param width   Width of rectangle.
   * @param height  Height of rectangle.
   */
  public Region (int x, int y, int width, int height)
  {
    this (new Rect (x, y, width, height));
  }



  /**
   * Create a region consisting of one rectangle as specified.
   * 
   * @param box  Box specification of rectangle to create region from.
   */
  public Region (Box box)
  {
    this (new Rect (box));
  }
  
  

  /**
   * Create a region as a copy of the specified region.
   * 
   * @param region  Region to copy.
   */
  public Region (Region region)
  {
    extent_ = new Box();
    rectangles_ = new int[region.nRectangles_ << 2];
    set (region);
  }
  


  /**
   * Clone this region.
   * 
   * @return  Clone of this region.
   */
  public Object clone()
  {
    return new Region (this);
  }


  
  /**
   * Convert this region to an AWT Area.
   * <p>
   * Note: The AWT classes are referenced explicitly here rather tham
   * importing them to indicate that the Region implementation does not
   * dependent on the AWT.
   * 
   * @return  Area equivalent of this rectangle.
   */
  public java.awt.geom.Area createArea()
  {
    if (nRectangles_ == 0) return null;
    
    java.awt.Rectangle rectangle =
      new java.awt.Rectangle (rectangles_[2],
                              rectangles_[0],
                              rectangles_[3] - rectangles_[2],
                              rectangles_[1] - rectangles_[0]);
    java.awt.geom.Area area = new java.awt.geom.Area (rectangle);
    
    for (int i = 1; i < nRectangles_; i++) {
      int j = i * 4;
      rectangle = new java.awt.Rectangle (rectangles_[j+2],
                                          rectangles_[j+0],
                                          rectangles_[j+3] - rectangles_[j+2],
                                          rectangles_[j+1] - rectangles_[j+0]);
      
      area.add (new java.awt.geom.Area (rectangle));
    }

    return area;
  }


  
  private static void checkMemory (Region region, int nRectangles)
  {
    int nEntries = nRectangles << 2;

    if (region == null) {
      if (gRectangles_.length < nEntries) {
        int newSize = nEntries * 2;
        int newArray[] = new int[newSize];
        System.arraycopy (gRectangles_, 0, newArray, 0, gRectangles_.length);
        gRectangles_ = newArray;
      }
    }
    else {
      if (region.rectangles_.length < nEntries) {
        int newSize = nEntries * 2;
        int newArray[] = new int[newSize];
        System.arraycopy (region.rectangles_, 0, newArray, 0,
                          region.rectangles_.length);
        region.rectangles_ = newArray;
      }
    }
  }
  
  

  /**
   * Set the content of this region according to the specified
   * region.
   * 
   * @param region  Region to copy.
   */
  public void set (Region region)
  {
    extent_.copy (region.extent_);

    checkMemory (this, region.nRectangles_);

    System.arraycopy (region.rectangles_, 0,
                      rectangles_, 0, region.nRectangles_ << 2);

    nRectangles_ = region.nRectangles_;
  }


  
  /**
   * Set the content of this region according to the specified
   * rectangle.
   *
   * @param rectangle  Rectangle to set region according to.
   */
  public void set (Rect rectangle)
  {
    rectangles_ = new int[INITIAL_SIZE];      

    if (rectangle.isEmpty()) {
      extent_      = new Box();
      nRectangles_ = 0;
    }
    else {
      extent_ = new Box (rectangle);
      rectangles_[0] = extent_.y1;
      rectangles_[1] = extent_.y2;    
      rectangles_[2] = extent_.x1;
      rectangles_[3] = extent_.x2;    
      nRectangles_ = 1;
    }
  }
  
  

  /**
   * Clear the region.
   */
  public void clear()
  {
    nRectangles_ = 0;
    extent_.set (0, 0, 0, 0);
  }



  /**
   * Return true if this region equals the specified object.
   * Corrensponds to XEqualRegion of X11.
   * 
   * @param object  Object to check against.
   * @return        True if the two regions equals, false otherwise.
   * @throws        ClassCastException if object is not of type Region.
   */
  public boolean equals (Object object) 
  {
    Region region = (Region) object;
    
    if      (nRectangles_ != region.nRectangles_) return false;
    else if (nRectangles_ == 0)                   return true;
    else if (extent_.x1 != region.extent_.x1)     return false;
    else if (extent_.x2 != region.extent_.x2)     return false;
    else if (extent_.y1 != region.extent_.y1)     return false;
    else if (extent_.y2 != region.extent_.y2)     return false;
    else {
      for (int i = 0; i < nRectangles_ << 2; i++)
        if (rectangles_[i] != region.rectangles_[i]) return false;
    }
    
    return true;
  }
  
  

  /**
   * Return true if the region is empty. Corresponds to XEmptyRegion in X11.
   * 
   * @return  True if the region is empty, false otherwise.
   */
  public boolean isEmpty()
  {
    return nRectangles_ == 0;
  }
  


  /**
   * Offset the entire region a specified distance.
   * Corresponds to XOffsetRegion in X11.
   * 
   * @param dx  Offset in x direction.
   * @param dy  Offset in y direction.
   */
  public void offset (int dx, int dy)
  {
    for (int i = 0; i < rectangles_.length; i+=4) {
      rectangles_[i+0] += dy;
      rectangles_[i+1] += dy;      
      rectangles_[i+2] += dx;
      rectangles_[i+3] += dx;      
    }

    extent_.offset (dx, dy);
  }

  

  /**
   * Return true if the specified region intersect this region.
   * 
   * @param region  Region to check against.
   * @return        True if the region intersects this one, false otherwise.
   */
  public boolean isIntersecting (Region region)
  {
    Region r = (Region) clone();
    r.intersect (region);
    return !r.isEmpty();
  }



  /**
   * Return true if the specified rectangle intersect this region.   
   * 
   * @param rectangle  Rectangle to check against.
   * @return           True if the rectangle intersects this, false otherwise.
   */
  public boolean isIntersecting (Rect rectangle)
  {
    Region region = new Region (rectangle);
    return isIntersecting (region);
  }



  /**
   * Return true if the specified point is inside this region.
   * This method corresponds to XPointInRegion in X11.
   * 
   * @param x  X part of point to check.
   * @param y  Y part of point to check.
   * @return   True if the point is inside the region, false otherwise.
   */
  public boolean isInside (int x, int y)
  {
    if (isEmpty())
      return false;
    
    if (!extent_.isInside (x, y))
      return false;

    int rEnd = nRectangles_ << 2;
    
    // Find correct band
    int i = 0;
    while (i < rEnd && rectangles_[i+1] < y) {
      if (rectangles_[i] > y) return false; // Passed the band
      i += 4;
    }

    // Check each rectangle in the band
    while (i < rEnd && rectangles_[i] <= y) {
      if (x >= rectangles_[i+2] && x < rectangles_[i+3]) return true;
      i += 4;
    }

    return false;
  }



  /**
   * Return true if the specified rectangle is inside this region.
   * This method corresponds to XRectInRegion in X11.   
   * 
   * @param rectangle  Rectangle to check.
   * @return           True if the rectangle is inside this region,
   *                   false otherwise.
   */
  public boolean isInside (Rect rectangle)
  {
    // Trivial reject case 1 
    if (isEmpty())
      return false;

    // Trivial reject case 2
    if (!extent_.isOverlapping (rectangle))
      return false;

    int x1 = rectangle.x;
    int x2 = rectangle.x + rectangle.width;
    int y1 = rectangle.y;
    int y2 = rectangle.y + rectangle.height;

    int rEnd = nRectangles_ << 2;
    
    // Find start band
    int i = 0;
    while (i < rEnd && rectangles_[i+1] < y1) {
      if (rectangles_[i] > y1) return false; // Passed the band
      i += 4;
    }

    while (i < rEnd) {
      int yTop = rectangles_[i];
    
      // Find start rectangle within band
      while (i < rEnd && rectangles_[i+3] <= x1) {
        if (rectangles_[i] > yTop) return false; // Passed the band
        i += 4;
      }
      
      if (i == rEnd) return false;
      
      // This rectangle must cover the entire rectangle horizontally
      if (x1 < rectangles_[i+2] || x2 > rectangles_[i+3]) return false;
      
      // See if we are done
      if (rectangles_[i+1] >= y2) return true;
      
      // Move to next band
      i += 4;
      while (i < rEnd && rectangles_[i] == yTop)
        i += 4;
    }

    return false;
  }
  

  
  /**
   * Return true if this region is inside of the specified rectangle.
   * 
   * @param rectangle  Rectangle to check if this is inside of.
   * @return           True if this region is inside the specified rectangle,
   *                   false otherwise.
   */
  public boolean isInsideOf (Rect rectangle)
  {
    return subtract (this, rectangle).isEmpty();
  }

  

  /**
   * Return the extent of the region.
   * Correspond to XClipBox in X11.
   * 
   * @return  The extent of this region.
   */
  public Rect getExtent()
  {
    return new Rect (extent_);
  }



  /**
   * Return the number of rectangles in the region. In case the number
   * is getting very high, the application might choose to call collapse().
   *
   * @return  Number of rectangles this region consists of.
   */
  public int getNRectangles()
  {
    return nRectangles_;
  }
  
  

  /**