|
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.TwoDTree
public class TwoDTree
Standard unbalanced 2-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).
This data structure offers no remove functionality.
Note that the example above is for Double values; the node values stored could be of any type that implements Comparable.
Constructor Summary | |
---|---|
TwoDTree()
|
Method Summary | |
---|---|
VerticalNode |
getRoot()
Return the root of the TwoDTree, which is guaranteed to be a Vertical Node. |
void |
insert(IPoint value)
Insert the value into its proper location. |
IPoint |
nearest(IPoint target)
Find the nearest point in the TwoDtree to the given point. |
TwoDNode |
parent(IPoint value)
Return the parent of the point IF the point were to be inserted into the 2d-tree. |
java.util.ArrayList<IPoint> |
search(IRectangle space)
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 visit those nodes via the given visitor. |
void |
setRoot(VerticalNode node)
Set the root of the TwoDTree. |
java.lang.String |
toString()
Reasonable toString to aid debugging. |
void |
updateRectangles()
Propagate all rectangles down to leaves. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public TwoDTree()
Method Detail |
---|
public void insert(IPoint value)
value
- non-null value to be added into the tree.
java.lang.IllegalArgumentException
- if value is nullpublic VerticalNode getRoot()
public TwoDNode parent(IPoint value)
public void setRoot(VerticalNode node)
Use with Caution! One issue that may cause problems is when the new root does not have 'boundless' space associated with it.
Note that @see updateRectangles()
should always be called after
invoking this function, to ensure rectangles are all properly computed.
public IPoint nearest(IPoint target)
Only returns null if the tree was initially empty or if the target is null. Otherwise, must return some point that belongs to the tree.
target
- point which serves as focus of the search.public java.util.ArrayList<IPoint> search(IRectangle space)
space
- non-null rectangular region within which to search.
ArrayList
of IPoint
objects found within the space.
java.lang.NullPointerException
- if space or visitor is null.public void search(IRectangle space, IVisitTwoDNode visitor)
space
- non-null space within which search occurs.visitor
- non-null IVisitTwoDNode
visitor.
java.lang.NullPointerException
- if space or visitor is null.public java.lang.String toString()
toString
in class java.lang.Object
public void updateRectangles()
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |