Algorithm
Development Kit 1.0

algs.model.kdtree
Class VerticalNode

java.lang.Object
  extended by algs.model.kdtree.TwoDNode
      extended by algs.model.kdtree.VerticalNode

public class VerticalNode
extends TwoDNode

Represents a node in the 2D-tree that partitions the space by means of a vertical line at the given x-coordinate.

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

Ancestors via the left son are those points which are to the left of the point represented by this node. Ancestors via the right son are those points which are to the right of the point represented by this node.

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

Field Summary
 
Fields inherited from class algs.model.kdtree.TwoDNode
coord, point
 
Constructor Summary
VerticalNode(IPoint point)
          X-coordinate is taken from the IPoint.
 
Method Summary
 TwoDNode construct(IPoint value)
          This method constructs the node of the appropriate class based upon the vertical property of this node.
protected  boolean inAboveRange(IRectangle r)
          Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.
protected  boolean inBelowRange(IRectangle r)
          Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.
 boolean isBelow(IPoint point)
          Returns whether the point is below the line represented by this node.
 boolean isVertical()
          Determines whether node splits plane vertically
protected  void split(TwoDNode child, boolean above)
          Manipulates child node's region accordingly, based on our own.
 
Methods inherited from class algs.model.kdtree.TwoDNode
getAbove, getBelow, getRegion, search, search, setAbove, setBelow, specialUpdateRectangle, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

VerticalNode

public VerticalNode(IPoint point)
X-coordinate is taken from the IPoint.

Parameters:
point - Point being stored.
Method Detail

isVertical

public boolean isVertical()
Description copied from class: TwoDNode
Determines whether node splits plane vertically

Specified by:
isVertical in class TwoDNode
Returns:
true if this node represents a VerticalNode in the TwoDTree; false otherwise.
See Also:
TwoDNode.isVertical()

construct

public 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.

Specified by:
construct in class TwoDNode
Parameters:
value - IPoint object to be stored with the constructed node
Returns:
Horizontal node to be the next level in the TwoD tree.

split

protected void split(TwoDNode child,
                     boolean above)
Description copied from class: TwoDNode
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.

Specified by:
split in class TwoDNode
Parameters:
child - child node to be affected by split
above - Determines whether to return left- or bottom- side
See Also:
TwoDNode.split(TwoDNode, boolean)

inBelowRange

protected boolean inBelowRange(IRectangle r)
Description copied from class: TwoDNode
Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.

Specified by:
inBelowRange in class TwoDNode
Parameters:
r - query rectangle
See Also:
TwoDNode.inBelowRange(IRectangle)

inAboveRange

protected boolean inAboveRange(IRectangle r)
Description copied from class: TwoDNode
Helper method for search algorithm, implemented in the Horizontal and Vertical subclasses.

Specified by:
inAboveRange in class TwoDNode
Parameters:
r - query rectangle
See Also:
TwoDNode.inAboveRange(IRectangle)

isBelow

public boolean isBelow(IPoint point)
Description copied from class: TwoDNode
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.

Specified by:
isBelow in class TwoDNode
Returns:
true if point is "below" us, based upon our direction
See Also:
TwoDNode.isBelow(IPoint)

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.