com.vividsolutions.jts.index.kdtree
Class KdTree

java.lang.Object
  extended bycom.vividsolutions.jts.index.kdtree.KdTree

public class KdTree
extends java.lang.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
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
 KdNode insert(Coordinate p)
          Inserts a new point in the kd-tree, with no data.
 KdNode insert(Coordinate p, java.lang.Object data)
          Inserts a new point into the kd-tree.
 java.util.List query(Envelope queryEnv)
          Performs a range search of the points in the index.
 void query(Envelope queryEnv, java.util.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. 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

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,
                     java.lang.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 java.util.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,
                  java.util.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