com.revolsys.jts.index.kdtree

Class KdTree

java.lang.Object

com.revolsys.jts.index.kdtree.KdTree

public class KdTree
extends Object

An implementation of a 2-D KD-Tree. KD-trees provide fast range searching on point data.

This implementation supports detecting and snapping points which are closer than a given tolerance value. If the same point (up to tolerance) is inserted more than once a new node is not created but the count of the existing node is incremented.

Author:

David Skea, Martin Davis

Constructor Summary

Constructors

Constructor and Description
KdTree() Creates a new instance of a KdTree with a snapping tolerance of 0.0.
KdTree(double tolerance) Creates a new instance of a KdTree, specifying a snapping distance tolerance.

Method Summary

Methods

Modifier and Type	Method and Description
KdNode	insert(Point p) Inserts a new point in the kd-tree, with no data.
KdNode	insert(Point p, Object data) Inserts a new point into the kd-tree.
boolean	isEmpty() Tests whether the index contains any items.
List	query(BoundingBox queryEnv) Performs a range search of the points in the index.
void	query(BoundingBox queryEnv, List result) Performs a range search of the points in the index.

Methods inherited from class java.lang.Object

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

Constructor Detail

KdTree

public KdTree()

Creates a new instance of a KdTree with a snapping tolerance of 0.0. (I.e. distinct points will not be snapped)

KdTree

public KdTree(double tolerance)

Creates a new instance of a KdTree, specifying a snapping distance tolerance. Point which lie closer than the tolerance to a point already in the tree will be treated as identical to the existing point.

Parameters:

tolerance - the tolerance distance for considering two points equal

Method Detail

insert

public KdNode insert(Point p)

Inserts a new point in the kd-tree, with no data.

Parameters:

p - the point to insert

Returns:

the kdnode containing the point

insert

public KdNode insert(Point p,
            Object data)

Inserts a new point into the kd-tree.

Parameters:

p - the point to insert

data - a data item for the point

Returns:

returns a new KdNode if a new point is inserted, else an existing node is returned with its counter incremented. This can be checked by testing returnedNode.getCount() > 1.

isEmpty

public boolean isEmpty()

Tests whether the index contains any items.

Returns:

true if the index does not contain any items

query

public List query(BoundingBox queryEnv)

Performs a range search of the points in the index.

Parameters:

queryEnv - the range rectangle to query

Returns:

a list of the KdNodes found

query

public void query(BoundingBox queryEnv,
         List result)

Performs a range search of the points in the index.

Parameters:

queryEnv - the range rectangle to query

result - a list to accumulate the result nodes into