org.locationtech.jts.index.kdtree

Class KdTree

java.lang.Object

org.locationtech.jts.index.kdtree.KdTree

public class KdTree
extends Object

An implementation of a KD-Tree over two dimensions (X and Y). KD-trees provide fast range searching and fast lookup for point data. The tree is built dynamically by inserting points. The tree supports queries by range and for point equality. For querying an internal stack is used instead of recursion to avoid overflow.

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 an inserted 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.

The structure of a KD-Tree depends on the order of insertion of the points. A tree may become unbalanced if the inserted points are coherent (e.g. monotonic in one or both dimensions). A perfectly balanced tree has depth of only log2(N), but an unbalanced tree may be much deeper. This has a serious impact on query efficiency. One solution to this is to randomize the order of points before insertion (e.g. by using Fisher-Yates shuffling).

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

Modifier and Type	Method and Description
int	depth() Computes the depth of the tree.
KdNode	getRoot() Gets the root node of this tree.
KdNode	insert(Coordinate p) Inserts a new point in the kd-tree, with no data.
KdNode	insert(Coordinate p, Object data) Inserts a new point into the kd-tree.
boolean	isEmpty() Tests whether the index contains any items.
KdNode	query(Coordinate queryPt) Searches for a given point in the index and returns its node if found.
List	query(Envelope queryEnv) Performs a range search of the points in the index.
void	query(Envelope queryEnv, KdNodeVisitor visitor) Performs a range search of the points in the index and visits all nodes found.
void	query(Envelope queryEnv, List result) Performs a range search of the points in the index.
int	size() Computes the size (number of items) in the tree.
static Coordinate[]	toCoordinates(Collection kdnodes) Converts a collection of KdNodes to an array of Coordinates.
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.

Methods inherited from class java.lang.Object

equals, 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. 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 - the tolerance distance for considering two points equal

Method Detail

toCoordinates

public static Coordinate[] toCoordinates(Collection kdnodes)

Converts a collection of KdNodes to an array of Coordinates.

Parameters:

kdnodes - a collection of nodes

Returns:

an array of the coordinates represented by the nodes

toCoordinates

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 - a collection of nodes

includeRepeated - true if repeated nodes should be included multiple times

Returns:

an array of the coordinates represented by the nodes

getRoot

public KdNode getRoot()

Gets the root node of this tree.

Returns:

the root node of the tree

isEmpty

public boolean isEmpty()

Tests whether the index contains any items.

Returns:

true if the index does not contain any items

insert

public KdNode insert(Coordinate 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(Coordinate 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.

query

public void query(Envelope queryEnv,
                  KdNodeVisitor visitor)

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

Parameters:

queryEnv - the range rectangle to query

visitor - a visitor to visit all nodes found by the search

query

public List query(Envelope 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(Envelope 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

query

public KdNode query(Coordinate queryPt)

Searches for a given point in the index and returns its node if found.

Parameters:

queryPt - the point to query

Returns:

the point node, if it is found in the index, or null if not

depth

public int depth()

Computes the depth of the tree.

Returns:

the depth of the tree

size

public int size()

Computes the size (number of items) in the tree.

Returns:

the size of the tree