com.vividsolutions.jts.index.kdtree

Class 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.

    • 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.

    • 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

      • 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 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