public class KdTree
extends java.lang.Object
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.
Modifier and Type | Class and Description |
---|---|
private static class |
KdTree.BestMatchVisitor |
Modifier and Type | Field and Description |
---|---|
private long |
numberOfNodes |
private KdNode |
root |
private double |
tolerance |
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.
|
Modifier and Type | Method and 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,
KdNodeVisitor visitor)
Performs a range search of the points in the index and visits all nodes found.
|
void |
query(Envelope queryEnv,
java.util.List result)
Performs a range search of the points in the index.
|
private void |
queryNode(KdNode currentNode,
Envelope queryEnv,
boolean odd,
KdNodeVisitor visitor) |
static Coordinate[] |
toCoordinates(java.util.Collection kdnodes)
Converts a collection of
KdNode s to an array of Coordinate s. |
static Coordinate[] |
toCoordinates(java.util.Collection kdnodes,
boolean includeRepeated)
Converts a collection of
KdNode s
to an array of Coordinate s,
specifying whether repeated nodes should be represented
by multiple coordinates. |
private KdNode root
private long numberOfNodes
private double tolerance
public KdTree()
public KdTree(double tolerance)
tolerance
- the tolerance distance for considering two points equalpublic static Coordinate[] toCoordinates(java.util.Collection kdnodes)
KdNode
s to an array of Coordinate
s.kdnodes
- a collection of nodespublic static Coordinate[] toCoordinates(java.util.Collection kdnodes, boolean includeRepeated)
KdNode
s
to an array of Coordinate
s,
specifying whether repeated nodes should be represented
by multiple coordinates.kdnodes
- a collection of nodesincludeRepeated
- true if repeated nodes should
be included multiple timespublic boolean isEmpty()
public KdNode insert(Coordinate p)
p
- the point to insertpublic KdNode insert(Coordinate p, java.lang.Object data)
p
- the point to insertdata
- a data item for the pointprivate KdNode findBestMatchNode(Coordinate p)
p
- the point being insertedprivate KdNode insertExact(Coordinate p, java.lang.Object data)
p
- the point to insertdata
- the data for the pointprivate void queryNode(KdNode currentNode, Envelope queryEnv, boolean odd, KdNodeVisitor visitor)
public void query(Envelope queryEnv, KdNodeVisitor visitor)
queryEnv
- the range rectangle to queryvisitor
- a visitor to visit all nodes found by the searchpublic java.util.List query(Envelope queryEnv)
queryEnv
- the range rectangle to querypublic void query(Envelope queryEnv, java.util.List result)
queryEnv
- the range rectangle to queryresult
- a list to accumulate the result nodes into