rect.java

移动对象空间数据库中索引r树源码,能在eclipse下直接运行.

//Rect.java
//  
//This library is free software; you can redistribute it and/or
//modify it under the terms of the GNU Lesser General Public
//License as published by the Free Software Foundation; either
//version 2.1 of the License, or (at your option) any later version.
//  
//This library 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
//Lesser General Public License for more details.
package rtree;
import java.awt.Rectangle;

/**
   It is very easy to extend this program to n dimensions. Here every thing is 
   hard coaded for 2 dim. To convert to more than 2 dim. :-
   <br>make the point class to hold the required dimensions.(keep an array of 
   dimensions)
   <br>The rect class needs the four points directly, instead of that make it to
   accept Point as its argument in the constructor.
   <br>Then on deal with the point class directly instead of the four points 
   directly.
   <p>The methods of relational topology(equals,contains etc.) are from various
   papers by <b>D. Papadias</b> and mainly from Modeling Topological Spatial 
   Relation: Strategies for Query Processing.- <b>Egenhofer</b>
   <br>The methods are nothing but set theories.
   <p>In GIS there can be many types of combinations of the topological relations.
   The theories of these combinations are given in the above said papers. If 
   required this class can be improved for those conditions.
   @author Prachuryya Barua
*/
//TODO: Apply the isNull considerations.
//      Take the common procedures in overloaded methods to one method.
public class Rect implements java.io.Serializable
{
  private int minX=0,minY=0,maxX=0,maxY=0;
  boolean isNull = false;
  public Rect()
  {
    initNull();
  }
  
