Class KdTree

Hierarchy: Object , KdTree

public class KdTree

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 distance tolerance. If the same point (up to tolerance) is inserted more than once, it is snapped to the existing node. In other words, if a point is inserted which lies within the tolerance of a node already in the index, it is snapped to that node. When a point is snapped to a node then a new node is not created but the count of the existing node is incremented. If more than one node in the tree is within tolerance of an inserted point, the closest and then lowest node is snapped to.

Authors:: David Skea; Martin Davis

public KdTree()

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

public KdTree(double tolerance)

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

Parameters:: tolerance - tolerance the tolerance distance for considering two points equal

public static Coordinate[] toCoordinates(Collection kdnodes)

Converts a collection of KdNodes to an array of Coordinates.

Parameters:: kdnodes - kdnodes a collection of nodes

Returns:: an array of the coordinates represented by the nodes

public static Coordinate[] toCoordinates(Collection kdnodes, boolean includeRepeated)

Converts a collection of KdNodes to an array of Coordinates, specifying whether repeated nodes should be represented by multiple coordinates.

Parameters:: kdnodes - kdnodes a collection of nodes; includeRepeated - includeRepeated true if repeated nodes should be included multiple times

Returns:: an array of the coordinates represented by the nodes

public boolean isEmpty()

Tests whether the index contains any items.

Returns:: true if the index does not contain any items

public KdNode insert(Coordinate p)

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

Parameters:: p - p the point to insert

Returns:: the kdnode containing the point

public KdNode insert(Coordinate p, Object data)

Inserts a new point into the kd-tree.

Parameters:: p - p the point to insert; data - 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.

public void query(Envelope queryEnv, KdNodeVisitor visitor)

Performs a range search of the points in the index and visits all nodes found.

Parameters:: queryEnv - queryEnv the range rectangle to query; visitor - visitor a visitor to visit all nodes found by the search

public List query(Envelope queryEnv)

Performs a range search of the points in the index.

Parameters:: queryEnv - queryEnv the range rectangle to query

Returns:: a list of the KdNodes found

public void query(Envelope queryEnv, List result)

Performs a range search of the points in the index.

Parameters:: queryEnv - queryEnv the range rectangle to query; result - result a list to accumulate the result nodes into