ags.utils.dataStructures.trees.secondGenKD
Class KdTree<T>

java.lang.Object
  ags.utils.dataStructures.trees.secondGenKD.KdTree<T>

Direct Known Subclasses:

KdTree.ChildNode, KdTree.Manhattan, KdTree.SqrEuclid, KdTree.WeightedManhattan, KdTree.WeightedSqrEuclid

public abstract class KdTree<T>
extends Object

An efficient well-optimized kd-tree

Nested Class Summary

private class	KdTree.ChildNode Internal class for child nodes
static class	KdTree.DataPoint<T> A location point and it's value (used for storage of the tree model)
static class	KdTree.Entry<T> Stores a distance and value to output
static class	KdTree.Manhattan<T> Class for tree with Manhattan distancing
private static class	KdTree.ResultHeap Class for tracking up to 'size' closest values
static class	KdTree.SqrEuclid<T> Class for tree with Unweighted Squared Euclidean distancing
private static class	KdTree.Status Enumeration representing the status of a node during the running
static class	KdTree.WeightedManhattan<T> Class for tree with Weighted Manhattan distancing
static class	KdTree.WeightedSqrEuclid<T> Class for tree with Weighted Squared Euclidean distancing

Field Summary

private static int	bucketSize
private Object[]	data
private int	dimensions
private KdTree<T>	left
private int	locationCount
private double[][]	locations
private LinkedList<double[]>	locationStack
private double[]	maxLimit
private double[]	minLimit
private KdTree<T>	parent
private KdTree<T>	right
private boolean	singularity
private Integer	sizeLimit
private int	splitDimension
private double	splitValue
private KdTree.Status	status

Constructor Summary

protected	KdTree(int dimensions, Integer sizeLimit) Construct a RTree with a given number of dimensions and a limit on maxiumum size (after which it throws away old points)
private	KdTree(KdTree<T> parent, boolean right) Constructor for child nodes.

Method Summary

void	addPoint(double[] location, T value) Add a point and associated value to the tree
private void	extendBounds(double[] location) Extends the bounds of this node do include a new location
private int	findWidestAxis() Find the widest axis of the bounds of this node
protected double	getAxisWeightHint(int i)
List<KdTree.DataPoint<T>>	getDataPoints() Traverses the tree and stores all data points in a list.
List<KdTree.Entry<T>>	nearestNeighbor(double[] location, int count, boolean sequentialSorting) Calculates the nearest 'count' points to 'location'
protected abstract double	pointDist(double[] p1, double[] p2)
protected abstract double	pointRegionDist(double[] point, double[] min, double[] max)
private void	removeOld() Remove the oldest value from the tree.
int	size() Get the number of points in the tree

Methods inherited from class java.lang.Object

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

Field Detail

bucketSize

private static final int bucketSize

See Also:

Constant Field Values

dimensions

private final int dimensions

parent

private final KdTree<T> parent

locationStack

private final LinkedList<double[]> locationStack

sizeLimit

private final Integer sizeLimit

locations

private double[][] locations

data

private Object[] data

locationCount

private int locationCount

left

private KdTree<T> left

right

private KdTree<T> right

splitDimension

private int splitDimension

splitValue

private double splitValue

minLimit

private double[] minLimit

maxLimit

private double[] maxLimit

singularity

private boolean singularity

status

private KdTree.Status status

Constructor Detail

KdTree

protected KdTree(int dimensions,
                 Integer sizeLimit)

Construct a RTree with a given number of dimensions and a limit on maxiumum size (after which it throws away old points)

KdTree

private KdTree(KdTree<T> parent,
               boolean right)

Constructor for child nodes. Internal use only.

Method Detail

size

public int size()

Get the number of points in the tree

addPoint

public void addPoint(double[] location,
                     T value)

Add a point and associated value to the tree

extendBounds

private final void extendBounds(double[] location)

Extends the bounds of this node do include a new location

findWidestAxis

private final int findWidestAxis()

Find the widest axis of the bounds of this node

removeOld

private void removeOld()

Remove the oldest value from the tree. Note: This cannot trim the bounds of nodes, nor empty nodes, and thus you can't expect it to perfectly preserve the speed of the tree as you keep adding.

nearestNeighbor

public List<KdTree.Entry<T>> nearestNeighbor(double[] location,
                                             int count,
                                             boolean sequentialSorting)

Calculates the nearest 'count' points to 'location'

pointDist

protected abstract double pointDist(double[] p1,
                                    double[] p2)

pointRegionDist

protected abstract double pointRegionDist(double[] point,
                                          double[] min,
                                          double[] max)

getAxisWeightHint

protected double getAxisWeightHint(int i)

getDataPoints

public final List<KdTree.DataPoint<T>> getDataPoints()

Traverses the tree and stores all data points in a list.