Class KdTree
- java.lang.Object
-
- org.locationtech.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 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 a 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
KdTree.BestMatchVisitor
-
Field Summary
Fields Modifier and Type Field Description private long
numberOfNodes
private KdNode
root
private double
tolerance
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private KdNode
findBestMatchNode(Coordinate p)
Finds the node in the tree which is the best match for a point being inserted.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.private KdNode
insertExact(Coordinate p, java.lang.Object data)
Inserts a point known to be beyond the distance tolerance of any existing node.boolean
isEmpty()
Tests whether the index contains any items.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.void
query(Envelope queryEnv, KdNodeVisitor visitor)
Performs a range search of the points in the index and visits all nodes found.private void
queryNode(KdNode currentNode, Envelope queryEnv, boolean odd, KdNodeVisitor visitor)
static Coordinate[]
toCoordinates(java.util.Collection kdnodes)
Converts a collection ofKdNode
s to an array ofCoordinate
s.static Coordinate[]
toCoordinates(java.util.Collection kdnodes, boolean includeRepeated)
Converts a collection ofKdNode
s to an array ofCoordinate
s, specifying whether repeated nodes should be represented by multiple coordinates.
-
-
-
Field Detail
-
root
private KdNode root
-
numberOfNodes
private long numberOfNodes
-
tolerance
private double 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
-
toCoordinates
public static Coordinate[] toCoordinates(java.util.Collection kdnodes)
Converts a collection ofKdNode
s to an array ofCoordinate
s.- Parameters:
kdnodes
- a collection of nodes- Returns:
- an array of the coordinates represented by the nodes
-
toCoordinates
public static Coordinate[] toCoordinates(java.util.Collection kdnodes, boolean includeRepeated)
Converts a collection ofKdNode
s to an array ofCoordinate
s, specifying whether repeated nodes should be represented by multiple coordinates.- Parameters:
kdnodes
- a collection of nodesincludeRepeated
- true if repeated nodes should be included multiple times- Returns:
- an array of the coordinates represented by the nodes
-
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, java.lang.Object data)
Inserts a new point into the kd-tree.- Parameters:
p
- the point to insertdata
- 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.
-
findBestMatchNode
private KdNode findBestMatchNode(Coordinate p)
Finds the node in the tree which is the best match for a point being inserted. The match is made deterministic by returning the lowest of any nodes which lie the same distance from the point. There may be no match if the point is not within the distance tolerance of any existing node.- Parameters:
p
- the point being inserted- Returns:
- the best matching node
-
insertExact
private KdNode insertExact(Coordinate p, java.lang.Object data)
Inserts a point known to be beyond the distance tolerance of any existing node. The point is inserted at the bottom of the exact splitting path, so that tree shape is deterministic.- Parameters:
p
- the point to insertdata
- the data for the point- Returns:
- the created node
-
queryNode
private void queryNode(KdNode currentNode, Envelope queryEnv, boolean odd, KdNodeVisitor visitor)
-
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 queryvisitor
- a visitor to visit all nodes found by the search
-
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 queryresult
- a list to accumulate the result nodes into
-
-