|
|||||||||
| 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 dimensions| Method 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 tree
public java.lang.Object search(double[] key)
throws KeySizeException
key - key for KD-tree node
KeySizeException - if key.length mismatches K
public 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 key
public 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 K
public 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 size
public 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 | ||||||||