|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.kdtree.DimensionalNode
public class DimensionalNode
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.
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 |
---|
public static int numDoubleRecursions
public static int numRecursions
public final IMultiPoint point
public final int dimension
public final int max
public final double coord
protected Hypercube region
protected DimensionalNode below
protected DimensionalNode above
Constructor Detail |
---|
public DimensionalNode(int dimension, IMultiPoint pt)
By default, region being managed is boundless on all dimensions.
dimension
- which dimension does this node representpt
- the multi-dimensional pointMethod Detail |
---|
public boolean isBoundless()
Will only be true for root node in KD-tree or newly instantiated nodes that have yet to be added to a KD tree.
public boolean isLeaf()
public DimensionalNode getBelow()
public IHypercube region()
public DimensionalNode getAbove()
public void setBelow(DimensionalNode node)
If setting to null, there is no knowledge of dimension coordinates.
node
- Next node to be inserted into the tree.public void setAbove(DimensionalNode node)
If setting to null, there is no knowledge of dimension coordinates.
node
- Next node to be inserted into the tree.public boolean isBelow(IMultiPoint pt)
Calculation assumes a multi-dimensional point being compared within the given dimension 'dimension'
pt
- Point being compared
protected DimensionalNode construct(IMultiPoint value)
In short, this acts as a factory for the nodes in the next level of the tree.
value
- value to be inserted
protected double shorter(double[] rawTarget, double min)
rawTarget
- optimized double[] form of targetmin
- shortest distance so far.
protected IMultiPoint nearest(double[] rawTarget, double[] min)
If no descendant improves on the min[] result then null is returned.
min
- minimum distance found so farrawTarget
- the target in raw optimized form
public void search(IHypercube space, java.util.ArrayList<IMultiPoint> results)
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.
space
- non-null region within which search occurs.results
- non-null ArrayListjava.lang.NullPointerException
- if space is null or results is nullpublic void search(IHypercube space, IVisitKDNode visitor)
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.
space
- non-null space inside which search occurs.visitor
- visitor to perform computation on the node
java.lang.NullPointerException
- if space is null or visitor is null.public java.lang.String toString()
toString
in class java.lang.Object
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |