|
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.KDTree
public class KDTree
Standard unbalanced k-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).
Note that the example above is for Double values; the node values stored could be of any type that implements Comparable.
Original source derived from Bentley [1975]. http://portal.acm.org/citation.cfm?id=361007
Field Summary | |
---|---|
int |
maxDimension
Maximum dimension for this tree. |
Constructor Summary | |
---|---|
KDTree(int md)
Default KDTree constructor. |
Method Summary | |
---|---|
int |
count()
Helper method for testing. |
int |
getNumDoubleRecursion()
|
int |
getNumRecursion()
|
DimensionalNode |
getRoot()
Return the root of the KDTree. |
int |
height()
Helper method for testing. |
void |
insert(IMultiPoint value)
Insert the value into its proper location. |
IMultiPoint |
nearest(IMultiPoint target)
Find the nearest point in the KDtree to the given point. |
int |
nextDimension(DimensionalNode node)
Helper method to always determine the next dimensionality given a node. |
int |
nextDimension(int d)
Helper method to always determine the next dimensionality given an integer representing the specified dimension in the KDTree. |
DimensionalNode |
parent(IMultiPoint value)
Return the parent of the point IF the point were to be inserted into the kd-tree. |
void |
removeAll()
Empty the KDTree of all of its internal points. |
java.util.ArrayList<IMultiPoint> |
search(IHypercube space)
Locate all points within the KDTree that fall within the given IHypercube. |
void |
search(IHypercube space,
IVisitKDNode visitor)
Locate all points within the TwoDTree that fall within the given IHypercube and visit those nodes via the given visitor. |
void |
setRoot(DimensionalNode newRoot)
Set the root of the KDTree. |
java.lang.String |
toString()
Reasonable toString to aid debugging. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public final int maxDimension
Constructor Detail |
---|
public KDTree(int md)
md
- Maximum dimension of nodes within this tree.Method Detail |
---|
public int nextDimension(DimensionalNode node)
node
- returns dimension to use for children of this node.public int nextDimension(int d)
d
- returns dimension of children nodes for next dimension.public void removeAll()
public DimensionalNode parent(IMultiPoint value)
public void insert(IMultiPoint value)
No balancing is performed.
isBelow checks for strict less than. This means that (by default) equal coordinates are going to appear in above Subtree
value
- non-null value to be added into the tree.
java.lang.IllegalArgumentException
- if value is nullpublic DimensionalNode getRoot()
public void setRoot(DimensionalNode newRoot)
newRoot
- The desired node to be the root of the tree.public IMultiPoint nearest(IMultiPoint target)
Only returns null if the tree was initially empty. Otherwise, must return some point that belongs to the tree.
If tree is empty or if the target is null
then
null
is returned.
target
- the target of the search.public java.util.ArrayList<IMultiPoint> search(IHypercube space)
space
- non-null space in which to search
java.lang.NullPointerException
- if space is nullpublic void search(IHypercube space, IVisitKDNode visitor)
space
- non-null space within which to search.visitor
- non-null IVisitTwoDNode visitor that contains behavior to process at
each discovered point within the space.
java.lang.NullPointerException
- if space or visitor is nullpublic java.lang.String toString()
toString
in class java.lang.Object
public int count()
public int height()
public int getNumRecursion()
public int getNumDoubleRecursion()
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |