org.simbrain.util.projection

Class NTree

java.lang.Object

org.simbrain.util.projection.NTree

All Implemented Interfaces:

java.lang.Iterable<DataPoint>

public class NTree
extends java.lang.Object
implements java.lang.Iterable<DataPoint>

An n-dimensional generalization of a simple QuadTree structure. This is a binary tree that splits elements based on successive dimensions, repeating as necessary. There are two types of nodes in the structure, branches and leaves. The leaf nodes are a n-dimensional 'space' that contains a number of elements. When an element is added that increases the number of points in that leaf beyond the threshold specified by MAX, the leaf is split into two new leaves attached to a new branch that replaces the old leaf. In splitting a leaf, a mid-point is determined which places approximately half of the points from the old leaf elements in each new leaf.

In searching for an element, the mid-point of each branch is used to determine the path through the tree. When the point to be searched is closer than the given tolerance to the midpoint, the other branch is also followed for correctness.

A couple of other standard collections are used to provide efficient index-based access and for reverse lookups of leafs.

Author:

James Matthew Watson - July 2, 2007

Field Summary

Fields

Modifier and Type	Field and Description
int	dimensions The number of dimensions this structure supports
(package private) static int	MAX The number of elements to allow in a leaf before splitting

Constructor Summary

Constructors

Constructor and Description
NTree(int dimensions) Constructs an NTree with the given number of dimensions.

Method Summary

Modifier and Type	Method and Description
DataPoint	add(DataPoint point) Adds a point to the set.
void	addAll(NTree other) adds all the elements from the given tree to this tree
java.util.ArrayList<DataPoint>	asArrayList() returns the tree as an arraylist.
DataPoint	get(int index)
DataPoint	getClosestPoint(DataPoint point) Returns the closest point in the tree to the given point.
java.util.List<DataPoint>	getClosestPoints(int number, DataPoint point) Gets the closest points to the passed in point.
static double	getDistance(DataPoint a, DataPoint b) Determines the Euclidean distance between two points.
int	getIndex(DataPoint point) Returns the index for the given point.
DataPoint	isUnique(DataPoint point, double tolerance) Checks whether the given point already exists in the tree with the specified tolerance.
java.util.Iterator<DataPoint>	iterator() Returns an iterator over this tree
void	set(int index, DataPoint point) replaces the point at the given index with the one provided.
int	size() Returns 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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

MAX

static final int MAX

The number of elements to allow in a leaf before splitting

See Also:

Constant Field Values

dimensions

public final int dimensions

The number of dimensions this structure supports

Constructor Detail

NTree

public NTree(int dimensions)

Constructs an NTree with the given number of dimensions.

Parameters:

dimensions - the number of dimensions

Method Detail

size

public int size()

Returns the number of points in the tree.

Returns:

the number of points in the tree

add

public DataPoint add(DataPoint point)

Adds a point to the set.

Parameters:

point - the point to add

Returns:

get

public DataPoint get(int index)

Parameters:

index - of element to return.

Returns:

Array of element at index location

isUnique

public DataPoint isUnique(DataPoint point,
                          double tolerance)

Checks whether the given point already exists in the tree with the specified tolerance.

Parameters:

point - the point to search for

tolerance - the tolerance for determining uniqueness

Returns:

the matching datapoint if it exists, null if the datapoint is unique

getDistance

public static double getDistance(DataPoint a,
                                 DataPoint b)

Determines the Euclidean distance between two points.

Parameters:

a - First point of distance

b - Second point of distance

Returns:

the Euclidean distance between points 1 and 2

getClosestPoints

public java.util.List<DataPoint> getClosestPoints(int number,
                                                  DataPoint point)

Gets the closest points to the passed in point. The amount of points to determine is specified by the number argument

Parameters:

number - the number of points to collect

point - the point to find points close to

Returns:

the closest points

getClosestPoint

public DataPoint getClosestPoint(DataPoint point)

Returns the closest point in the tree to the given point.

Parameters:

point -

Returns:

the point closest to the given point

getIndex

public int getIndex(DataPoint point)

Returns the index for the given point.

Parameters:

point - the point to lookup

Returns:

the index of that point

asArrayList

public java.util.ArrayList<DataPoint> asArrayList()

returns the tree as an arraylist. This returned list is ordered by index

Returns:

the tree as an arraylist

addAll

public void addAll(NTree other)

adds all the elements from the given tree to this tree

Parameters:

other - the other tree

iterator

public java.util.Iterator<DataPoint> iterator()

Returns an iterator over this tree

Specified by:

iterator in interface java.lang.Iterable<DataPoint>

Returns:

set

public void set(int index,
                DataPoint point)

replaces the point at the given index with the one provided.

Parameters:

index - the index to set the point at

point - the point to set