  public Rect(int topX,int topY,int botX, int botY)
    throws IllegalValueException
  {
    if((topX > botX) || (topY > botY)){
      System.out.println("\ttopX:"+topX+"\ttopY:"+topY+"\tbotX:"+botX+"\tbotY:"+botY);
      throw new IllegalValueException("rtree.Rect.Rect: wrong order of params.");
    }
    init(topX,topY,botX,botY);
  }
  Rect(Rect rect)
    throws IllegalValueException
  {
    if(rect == null)
      throw new IllegalValueException("rtree.Rect.Rect: Param is null.");
    if(rect.isNull()){
      initNull();
    }
    else
      init(rect.getMinX(), rect.getMinY(), rect.getMaxX(), rect.getMaxY());
  }
  private void initNull()
  {
    minX = 0;
    minY = 0;
    maxX = -1;
    maxY = -1;
    isNull = true;
  }
  private void init(int minX, int minY, int maxX, int maxY)
  {
    this.minX = minX;
    this.minY = minY;
    this.maxX = maxX;
    this.maxY = maxY;
    isNull = false;
  }
  /*
    If you want to make the constructor take Point, then....
    Point minP,maxP;
    Rect(int minX,int minY,int botX, int botY)
    throws IllegalValueException
    {
    if((minX > maxX) || (minY > maxY))
    throw new IllegalValueException("rtree.Rect.Rect: "
    +"minP > maxP ?");
    minP = new Point(minX,minY);
    maxP = new Point(maxX,maxY);
    }
    Rect(Point minP,Point maxP)
    throws IllgalValueException
    {
    if((minP == null) || (maxP == null))
    throw new IllegalValueException("rtree.Rect.Rect: "
    +"Either of the point are null");
    if((minP.getX() > maxP.getX()) || (minP.getY() > maxP.getY()))
    throw new IllegalValueException("rtree.Rect.Rect: "
    +"minP > maxP?");
    this.minP = (Point)minP.clone();
    this.maxP = (Point)maxP.clone();
    }
  */
  public boolean isNull()
  {
    return isNull;
    //if(minX == 0 && minY == 0 && maxX == -1 && maxY == -1)
    //return true;
    //else
    //return false;
  }
  public static int sizeInBytes()
  {
    return(Node.INTEGER_SIZE*4);//depends upon the points
  }
  public int getArea()
  {
    if(isNull())
      return 0;
    return((maxX-minX)*(maxY-minY));
  }
  public int getWidth()
  {
    if(isNull())
      return 0;
    return(Math.abs(maxX - minX));
  }
  public int getHeight()
  {
    if(isNull())
      return 0;
    return(Math.abs(maxY - minY));
  }
  public int getMinX()
  {
    return(minX);
  }
  public int getMinY()
  {
    return(minY);
  }
  public int getMaxX()
  {
    return(maxX);
  }
  public int getMaxY()
  {
    return(maxY);
  }
  /**
     Include the given Rectangle.
  */
  public void expandToInclude(Rect rect)
  {
    if(rect == null || rect.isNull())
      return;
    
    if(this.isNull()){
      init(rect.getMinX(),rect.getMinY(), rect.getMaxX(), rect.getMaxY());
      return;
    }
    minX = Math.min(rect.getMinX(),minX);//minX
    minY = Math.min(rect.getMinY(),minY);//minY
    maxX = Math.max(rect.getMaxX(),maxX);//maxX
    maxY = Math.max(rect.getMaxY(),maxY);//maxY
  }
  /**
     return the minimum bounding rectangle of this rectangle and the passed
     rectangle.
  */
  public Rect getResultingMBR(Rect rectangle)
    throws IllegalValueException
  {
    if(rectangle == null)
      throw new IllegalValueException("rtree.Rect.getResultingMBR : Rect is null");
    if(rectangle.isNull())
      if(this.isNull())
        return new Rect();
      else
        return new Rect(this);
    else//rectangle is not null
      if(this.isNull())
        return rectangle;
    //if nobody is "isNull"
    int topX,topY,botX,botY;
    topX = Math.min(rectangle.getMinX(),minX);//minX
    topY = Math.min(rectangle.getMinY(),minY);//minY
    botX = Math.max(rectangle.getMaxX(),maxX);//maxX
    botY = Math.max(rectangle.getMaxY(),maxY);//maxY
    return(new Rect(topX,topY,botX,botY));
  }
  /**
     Overloaded type of the previous function - but static
  */
  public static Rect getResultingMBR(Rect source, Rect dest)
    throws IllegalValueException
  {
    if((dest == null) || (source == null))
      throw new IllegalValueException("rtree.Rect.getResultingMBR : Rect is null");
    return source.getResultingMBR(dest);
  }
  /**
     Another overloaded version - but static
  */
  public static Rect getResultingMBR(Rect[] rects)
    throws IllegalValueException
  {
    if(rects.length <= 0)
      throw new IllegalValueException("rtree.Rect.getResultingMBR : "+
                                      "Array of rectangles are empty.");
    Rect result = rects[0];
    for(int i=1; i<rects.length; ++i)
      result = getResultingMBR(rects[i],result);
    return result;
  }
  /**
     Another overloaded version - but static
  */
  public static Rect getResultingMBR(Rect[] rects, Rect rect)
    throws IllegalValueException
  {
    Rect result = getResultingMBR(rects);
    result = getResultingMBR(rect,result);
    return result;
  }
  //--------------------------Topological methods---------------------------
  /**
     Checks if this rectangle contains 'rect'.
     <br>Checks the two minimal conditions from 'contains' matrix(Egenhofer.)
     <br>Correct for Point as well.
  */
  public boolean contains(Rect rect)
    throws IllegalValueException
  { 
    if(rect == null)
      throw new IllegalValueException("rtree.Rect.contains: null argument");
    boolean ret = true;
    //m12 = true && m22 = false
    //X dim.
    if((minX >= rect.getMinX()) || (maxX <= rect.getMaxX()))
      return false;
    //Y dim.
    if((minY >= rect.getMinY()) || (maxY <= rect.getMaxY()))
      return false;
    return ret;
  }
  /**
     The difference betn. this method and <code>contains</code> is that this method returns true
     even if the <code>covers</code> condition if true. 
     @return true if this rectangle completely encloses 'rect'.
  */
    
  public boolean encloses(Rect rect)
    throws IllegalValueException
  {
    if(rect == null)
      throw new IllegalValueException("rtree.Rect.overlaps: null argument");
    boolean ret = true;
    //X dim.
    if((minX > rect.getMinX()) || (maxX < rect.getMaxX()))
      return false;
    //Y dim.
    if((minY > rect.getMinY()) || (maxY < rect.getMaxY()))
      return false;
    return ret;
  }

  /**
     Check if this rectangle is contained by 'rect'
  */
  public boolean containedBy(Rect rect)
    throws IllegalValueException
  { 
    if(rect == null)
      throw new IllegalValueException("rtree.Rect.containedBy:null argument");
    boolean ret = true;
    //m21 = true && m22 = false
    //X dim.
    if((rect.getMinX() >= minX) || (rect.getMaxX() <= maxX))
      return false;
    //Y dim.