Class KdTree

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12
13	package org.locationtech.jts.index.kdtree;
14
15	import java.util.ArrayList;
16	import java.util.Collection;
17	import java.util.Iterator;
18	import java.util.List;
19
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geom.CoordinateList;
22	import org.locationtech.jts.geom.Envelope;
23
24
25	/**
26	* An implementation of a 2-D KD-Tree. KD-trees provide fast range searching on
27	* point data.
28	* <p>
29	* This implementation supports detecting and snapping points which are closer
30	* than a given distance tolerance.
31	* If the same point (up to tolerance) is inserted
32	* more than once, it is snapped to the existing node.
33	* In other words, if a point is inserted which lies within the tolerance of a node already in the index,
34	* it is snapped to that node.
35	* When a point is snapped to a node then a new node is not created but the count of the existing node
36	* is incremented.
37	* If more than one node in the tree is within tolerance of an inserted point,
38	* the closest and then lowest node is snapped to.
39	*
40	* @author David Skea
41	* @author Martin Davis
42	*/
43	public class KdTree {
44
45	/**
46	* Converts a collection of {@link KdNode}s to an array of {@link Coordinate}s.
47	*
48	* @param kdnodes
49	* a collection of nodes
50	* @return an array of the coordinates represented by the nodes
51	*/
52	public static Coordinate[] toCoordinates(Collection kdnodes) {
53	return toCoordinates(kdnodes, false);
54	}
55
56	/**
57	* Converts a collection of {@link KdNode}s
58	* to an array of {@link Coordinate}s,
59	* specifying whether repeated nodes should be represented
60	* by multiple coordinates.
61	*
62	* @param kdnodes a collection of nodes
63	* @param includeRepeated true if repeated nodes should
64	* be included multiple times
65	* @return an array of the coordinates represented by the nodes
66	*/
67	public static Coordinate[] toCoordinates(Collection kdnodes, boolean includeRepeated) {
68	CoordinateList coord = new CoordinateList();
69	for (Iterator it = kdnodes.iterator(); it.hasNext();) {
70	KdNode node = (KdNode) it.next();
71	int count = includeRepeated ? node.getCount() : 1;
72	for (int i = 0; i < count; i++) {
73	coord.add(node.getCoordinate(), true);
74	}
75	}
76	return coord.toCoordinateArray();
77	}
78
79	private KdNode root = null;
80	private long numberOfNodes;
81	private double tolerance;
82
83	/**
84	* Creates a new instance of a KdTree with a snapping tolerance of 0.0. (I.e.
85	* distinct points will <i>not</i> be snapped)
86	*/
87	public KdTree() {
88	this(0.0);
89	}
90
91	/**
92	* Creates a new instance of a KdTree, specifying a snapping distance
93	* tolerance. Points which lie closer than the tolerance to a point already in
94	* the tree will be treated as identical to the existing point.
95	*
96	* @param tolerance
97	* the tolerance distance for considering two points equal
98	*/
99	public KdTree(double tolerance) {
100	this.tolerance = tolerance;
101	}
102
103	/**
104	* Tests whether the index contains any items.
105	*
106	* @return true if the index does not contain any items
107	*/
108	public boolean isEmpty() {
109	if (root == null)
110	return true;
111	return false;
112	}
113
114	/**
115	* Inserts a new point in the kd-tree, with no data.
116	*
117	* @param p
118	* the point to insert
119	* @return the kdnode containing the point
120	*/
121	public KdNode insert(Coordinate p) {
122	return insert(p, null);
123	}
124
125	/**
126	* Inserts a new point into the kd-tree.
127	*
128	* @param p
129	* the point to insert
130	* @param data
131	* a data item for the point
132	* @return returns a new KdNode if a new point is inserted, else an existing
133	* node is returned with its counter incremented. This can be checked
134	* by testing returnedNode.getCount() > 1.
135	*/
136	public KdNode insert(Coordinate p, Object data) {
137	if (root == null) {
138	root = new KdNode(p, data);
139	return root;
140	}
141
142	/**
143	* Check if the point is already in the tree, up to tolerance.
144	* If tolerance is zero, this phase of the insertion can be skipped.
145	*/
146	if ( tolerance > 0 ) {
147	KdNode matchNode = findBestMatchNode(p);
148	if (matchNode != null) {
149	// point already in index - increment counter
150	matchNode.increment();
151	return matchNode;
152	}
153	}
154
155	return insertExact(p, data);
156	}
157
158	/**
159	* Finds the node in the tree which is the best match for a point
160	* being inserted.
161	* The match is made deterministic by returning the lowest of any nodes which
162	* lie the same distance from the point.
163	* There may be no match if the point is not within the distance tolerance of any
164	* existing node.
165	*
166	* @param p the point being inserted
167	* @return the best matching node
168	* @return null if no match was found
169	*/
170	private KdNode findBestMatchNode(Coordinate p) {
171	BestMatchVisitor visitor = new BestMatchVisitor(p, tolerance);
172	query(visitor.queryEnvelope(), visitor);
173	return visitor.getNode();
174	}
175
176	static private class BestMatchVisitor implements KdNodeVisitor {
177
178	private double tolerance;
179	private KdNode matchNode = null;
180	private double matchDist = 0.0;
181	private Coordinate p;
182
183	public BestMatchVisitor(Coordinate p, double tolerance) {
184	this.p = p;
185	this.tolerance = tolerance;
186	}
187
188	public Envelope queryEnvelope() {
189	Envelope queryEnv = new Envelope(p);
190	queryEnv.expandBy(tolerance);
191	return queryEnv;
192	}
193
194	public KdNode getNode() {
195	return matchNode;
196	}
197
198	public void visit(KdNode node) {
199	double dist = p.distance(node.getCoordinate());
200	boolean isInTolerance = dist <= tolerance;
201	if (! isInTolerance) return;
202	boolean update = false;
203	if (matchNode == null
204	\|\| dist < matchDist
205	// if distances are the same, record the lesser coordinate
206	\|\| (matchNode != null && dist == matchDist
207	&& node.getCoordinate().compareTo(matchNode.getCoordinate()) < 1))
208	update = true;
209
210	if (update) {
211	matchNode = node;
212	matchDist = dist;
213	}
214	}
215	}
216
217	/**
218	* Inserts a point known to be beyond the distance tolerance of any existing node.
219	* The point is inserted at the bottom of the exact splitting path,
220	* so that tree shape is deterministic.
221	*
222	* @param p the point to insert
223	* @param data the data for the point
224	* @return the created node
225	*/
226	private KdNode insertExact(Coordinate p, Object data) {
227	KdNode currentNode = root;
228	KdNode leafNode = root;
229	boolean isOddLevel = true;
230	boolean isLessThan = true;
231
232	/**
233	* Traverse the tree, first cutting the plane left-right (by X ordinate)
234	* then top-bottom (by Y ordinate)
235	*/
236	while (currentNode != null) {
237	// test if point is already a node (not strictly necessary)
238	if (currentNode != null) {
239	boolean isInTolerance = p.distance(currentNode.getCoordinate()) <= tolerance;
240
241	// check if point is already in tree (up to tolerance) and if so simply
242	// return existing node
243	if (isInTolerance) {
244	currentNode.increment();
245	return currentNode;
246	}
247	}
248
249	if (isOddLevel) {
250	isLessThan = p.x < currentNode.getX();
251	} else {
252	isLessThan = p.y < currentNode.getY();
253	}
254	leafNode = currentNode;
255	if (isLessThan) {
256	currentNode = currentNode.getLeft();
257	} else {
258	currentNode = currentNode.getRight();
259	}
260
261	isOddLevel = ! isOddLevel;
262	}
263
264	// no node found, add new leaf node to tree
265	numberOfNodes = numberOfNodes + 1;
266	KdNode node = new KdNode(p, data);
267	if (isLessThan) {
268	leafNode.setLeft(node);
269	} else {
270	leafNode.setRight(node);
271	}
272	return node;
273	}
274
275	private void queryNode(KdNode currentNode,
276	Envelope queryEnv, boolean odd, KdNodeVisitor visitor) {
277	if (currentNode == null)
278	return;
279
280	double min;
281	double max;
282	double discriminant;
283	if (odd) {
284	min = queryEnv.getMinX();
285	max = queryEnv.getMaxX();
286	discriminant = currentNode.getX();
287	} else {
288	min = queryEnv.getMinY();
289	max = queryEnv.getMaxY();
290	discriminant = currentNode.getY();
291	}
292	boolean searchLeft = min < discriminant;
293	boolean searchRight = discriminant <= max;
294
295	// search is computed via in-order traversal
296	if (searchLeft) {
297	queryNode(currentNode.getLeft(), queryEnv, !odd, visitor);
298	}
299	if (queryEnv.contains(currentNode.getCoordinate())) {
300	visitor.visit(currentNode);
301	}
302	if (searchRight) {
303	queryNode(currentNode.getRight(), queryEnv, !odd, visitor);
304	}
305
306	}
307
308	/**
309	* Performs a range search of the points in the index and visits all nodes found.
310	*
311	* @param queryEnv
312	* the range rectangle to query
313	* @param visitor a visitor to visit all nodes found by the search
314	*/
315	public void query(Envelope queryEnv, KdNodeVisitor visitor) {
316	queryNode(root, queryEnv, true, visitor);
317	}
318
319	/**
320	* Performs a range search of the points in the index.
321	*
322	* @param queryEnv
323	* the range rectangle to query
324	* @return a list of the KdNodes found
325	*/
326	public List query(Envelope queryEnv) {
327	final List result = new ArrayList();
328	query(queryEnv, result);
329	return result;
330	}
331
332	/**
333	* Performs a range search of the points in the index.
334	*
335	* @param queryEnv
336	* the range rectangle to query
337	* @param result
338	* a list to accumulate the result nodes into
339	*/
340	public void query(Envelope queryEnv, final List result) {
341	queryNode(root, queryEnv, true, new KdNodeVisitor() {
342
343	public void visit(KdNode node) {
344	result.add(node);
345	}
346
347	});
348	}
349	}
350