maspack.geometry
Class KDTree<T>

java.lang.Object
  extended by maspack.geometry.KDTree<T>
Type Parameters:
T -
Direct Known Subclasses:
KDTree3d

public class KDTree<T>
extends java.lang.Object

Generic KD-Tree utility, requires a KDComparator for computing distances between elements. Used for finding nearest M neighbours of a supplied point in log(N) time.

Author:
Antonio

Nested Class Summary
static class KDTree.KDNode<T>
          KD node associated with a node on a KD-Tree
 
Constructor Summary
KDTree(int dim, java.util.List<T> list, KDComparator<T> comp)
          Default constructor.
 
Method Summary
 boolean contains(T value)
          Checks if the tree contains the supplied value
 java.util.ArrayList<T> nearestNeighbourSearch(T pnt, int K, double tol)
          K Nearest Neighbour search
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

KDTree

public KDTree(int dim,
              java.util.List<T> list,
              KDComparator<T> comp)
Default constructor. Creates a KD-Tree structure for a given dimension, list of points, and comparator

Method Detail

contains

public boolean contains(T value)
Checks if the tree contains the supplied value


nearestNeighbourSearch

public java.util.ArrayList<T> nearestNeighbourSearch(T pnt,
                                                     int K,
                                                     double tol)
K Nearest Neighbour search

Parameters:
pnt - point to find neighbors of.
K - Number of neighbors to retrieve. Can return more than K, if last nodes are equal distances.
tol - tolerence for located neighbors
Returns:
collection of T neighbors.