maspack.geometry

Class KDTree<T>

java.lang.Object

maspack.geometry.KDTree<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

Nested Classes

Modifier and Type	Class and Description
static class	KDTree.KDNode<T> KD node associated with a node on a KD-Tree

Constructor Summary

Constructors

Constructor and Description
KDTree(int dim, java.util.List<T> list, KDComparator<T> comp) Default constructor.

Method Summary

Modifier and Type	Method and Description
boolean	contains(T value) Checks if the tree contains the supplied value
T	nearestNeighbourSearch(T pnt, double tol) Nearest Neighbour search
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 - tolerance for located neighbors

Returns:

collection of T neighbors.

nearestNeighbourSearch

public T nearestNeighbourSearch(T pnt,
                                double tol)

Nearest Neighbour search

Parameters:

pnt - point to find neighbors of.

Returns:

nearest point