org.jhotdraw.geom
Class QuadTree<T>

java.lang.Object
  extended by org.jhotdraw.geom.QuadTree<T>
All Implemented Interfaces:
java.io.Serializable

public class QuadTree<T>
extends java.lang.Object
implements java.io.Serializable

A QuadTree allows to quickly find an object on a two-dimensional space.

QuadTree recursively subdivides a space into four rectangles. Each node of a QuadTree subdivides the space covered by the rectangle of its parent node into four smaller rectangles covering the upper left, upper right, lower left and lower right quadrant of the parent rectangle.

Version:
$Id: QuadTree.java 717 2010-11-21 12:30:57Z rawcoder $
Author:
Werner Randelshofer
See Also:
Serialized Form

Nested Class Summary
private  class QuadTree.QuadNode
           
 
Field Summary
private  int maxCapacity
           
private  int maxOutside
           
private  int minSize
           
private  java.util.HashMap<T,java.awt.geom.Rectangle2D.Double> outside
           
private  QuadTree.QuadNode root
           
 
Constructor Summary
QuadTree()
          Creates a new instance.
QuadTree(java.awt.geom.Rectangle2D.Double bounds)
           
 
Method Summary
 void add(T o, java.awt.geom.Rectangle2D.Double bounds)
           
 java.util.Collection<T> findContains(java.awt.geom.Point2D.Double p)
           
 java.util.Collection<T> findInside(java.awt.geom.Rectangle2D.Double r)
           
 java.util.Collection<T> findIntersects(java.awt.geom.Rectangle2D.Double r)
           
 java.util.Collection<T> findIntersects(java.awt.geom.Rectangle2D r)
           
 void remove(T o)
           
 void reorganize()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

outside

private java.util.HashMap<T,java.awt.geom.Rectangle2D.Double> outside

root

private QuadTree.QuadNode root

maxCapacity

private int maxCapacity

minSize

private int minSize

maxOutside

private int maxOutside
Constructor Detail

QuadTree

public QuadTree()
Creates a new instance.


QuadTree

public QuadTree(java.awt.geom.Rectangle2D.Double bounds)
Method Detail

add

public void add(T o,
                java.awt.geom.Rectangle2D.Double bounds)

reorganize

public void reorganize()

remove

public void remove(T o)

findContains

public java.util.Collection<T> findContains(java.awt.geom.Point2D.Double p)

findIntersects

public java.util.Collection<T> findIntersects(java.awt.geom.Rectangle2D r)

findIntersects

public java.util.Collection<T> findIntersects(java.awt.geom.Rectangle2D.Double r)

findInside

public java.util.Collection<T> findInside(java.awt.geom.Rectangle2D.Double r)