Algorithm
Development Kit 1.0

algs.model.kdtree
Class TwoDNode

java.lang.Object
  extended by algs.model.kdtree.TwoDNode
Direct Known Subclasses:
HorizontalNode, VerticalNode

public abstract class TwoDNode
extends java.lang.Object

Represents the base class of a node in the TwoD tree.

This class is intended as a simpler, optimized implementation of DimensionalNode for two dimensional KD trees.

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

Field Summary
 double coord
          Coordinate.
 IPoint point
          Store the point.
 
Constructor Summary
TwoDNode(double coord, IPoint point)
          Stores the coordinate value to be used for dividing the plane either vertically or horizontally
 
Method Summary
abstract  TwoDNode construct(IPoint value)
          This method constructs the node of the appropriate class based upon the vertical property of this node.
 TwoDNode getAbove()
          Return node "Above" this one.
 TwoDNode getBelow()
          Return node "Below" this one.
 IRectangle getRegion()
          Return region associated with this node.
protected abstract  boolean inAboveRange(IRectangle r)
          Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.
protected abstract  boolean inBelowRange(IRectangle r)
          Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.
abstract  boolean isBelow(IPoint point)
          Returns whether the point is below the line represented by this node.
abstract  boolean isVertical()
          Determines whether node splits plane vertically
 void search(IRectangle space, java.util.ArrayList<IPoint> results)
          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 use given visitor as the computation to perform on that node.
 void setAbove(TwoDNode node)
          Set node "Above" this one.
 void setBelow(TwoDNode node)
          Set the node "Below" this one.
protected  void specialUpdateRectangle()
          Called once the node has its region properly set, and it must propagate to children (if they exist) in below and above.
protected abstract  void split(TwoDNode child, boolean above)
          Manipulates child node's region accordingly, based on our own.
 java.lang.String toString()
          Reasonable toString method.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

coord

public final double coord
Coordinate.


point

public final IPoint point
Store the point.

Constructor Detail

TwoDNode

public TwoDNode(double coord,
                IPoint point)
Stores the coordinate value to be used for dividing the plane either vertically or horizontally

Note the initial region associated with this TwoDNode object is unbounded and will only be set properly when it is added into the tree.

Parameters:
coord - coordinate value to be used for dividing plane
point - the IPoint object from which coordinate is derived.
Method Detail

getBelow

public TwoDNode getBelow()
Return node "Below" this one.


getAbove

public TwoDNode getAbove()
Return node "Above" this one.


getRegion

public IRectangle getRegion()
Return region associated with this node.


setBelow

public void setBelow(TwoDNode node)
Set the node "Below" this one.

Let subclass deal with updating region.

Parameters:
node - new node to be properly set.

setAbove

public void setAbove(TwoDNode node)
Set node "Above" this one.

Let subclass deal with updating region.

Parameters:
node - new node to be properly set.

isVertical

public abstract boolean isVertical()
Determines whether node splits plane vertically

Returns:
true if this node represents a VerticalNode in the TwoDTree; false otherwise.

isBelow

public abstract boolean isBelow(IPoint point)
Returns whether the point is below the line represented by this node.

For vertical nodes, below is clear. For horizontal nodes, a true value for below is interpreted as being left.

Parameters:
point -
Returns:
true if point is "below" us, based upon our direction

split

protected abstract void split(TwoDNode child,
                              boolean above)
Manipulates child node's region accordingly, based on our own.

For VerticalNode, below is clear. For HorizontalNode, a true value for below is interpreted as being left.

Parameters:
child - child node to be affected by split
above - Determines whether to return left- or bottom- side

construct

public abstract TwoDNode construct(IPoint value)
This method constructs the node of the appropriate class based upon the vertical property of this node.

In short, this acts as a factory for the nodes in the next level of the tree.

Parameters:
value - point to be inserted.
Returns:
appropriate TwoDNode subclass (either VerticalNode or HorizontalNode)

search

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

Parameters:
space - non-null region within which search occurs.
results - non-null ArrayList into which located points are inserted.
Throws:
java.lang.NullPointerException - if space is null or results is null

search

public void search(IRectangle space,
                   IVisitTwoDNode visitor)
Locate all points within the TwoDTree that fall within the given rectangle and use given visitor as the computation to perform on that node.

Parameters:
space - non-null space within which search is to be conducted.
visitor - visitor to perform computation on the node
Throws:
NullPointer - if value is null or visitor is null.

inBelowRange

protected abstract boolean inBelowRange(IRectangle r)
Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.

Parameters:
r - query rectangle

inAboveRange

protected abstract boolean inAboveRange(IRectangle r)
Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.

Parameters:
r - query rectangle

specialUpdateRectangle

protected void specialUpdateRectangle()
Called once the node has its region properly set, and it must propagate to children (if they exist) in below and above.


toString

public java.lang.String toString()
Reasonable toString method.

Overrides:
toString in class java.lang.Object

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.