Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## com.vividsolutions.jts.index.kdtree
Class KdTree

    java.lang.Object
      com.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

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD