drasys.or.geom
Class KDTree

java.lang.Object
  |
  +--drasys.or.geom.KDTree

public class KDTree

extends java.lang.Object

implements PointIndexI

A K-Dimensional Tree implementation of a point index.

References:

Introduction to Algorithms
    Thomas H. Cormen, et al / Hardcover / Published 1990

Constructor Summary

KDTree()           The first key added to the index will determine the coordinate system and dimensionality for the KDTree.

KDTree(PriorityQueueI priorityQueue)           The first key added to the index will determine the coordinate system and dimensionality for the KDTree.

 

Method Summary
CoordinateSystemI	coordinateSystem()           Returns the coordinate system that the index is using.
java.util.Enumeration	elements()           Returns an enumeration to access all the elements in random order.
java.lang.Object	get(PointI point)           Returns an element with an exact key match.
PairI	getNearestNeighborTo(PointI point)           Returns the element with the nearest key.
void	put(PointI key, java.lang.Object value)           Put a new element into the index.
RangeI	range()           Returns the range of points in the index.
void	removeAllElements()           Removes all of the elements from the index.
java.util.Enumeration	selectedElements()           Returns an enumeration to access the selected elements in random order.
int	selectNearestNeighbors(PointI point, int n)           Select the 'n' elements whose keys are closest to 'point'.
int	selectRange(RangeI range)           Select the elements whose keys are in the range.
void	setCoordinateSystem(CoordinateSystemI coordinateSystem)           Sets the coordinate system for the index after first removing all the elements.
int	size()           Returns the number of elements selected in the index.
int	sizeOfSelected()           Returns the number of elements selected in the index.
boolean	supportsDuplicateKeys()           Returns true if the index can contain duplicate keys.

 

Methods inherited from class java.lang.Object

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

 

Constructor Detail

KDTree

public KDTree()

The first key added to the index will determine the coordinate system and dimensionality for the KDTree. All of the keys have to be from the same coordinate system. The default priority queue will be 'PriorityQueue'.

KDTree

public KDTree(PriorityQueueI priorityQueue)

The first key added to the index will determine the coordinate system and dimensionality for the KDTree. All of the keys have to be from the same coordinate system. The priority queue will be set to 'priorityQueue' and the compare object will be set to 'CompareNumber'.

size

public int size()

Returns the number of elements selected in the index.

Specified by:

size in interface PointIndexI

sizeOfSelected

public int sizeOfSelected()

Returns the number of elements selected in the index.

Specified by:

sizeOfSelected in interface PointIndexI

removeAllElements

public void removeAllElements()

Removes all of the elements from the index.

Specified by:

removeAllElements in interface PointIndexI

range

public RangeI range()

Returns the range of points in the index.

Specified by:

range in interface PointIndexI

setCoordinateSystem

public void setCoordinateSystem(CoordinateSystemI coordinateSystem)

Sets the coordinate system for the index after first removing all the elements. If the coordinate system is not set when the first element is added, it will be set to the coordinate system of the key.

Specified by:

setCoordinateSystem in interface PointIndexI

Returns:

'null' if the index is not set.

coordinateSystem

public CoordinateSystemI coordinateSystem()

Returns the coordinate system that the index is using.

Specified by:

coordinateSystem in interface PointIndexI

Returns:

'null' if the coordinate system is not set.

supportsDuplicateKeys

public boolean supportsDuplicateKeys()

Returns true if the index can contain duplicate keys.

Specified by:

supportsDuplicateKeys in interface PointIndexI

get

public java.lang.Object get(PointI point)

Returns an element with an exact key match.

Specified by:

get in interface PointIndexI

Throws:

CorruptedException - If the internal data structure is corrupted.

getNearestNeighborTo

public PairI getNearestNeighborTo(PointI point)

Returns the element with the nearest key. Compares the distance proxy for all elements.

Specified by:

getNearestNeighborTo in interface PointIndexI

Returns:

A PairI interface where PairI.getFirst() returns the key and PairI.getSecond()returns the value.

selectNearestNeighbors

public int selectNearestNeighbors(PointI point,
                                  int n)

Select the 'n' elements whose keys are closest to 'point'. A call to this method may invalidate previous selection enumerations. Compares the distance proxy for all elements.

Specified by:

selectNearestNeighbors in interface PointIndexI

Returns:

the number of elements selected.

elements

public java.util.Enumeration elements()

Returns an enumeration to access all the elements in random order.

Specified by:

elements in interface PointIndexI

Returns:

An enumeration of PairI interfaces where PairI.getFirst() returns the key and PairI.getSecond() returns the value.

selectedElements

public java.util.Enumeration selectedElements()

Returns an enumeration to access the selected elements in random order.

Specified by:

selectedElements in interface PointIndexI

Returns:

An enumeration of PairI interfaces where PairI.getFirst() returns the key and PairI.getSecond() returns the value.

put

public void put(PointI key,
                java.lang.Object value)

Put a new element into the index.

Specified by:

put in interface PointIndexI

Returns:

A PairI interface where PairI.getFirst() returns the key and PairI.getSecond() returns the value.

selectRange

public int selectRange(RangeI range)

Select the elements whose keys are in the range. A call to this method may invalidate previous selection enumerations. Calling this method may invalidate any previously returned enumerations.

Specified by:

selectRange in interface PointIndexI

Returns:

the number of elements selected.