Class: KdTree

jsts.index.kdtree.KdTree

new KdTree(tolerance)

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. 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:
Name Type Description
tolerance Number (optional) the tolerance distance for considering two points equal.
Source:

Methods

insert() → {jsts.index.kdtree.KdNode}

Inserts a new point in the kd-tree. Will call correct *insert function depending on arguments
Source:
Returns:
The kd-node containing the point.
Type
jsts.index.kdtree.KdNode

insertCoordinate(p) → {jsts.index.kdtree.KdNode}

Inserts a new point in the kd-tree, with no data.
Parameters:
Name Type Description
p jsts.geom.Coordinate the point to insert.
Source:
Returns:
the kdnode containing the point.
Type
jsts.index.kdtree.KdNode

insertWithData(p, data) → {jsts.index.kdtree.KdNode}

Inserts a new point into the kd-tree.
Parameters:
Name Type Description
p jsts.geom.Coordinate the point to insert.
data Object a data item for the point.
Source:
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.
Type
jsts.index.kdtree.KdNode

query()

Will call the correct *query-function depending on arguments
Source:
Returns:

queryByEnvelope(queryEnv) → {Array}

Performs a range search of the points in the index.
Parameters:
Name Type Description
queryEnv jsts.geom.Envelope the range rectangle to query.
Source:
Returns:
a list of the KdNodes found.
Type
Array

queryNode(currentNode, bottomNode, queryEnv, odd, result)

Query's the tree
Parameters:
Name Type Description
currentNode jsts.index.kdtree.KdNode the current node.
bottomNode jsts.index.kdtree.KdNode the bottom node.
queryEnv jsts.geom.Envelope the query-envelope.
odd Boolean true if the level is odd.
result Array the array to fill the result with.
Source:

queryWithArray(queryEnv, result)

Performs a range search of the points in the index.
Parameters:
Name Type Description
queryEnv jsts.geom.Envelope the range rectangle to query.
result Array a list to accumulate the result nodes into.
Source: