pt.lsts.neptus.data

Class KDTree

java.lang.Object

pt.lsts.neptus.data.KDTree

public class KDTree
extends java.lang.Object

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:

• Two different keys containing identical numbers should retrieve the same value from a given KD-tree. Therefore keys are cloned when a node is inserted.
  
  
• As with Hashtables, values inserted into a KD-tree are not cloned. Modifying a value between insertion and retrieval will therefore modify the value stored in the tree.

Since:

JDK1.2

Version:

%I%, %G%

Author:

Simon Levy, Bjoern Heckel

Constructor Summary

Constructors

Constructor and Description
KDTree(int k) Creates a KD-tree with specified number of dimensions.

Method Summary

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()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

KDTree

public KDTree(int k)

Creates a KD-tree with specified number of dimensions.

Parameters:

k - number of dimensions

Method Detail

insert

public void insert(double[] key,
                   java.lang.Object value)

Insert a node in a KD-tree. Uses algorithm translated from 352.ins.c of

   @Book{GonnetBaezaYates1991,                                   
     author =    {G.H. Gonnet and R. Baeza-Yates},
     title =     {Handbook of Algorithms and Data Structures},
     publisher = {Addison-Wesley},
     year =      {1991}
   }
 

Parameters:

key - key for KD-tree node

value - value at that key

Throws:

KeySizeException - if key.length mismatches K

KeyDuplicateException - if key already in tree

search

public java.lang.Object search(double[] key)

Find KD-tree node whose key is identical to key. Uses algorithm translated from 352.srch.c of Gonnet & Baeza-Yates.

Parameters:

key - key for KD-tree node

Returns:

object at key, or null if not found

Throws:

KeySizeException - if key.length mismatches K

delete

public void delete(double[] key)

Delete a node from a KD-tree. Instead of actually deleting node and rebuilding tree, marks node as deleted. Hence, it is up to the caller to rebuild the tree as needed for efficiency.

Parameters:

key - key for KD-tree node

Throws:

KeySizeException - if key.length mismatches K

KeyMissingException - if no node in tree has key

nearest

public java.lang.Object nearest(double[] key)

Find KD-tree node whose key is nearest neighbor to key. Implements the Nearest Neighbor algorithm (Table 6.4) of

 @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}
 }
 

Parameters:

key - key for KD-tree node

Returns:

object at node nearest to key, or null on failure

Throws:

KeySizeException - if key.length mismatches K

nearest

public java.lang.Object[] nearest(double[] key,
                                  int n)

Find KD-tree nodes whose keys are n nearest neighbors to key. Uses algorithm above. Neighbors are returned in ascending order of distance to key.

Parameters:

key - key for KD-tree node

n - how many neighbors to find

Returns:

objects at node nearest to key, or null on failure

Throws:

KeySizeException - if key.length mismatches K

java.lang.IllegalArgumentException - if n is negative or exceeds tree size

nearestNPoints

public java.util.Vector<Pair<double[],java.lang.Object>> nearestNPoints(double[] key,
                                                                        int n)

rangePoints

public java.util.Vector<Pair<double[],java.lang.Object>> rangePoints(double[] lowk,
                                                                     double[] uppk)

range

public java.lang.Object[] range(double[] lowk,
                                double[] uppk)

Range search in a KD-tree. Uses algorithm translated from 352.range.c of Gonnet & Baeza-Yates.

Parameters:

lowk - lower-bounds for key

uppk - upper-bounds for key

Returns:

array of Objects whose keys fall in range [lowk,uppk]

Throws:

KeySizeException - on mismatch among lowk.length, uppk.length, or K

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object