Algorithm
Development Kit 1.0

algs.model.kdtree
Class TwoDTree

java.lang.Object
  extended by algs.model.kdtree.TwoDTree

public class TwoDTree
extends java.lang.Object

Standard unbalanced 2-dimensional binary tree.

Stores a set of points against which one can execute 2-dimensional range queries against a rectangle D whose domain is defined by a rectangle D=[x1,x2] x [y1,y2]. Note that the rectangle could be infinite in none, one, or two of these dimensions by having any of its coordinates set to Double.NEGATIVE_INFINITY or Double.POSITIVE_INFINITY. A rectangle could be one-dimensional (if either x1==x2 or y1==y2) or zero-dimensional (if both x1==x2 and y1==y2).

This data structure offers no remove functionality.

Note that the example above is for Double values; the node values stored could be of any type that implements Comparable.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
TwoDTree()
           
 
Method Summary
 VerticalNode getRoot()
          Return the root of the TwoDTree, which is guaranteed to be a Vertical Node.
 void insert(IPoint value)
          Insert the value into its proper location.
 IPoint nearest(IPoint target)
          Find the nearest point in the TwoDtree to the given point.
 TwoDNode parent(IPoint value)
          Return the parent of the point IF the point were to be inserted into the 2d-tree.
 java.util.ArrayList<IPoint> search(IRectangle space)
          Locate all points within the TwoDTree that fall within the given rectangle.
 void search(IRectangle space, IVisitTwoDNode visitor)
          Locate all points within the TwoDTree that fall within the given rectangle and visit those nodes via the given visitor.
 void setRoot(VerticalNode node)
          Set the root of the TwoDTree.
 java.lang.String toString()
          Reasonable toString to aid debugging.
 void updateRectangles()
          Propagate all rectangles down to leaves.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

TwoDTree

public TwoDTree()
Method Detail

insert

public void insert(IPoint value)
Insert the value into its proper location. No balancing is performed.

Parameters:
value - non-null value to be added into the tree.
Throws:
java.lang.IllegalArgumentException - if value is null

getRoot

public VerticalNode getRoot()
Return the root of the TwoDTree, which is guaranteed to be a Vertical Node.


parent

public TwoDNode parent(IPoint value)
Return the parent of the point IF the point were to be inserted into the 2d-tree. Returns null only if the tree is empty to begin with (i.e., there are no parents). Note that you will have to inspect the dimension for the TwoNode to determine if this is a Below or an Above parent.


setRoot

public void setRoot(VerticalNode node)
Set the root of the TwoDTree.

Use with Caution! One issue that may cause problems is when the new root does not have 'boundless' space associated with it.

Note that @see updateRectangles() should always be called after invoking this function, to ensure rectangles are all properly computed.


nearest

public IPoint nearest(IPoint target)
Find the nearest point in the TwoDtree to the given point.

Only returns null if the tree was initially empty or if the target is null. Otherwise, must return some point that belongs to the tree.

Parameters:
target - point which serves as focus of the search.

search

public java.util.ArrayList<IPoint> search(IRectangle space)
Locate all points within the TwoDTree that fall within the given rectangle.

Parameters:
space - non-null rectangular region within which to search.
Returns:
ArrayList of IPoint objects found within the space.
Throws:
java.lang.NullPointerException - if space or visitor is null.

search

public void search(IRectangle space,
                   IVisitTwoDNode visitor)
Locate all points within the TwoDTree that fall within the given rectangle and visit those nodes via the given visitor.

Parameters:
space - non-null space within which search occurs.
visitor - non-null IVisitTwoDNode visitor.
Throws:
java.lang.NullPointerException - if space or visitor is null.

toString

public java.lang.String toString()
Reasonable toString to aid debugging.

Overrides:
toString in class java.lang.Object

updateRectangles

public void updateRectangles()
Propagate all rectangles down to leaves.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.