|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--edu.wlu.cs.levy.CG.KDTree
KDTree is a class supporting KD-tree insertion, deletion, equality search, range search, and nearest neighbor(s) using double-precision floating-point keys. Splitting dimension is chosen naively, by depth modulo K. Semantics are as follows:
Constructor Summary | |
KDTree(int k)
Creates a KD-tree with specified number of dimensions. |
Method Summary | |
void |
delete(double[] key)
Delete a node from a KD-tree. |
void |
insert(double[] key,
java.lang.Object value)
Insert a node in a KD-tree. |
java.lang.Object |
nearest(double[] key)
Find KD-tree node whose key is nearest neighbor to key. |
java.lang.Object[] |
nearest(double[] key,
int n)
Find KD-tree nodes whose keys are n nearest neighbors to key. |
java.lang.Object[] |
range(double[] lowk,
double[] uppk)
Range search in a KD-tree. |
java.lang.Object |
search(double[] key)
Find KD-tree node whose key is identical to key. |
java.lang.String |
toString()
|
Methods inherited from class java.lang.Object |
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
public KDTree(int k)
k
- number of dimensionsMethod Detail |
public void insert(double[] key, java.lang.Object value) throws KeySizeException, KeyDuplicateException
@Book{GonnetBaezaYates1991, author = {G.H. Gonnet and R. Baeza-Yates}, title = {Handbook of Algorithms and Data Structures}, publisher = {Addison-Wesley}, year = {1991} }
key
- key for KD-tree nodevalue
- value at that key
KeySizeException
- if key.length mismatches K
KeyDuplicateException
- if key already in treepublic java.lang.Object search(double[] key) throws KeySizeException
key
- key for KD-tree node
KeySizeException
- if key.length mismatches Kpublic void delete(double[] key) throws KeySizeException, edu.wlu.cs.levy.CG.KeyMissingException
key
- key for KD-tree node
KeySizeException
- if key.length mismatches K
KeyMissingException
- if no node in tree has keypublic java.lang.Object nearest(double[] key) throws KeySizeException
@techreport{AndrewMooreNearestNeighbor, author = {Andrew Moore}, title = {An introductory tutorial on kd-trees}, institution = {Robotics Institute, Carnegie Mellon University}, year = {1991}, number = {Technical Report No. 209, Computer Laboratory, University of Cambridge}, address = {Pittsburgh, PA} }
key
- key for KD-tree node
KeySizeException
- if key.length mismatches Kpublic java.lang.Object[] nearest(double[] key, int n) throws KeySizeException, java.lang.IllegalArgumentException
key
- key for KD-tree noden
- how many neighbors to find
KeySizeException
- if key.length mismatches K
java.lang.IllegalArgumentException
- if n is negative or
exceeds tree sizepublic java.lang.Object[] range(double[] lowk, double[] uppk) throws KeySizeException
lowk
- lower-bounds for keyuppk
- upper-bounds for key
KeySizeException
- on mismatch among lowk.length, uppk.length, or Kpublic java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |