public class KDTree
extends java.lang.Object
Constructor and Description |
---|
KDTree(int k)
Creates a KD-tree with specified number of dimensions.
|
Modifier and Type | Method and Description |
---|---|
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.util.Vector<Pair<double[],java.lang.Object>> |
nearestNPoints(double[] key,
int n) |
java.lang.Object[] |
range(double[] lowk,
double[] uppk)
Range search in a KD-tree.
|
java.util.Vector<Pair<double[],java.lang.Object>> |
rangePoints(double[] lowk,
double[] uppk) |
java.lang.Object |
search(double[] key)
Find KD-tree node whose key is identical to key.
|
java.lang.String |
toString() |
public KDTree(int k)
k
- number of dimensionspublic void insert(double[] key, java.lang.Object value)
@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 keyKeySizeException
- if key.length mismatches KKeyDuplicateException
- if key already in treepublic java.lang.Object search(double[] key)
key
- key for KD-tree nodeKeySizeException
- if key.length mismatches Kpublic void delete(double[] key)
key
- key for KD-tree nodeKeySizeException
- if key.length mismatches KKeyMissingException
- if no node in tree has keypublic java.lang.Object nearest(double[] key)
@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 nodeKeySizeException
- if key.length mismatches Kpublic java.lang.Object[] nearest(double[] key, int n)
key
- key for KD-tree noden
- how many neighbors to findKeySizeException
- if key.length mismatches Kjava.lang.IllegalArgumentException
- if n is negative or exceeds tree sizepublic java.util.Vector<Pair<double[],java.lang.Object>> nearestNPoints(double[] key, int n)
public java.util.Vector<Pair<double[],java.lang.Object>> rangePoints(double[] lowk, double[] uppk)
public java.lang.Object[] range(double[] lowk, double[] uppk)
lowk
- lower-bounds for keyuppk
- upper-bounds for keyKeySizeException
- on mismatch among lowk.length, uppk.length, or Kpublic java.lang.String toString()
toString
in class java.lang.Object
Copyright © 2004-2014 FEUP-LSTS and Neptus developers. All Rights Reserved.