Algorithm
Development Kit 1.0

algs.model.kdtree
Class DimensionalNode

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

public class DimensionalNode
extends java.lang.Object

Represents a node in the KD-tree that partitions the space by means of a plane that splits the hyperspace into an "above" and a "below" based upon orientation.

Ancestors via the above son are those points which are "above" of the point represented by this node. Ancestors via the below son are those points which are "below" of the point represented by this node.

Each dimensional node stores a Region for which it is responsible. Note that only the Root is boundless in all directions (i.e., [-INF, +INF, -INF, +INF]. Thereafter, child nodes are able to maintain their regions. When a dimensional node is inserted into the tree, its SPACE is properly updated based upon the parent, and dimension to which it is being added.

Because the original MultiPoint may have lots of dimensions, we store the values here for much faster access then simply accessing values through its methods.

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

Field Summary
protected  DimensionalNode above
          Node above this one.
protected  DimensionalNode below
          Node below this one.
 double coord
          Coordinate in this dimension from the multipoint.
 int dimension
          Which dimension is being represented (1 <= d <= max).
 int max
          Maximum dimension.
static int numDoubleRecursions
           
static int numRecursions
           
 IMultiPoint point
          Dimensional-coordinate.
protected  Hypercube region
          Region for which we are "responsible"
 
Constructor Summary
DimensionalNode(int dimension, IMultiPoint pt)
          Dimensional-coordinate is passed in as the value, together with its dimension.
 
Method Summary
protected  DimensionalNode construct(IMultiPoint value)
          This method constructs the node of the appropriate class based upon the dimensional property of this node.
 DimensionalNode getAbove()
          Return node "Above" this one.
 DimensionalNode getBelow()
          Return node "Below" this one.
 boolean isBelow(IMultiPoint pt)
          Returns whether the point is below the line represented by this node.
 boolean isBoundless()
          Determine if node has a boundless region associated with it.
 boolean isLeaf()
          Determines if node is a leaf node (i.e., has no children).
protected  IMultiPoint nearest(double[] rawTarget, double[] min)
          In sub-tree rooted at node, see if one of its descendants is closer to rawTarget than min[0].
 IHypercube region()
          Return region being managed.
 void search(IHypercube space, java.util.ArrayList<IMultiPoint> results)
          Locate all points within the KDTree that fall within the given hypercube.
 void search(IHypercube space, IVisitKDNode visitor)
          Locate all points within the KDTree that fall within the given hyperspace and use given visitor as the computation to perform on that node.
 void setAbove(DimensionalNode node)
          Set the node "Above" this one.
 void setBelow(DimensionalNode node)
          Set the node "Below" this one.
protected  double shorter(double[] rawTarget, double min)
          Given the target in optimized form, determine if node is closer than min.
 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

numDoubleRecursions

public static int numDoubleRecursions

numRecursions

public static int numRecursions

point

public final IMultiPoint point
Dimensional-coordinate.


dimension

public final int dimension
Which dimension is being represented (1 <= d <= max).


max

public final int max
Maximum dimension.


coord

public final double coord
Coordinate in this dimension from the multipoint.


region

protected Hypercube region
Region for which we are "responsible"


below

protected DimensionalNode below
Node below this one.


above

protected DimensionalNode above
Node above this one.

Constructor Detail

DimensionalNode

public DimensionalNode(int dimension,
                       IMultiPoint pt)
Dimensional-coordinate is passed in as the value, together with its dimension.

By default, region being managed is boundless on all dimensions.

Parameters:
dimension - which dimension does this node represent
pt - the multi-dimensional point
Method Detail

isBoundless

public boolean isBoundless()
Determine if node has a boundless region associated with it.

Will only be true for root node in KD-tree or newly instantiated nodes that have yet to be added to a KD tree.


isLeaf

public boolean isLeaf()
Determines if node is a leaf node (i.e., has no children).


getBelow

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


region

public IHypercube region()
Return region being managed.


getAbove

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


setBelow

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

If setting to null, there is no knowledge of dimension coordinates.

Parameters:
node - Next node to be inserted into the tree.

setAbove

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

If setting to null, there is no knowledge of dimension coordinates.

Parameters:
node - Next node to be inserted into the tree.

isBelow

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

Calculation assumes a multi-dimensional point being compared within the given dimension 'dimension'

Parameters:
pt - Point being compared
Returns:
true if pt is "below" us in our dimension

construct

protected DimensionalNode construct(IMultiPoint value)
This method constructs the node of the appropriate class based upon the dimensional property of this node.

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

Parameters:
value - value to be inserted
Returns:
appropriate node whose dimensionality is next in line.

shorter

protected double shorter(double[] rawTarget,
                         double min)
Given the target in optimized form, determine if node is closer than min.

Parameters:
rawTarget - optimized double[] form of target
min - shortest distance so far.
Returns:
-1 if not closer; otherwise returns a number [0, min) if closer.

nearest

protected IMultiPoint nearest(double[] rawTarget,
                              double[] min)
In sub-tree rooted at node, see if one of its descendants is closer to rawTarget than min[0].

If no descendant improves on the min[] result then null is returned.

Parameters:
min - minimum distance found so far
rawTarget - the target in raw optimized form
Returns:
existing point in tree that is closest.

search

public void search(IHypercube space,
                   java.util.ArrayList<IMultiPoint> results)
Locate all points within the KDTree that fall within the given hypercube.

Speedup occurs when an entire range is found to exist within the target space, thus all points in the subtree rooted here can be drained and added.

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(IHypercube space,
                   IVisitKDNode visitor)
Locate all points within the KDTree that fall within the given hyperspace and use given visitor as the computation to perform on that node.

Speedup occurs when an entire range is found to exist within the target space, thus all points in the subtree rooted here can be added.

If we are a leaf, then report the point if it is contained within space. Perhaps our region is wholly contained within space. If so, then we can safely add self and all points from our left and right subtrees. Otherwise, we have to do some computation to see whether we go down left and/or right subtrees.

Parameters:
space - non-null space inside which search occurs.
visitor - visitor to perform computation on the node
Throws:
java.lang.NullPointerException - if space is null or visitor is null.

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.