Class STRtree

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.index.strtree;
14
15	import java.io.Serializable;
16	import java.util.ArrayList;
17	import java.util.Collections;
18	import java.util.Comparator;
19	import java.util.Iterator;
20	import java.util.List;
21	import java.util.PriorityQueue;
22
23	import org.locationtech.jts.geom.Envelope;
24	import org.locationtech.jts.index.ItemVisitor;
25	import org.locationtech.jts.index.SpatialIndex;
26	import org.locationtech.jts.util.Assert;
27
28
29	/**
30	* A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm.
31	* For two-dimensional spatial data.
32	* <P>
33	* The STR packed R-tree is simple to implement and maximizes space
34	* utilization; that is, as many leaves as possible are filled to capacity.
35	* Overlap between nodes is far less than in a basic R-tree. However, once the
36	* tree has been built (explicitly or on the first call to #query), items may
37	* not be added or removed.
38	* <P>
39	* Described in: P. Rigaux, Michel Scholl and Agnes Voisard.
40	* <i>Spatial Databases With Application To GIS</i>.
41	* Morgan Kaufmann, San Francisco, 2002.
42	* <p>
43	* <b>Note that inserting items into a tree is not thread-safe.</b>
44	* Inserting performed on more than one thread must be synchronized externally.
45	* <p>
46	* Querying a tree is thread-safe.
47	* The building phase is done synchronously,
48	* and querying is stateless.
49	*
50	* @version 1.7
51	*/
52	public class STRtree extends AbstractSTRtree
53	implements SpatialIndex, Serializable
54	{
55
56	private static final class STRtreeNode extends AbstractNode
57	{
58	private STRtreeNode(int level)
59	{
60	super(level);
61	}
62
63	protected Object computeBounds() {
64	Envelope bounds = null;
65	for (Iterator i = getChildBoundables().iterator(); i.hasNext(); ) {
66	Boundable childBoundable = (Boundable) i.next();
67	if (bounds == null) {
68	bounds = new Envelope((Envelope)childBoundable.getBounds());
69	}
70	else {
71	bounds.expandToInclude((Envelope)childBoundable.getBounds());
72	}
73	}
74	return bounds;
75	}
76	}
77
78	/**
79	*
80	*/
81	private static final long serialVersionUID = 259274702368956900L;
82
83	private static Comparator xComparator =
84	new Comparator() {
85	public int compare(Object o1, Object o2) {
86	return compareDoubles(
87	centreX((Envelope)((Boundable)o1).getBounds()),
88	centreX((Envelope)((Boundable)o2).getBounds()));
89	}
90	};
91	private static Comparator yComparator =
92	new Comparator() {
93	public int compare(Object o1, Object o2) {
94	return compareDoubles(
95	centreY((Envelope)((Boundable)o1).getBounds()),
96	centreY((Envelope)((Boundable)o2).getBounds()));
97	}
98	};
99
100	private static double centreX(Envelope e) {
101	return avg(e.getMinX(), e.getMaxX());
102	}
103
104	private static double centreY(Envelope e) {
105	return avg(e.getMinY(), e.getMaxY());
106	}
107
108	private static double avg(double a, double b) { return (a + b) / 2d; }
109
110	private static IntersectsOp intersectsOp = new IntersectsOp() {
111	public boolean intersects(Object aBounds, Object bBounds) {
112	return ((Envelope)aBounds).intersects((Envelope)bBounds);
113	}
114	};
115
116	/**
117	* Creates the parent level for the given child level. First, orders the items
118	* by the x-values of the midpoints, and groups them into vertical slices.
119	* For each slice, orders the items by the y-values of the midpoints, and
120	* group them into runs of size M (the node capacity). For each run, creates
121	* a new (parent) node.
122	*/
123	protected List createParentBoundables(List childBoundables, int newLevel) {
124	Assert.isTrue(!childBoundables.isEmpty());
125	int minLeafCount = (int) Math.ceil((childBoundables.size() / (double) getNodeCapacity()));
126	ArrayList sortedChildBoundables = new ArrayList(childBoundables);
127	Collections.sort(sortedChildBoundables, xComparator);
128	List[] verticalSlices = verticalSlices(sortedChildBoundables,
129	(int) Math.ceil(Math.sqrt(minLeafCount)));
130	return createParentBoundablesFromVerticalSlices(verticalSlices, newLevel);
131	}
132
133	private List createParentBoundablesFromVerticalSlices(List[] verticalSlices, int newLevel) {
134	Assert.isTrue(verticalSlices.length > 0);
135	List parentBoundables = new ArrayList();
136	for (int i = 0; i < verticalSlices.length; i++) {
137	parentBoundables.addAll(
138	createParentBoundablesFromVerticalSlice(verticalSlices[i], newLevel));
139	}
140	return parentBoundables;
141	}
142
143	protected List createParentBoundablesFromVerticalSlice(List childBoundables, int newLevel) {
144	return super.createParentBoundables(childBoundables, newLevel);
145	}
146
147	/**
148	* @param childBoundables Must be sorted by the x-value of the envelope midpoints
149	*/
150	protected List[] verticalSlices(List childBoundables, int sliceCount) {
151	int sliceCapacity = (int) Math.ceil(childBoundables.size() / (double) sliceCount);
152	List[] slices = new List[sliceCount];
153	Iterator i = childBoundables.iterator();
154	for (int j = 0; j < sliceCount; j++) {
155	slices[j] = new ArrayList();
156	int boundablesAddedToSlice = 0;
157	while (i.hasNext() && boundablesAddedToSlice < sliceCapacity) {
158	Boundable childBoundable = (Boundable) i.next();
159	slices[j].add(childBoundable);
160	boundablesAddedToSlice++;
161	}
162	}
163	return slices;
164	}
165
166	private static final int DEFAULT_NODE_CAPACITY = 10;
167
168	/**
169	* Constructs an STRtree with the default node capacity.
170	*/
171	public STRtree()
172	{
173	this(DEFAULT_NODE_CAPACITY);
174	}
175
176	/**
177	* Constructs an STRtree with the given maximum number of child nodes that
178	* a node may have.
179	* <p>
180	* The minimum recommended capacity setting is 4.
181	*
182	*/
183	public STRtree(int nodeCapacity) {
184	super(nodeCapacity);
185	}
186
187	protected AbstractNode createNode(int level) {
188	return new STRtreeNode(level);
189	}
190
191	protected IntersectsOp getIntersectsOp() {
192	return intersectsOp;
193	}
194
195	/**
196	* Inserts an item having the given bounds into the tree.
197	*/
198	public void insert(Envelope itemEnv, Object item) {
199	if (itemEnv.isNull()) { return; }
200	super.insert(itemEnv, item);
201	}
202
203	/**
204	* Returns items whose bounds intersect the given envelope.
205	*/
206	public List query(Envelope searchEnv) {
207	//Yes this method does something. It specifies that the bounds is an
208	//Envelope. super.query takes an Object, not an Envelope. [Jon Aquino 10/24/2003]
209	return super.query(searchEnv);
210	}
211
212	/**
213	* Returns items whose bounds intersect the given envelope.
214	*/
215	public void query(Envelope searchEnv, ItemVisitor visitor) {
216	//Yes this method does something. It specifies that the bounds is an
217	//Envelope. super.query takes an Object, not an Envelope. [Jon Aquino 10/24/2003]
218	super.query(searchEnv, visitor);
219	}
220
221	/**
222	* Removes a single item from the tree.
223	*
224	* @param itemEnv the Envelope of the item to remove
225	* @param item the item to remove
226	* @return <code>true</code> if the item was found
227	*/
228	public boolean remove(Envelope itemEnv, Object item) {
229	return super.remove(itemEnv, item);
230	}
231
232	/**
233	* Returns the number of items in the tree.
234	*
235	* @return the number of items in the tree
236	*/
237	public int size()
238	{
239	return super.size();
240	}
241
242	/**
243	* Returns the number of items in the tree.
244	*
245	* @return the number of items in the tree
246	*/
247	public int depth()
248	{
249	return super.depth();
250	}
251
252	protected Comparator getComparator() {
253	return yComparator;
254	}
255
256	/**
257	* Finds the two nearest items in the tree,
258	* using {@link ItemDistance} as the distance metric.
259	* A Branch-and-Bound tree traversal algorithm is used
260	* to provide an efficient search.
261	* <p>
262	* If the tree is empty, the return value is <code>null</code.
263	* If the tree contains only one item,
264	* the return value is a pair containing that item.
265	* <b>
266	* If it is required to find only pairs of distinct items,
267	* the {@link ItemDistance} function must be <b>anti-reflexive</b>.
268	*
269	* @param itemDist a distance metric applicable to the items in this tree
270	* @return the pair of the nearest items
271	* or <code>null</code> if the tree is empty
272	*/
273	public Object[] nearestNeighbour(ItemDistance itemDist)
274	{
275	if (isEmpty()) return null;
276
277	// if tree has only one item this will return null
278	BoundablePair bp = new BoundablePair(this.getRoot(), this.getRoot(), itemDist);
279	return nearestNeighbour(bp);
280	}
281
282	/**
283	* Finds the item in this tree which is nearest to the given {@link Object},
284	* using {@link ItemDistance} as the distance metric.
285	* A Branch-and-Bound tree traversal algorithm is used
286	* to provide an efficient search.
287	* <p>
288	* The query <tt>object</tt> does <b>not</b> have to be
289	* contained in the tree, but it does
290	* have to be compatible with the <tt>itemDist</tt>
291	* distance metric.
292	*
293	* @param env the envelope of the query item
294	* @param item the item to find the nearest neighbour of
295	* @param itemDist a distance metric applicable to the items in this tree and the query item
296	* @return the nearest item in this tree
297	* or <code>null</code> if the tree is empty
298	*/
299	public Object nearestNeighbour(Envelope env, Object item, ItemDistance itemDist)
300	{
301	Boundable bnd = new ItemBoundable(env, item);
302	BoundablePair bp = new BoundablePair(this.getRoot(), bnd, itemDist);
303	return nearestNeighbour(bp)[0];
304	}
305
306	/**
307	* Finds the two nearest items from this tree
308	* and another tree,
309	* using {@link ItemDistance} as the distance metric.
310	* A Branch-and-Bound tree traversal algorithm is used
311	* to provide an efficient search.
312	* The result value is a pair of items,
313	* the first from this tree and the second
314	* from the argument tree.
315	*
316	* @param tree another tree
317	* @param itemDist a distance metric applicable to the items in the trees
318	* @return the pair of the nearest items, one from each tree
319	* or <code>null</code> if no pair of distinct items can be found
320	*/
321	public Object[] nearestNeighbour(STRtree tree, ItemDistance itemDist)
322	{
323	if (isEmpty() \|\| tree.isEmpty()) return null;
324	BoundablePair bp = new BoundablePair(this.getRoot(), tree.getRoot(), itemDist);
325	return nearestNeighbour(bp);
326	}
327
328	private Object[] nearestNeighbour(BoundablePair initBndPair)
329	{
330	double distanceLowerBound = Double.POSITIVE_INFINITY;
331	BoundablePair minPair = null;
332
333	// initialize search queue
334	PriorityQueue priQ = new PriorityQueue();
335	priQ.add(initBndPair);
336
337	while (! priQ.isEmpty() && distanceLowerBound > 0.0) {
338	// pop head of queue and expand one side of pair
339	BoundablePair bndPair = (BoundablePair) priQ.poll();
340	double pairDistance = bndPair.getDistance();
341
342	/**
343	* If the distance for the first pair in the queue
344	* is >= current minimum distance, other nodes
345	* in the queue must also have a greater distance.
346	* So the current minDistance must be the true minimum,
347	* and we are done.
348	*/
349	if (pairDistance >= distanceLowerBound)
350	break;
351
352	/**
353	* If the pair members are leaves
354	* then their distance is the exact lower bound.
355	* Update the distanceLowerBound to reflect this
356	* (which must be smaller, due to the test
357	* immediately prior to this).
358	*/
359	if (bndPair.isLeaves()) {
360	// assert: currentDistance < minimumDistanceFound
361	distanceLowerBound = pairDistance;
362	minPair = bndPair;
363	}
364	else {
365	/**
366	* Otherwise, expand one side of the pair,
367	* and insert the expanded pairs into the queue.
368	* The choice of which side to expand is determined heuristically.
369	*/
370	bndPair.expandToQueue(priQ, distanceLowerBound);
371	}
372	}
373	if (minPair == null)
374	return null;
375	// done - return items with min distance
376	return new Object[] {
377	((ItemBoundable) minPair.getBoundable(0)).getItem(),
378	((ItemBoundable) minPair.getBoundable(1)).getItem()
379	};
380	}
381
382	/**
383	* Tests whether some two items from this tree and another tree
384	* lie within a given distance.
385	* {@link ItemDistance} is used as the distance metric.
386	* A Branch-and-Bound tree traversal algorithm is used
387	* to provide an efficient search.
388	*
389	* @param tree another tree
390	* @param itemDist a distance metric applicable to the items in the trees
391	* @param maxDistance the distance limit for the search
392	* @return true if there are items within the distance
393	*/
394	public boolean isWithinDistance(STRtree tree, ItemDistance itemDist, double maxDistance)
395	{
396	BoundablePair bp = new BoundablePair(this.getRoot(), tree.getRoot(), itemDist);
397	return isWithinDistance(bp, maxDistance);
398	}
399
400	/**
401	* Performs a withinDistance search on the tree node pairs.
402	* This is a different search algorithm to nearest neighbour.
403	* It can utilize the {@link BoundablePair#maximumDistance()} between
404	* tree nodes to confirm if two internal nodes must
405	* have items closer than the maxDistance,
406	* and short-circuit the search.
407	*
408	* @param initBndPair the initial pair containing the tree root nodes
409	* @param maxDistance the maximum distance to search for
410	* @return true if two items lie within the given distance
411	*/
412	private boolean isWithinDistance(BoundablePair initBndPair, double maxDistance)
413	{
414	double distanceUpperBound = Double.POSITIVE_INFINITY;
415
416	// initialize search queue
417	PriorityQueue priQ = new PriorityQueue();
418	priQ.add(initBndPair);
419
420	while (! priQ.isEmpty()) {
421	// pop head of queue and expand one side of pair
422	BoundablePair bndPair = (BoundablePair) priQ.poll();
423	double pairDistance = bndPair.getDistance();
424
425	/**
426	* If the distance for the first pair in the queue
427	* is > maxDistance, all other pairs
428	* in the queue must have a greater distance as well.
429	* So can conclude no items are within the distance
430	* and terminate with result = false
431	*/
432	if (pairDistance > maxDistance)
433	return false;
434
435	/**
436	* If the maximum distance between the nodes
437	* is less than the maxDistance,
438	* than all items in the nodes must be
439	* closer than the max distance.
440	* Then can terminate with result = true.
441	*
442	* NOTE: using Envelope MinMaxDistance
443	* would provide a tighter bound,
444	* but not much performance improvement has been observed
445	*/
446	if (bndPair.maximumDistance() <= maxDistance)
447	return true;
448	/**
449	* If the pair items are leaves
450	* then their actual distance is an upper bound.
451	* Update the distanceUpperBound to reflect this
452	*/
453	if (bndPair.isLeaves()) {
454	// assert: currentDistance < minimumDistanceFound
455	distanceUpperBound = pairDistance;
456
457	/**
458	* If the items are closer than maxDistance
459	* can terminate with result = true.
460	*/
461	if (distanceUpperBound <= maxDistance)
462	return true;
463	}
464	else {
465	/**
466	* Otherwise, expand one side of the pair,
467	* and insert the expanded pairs into the queue.
468	* The choice of which side to expand is determined heuristically.
469	*/
470	bndPair.expandToQueue(priQ, distanceUpperBound);
471	}
472	}
473	return false;
474	}
475
476	/**
477	* Finds k items in this tree which are the top k nearest neighbors to the given {@code item},
478	* using {@code itemDist} as the distance metric.
479	* A Branch-and-Bound tree traversal algorithm is used
480	* to provide an efficient search.
481	* This method implements the KNN algorithm described in the following paper:
482	* <p>
483	* Roussopoulos, Nick, Stephen Kelley, and Frédéric Vincent. "Nearest neighbor queries."
484	* ACM sigmod record. Vol. 24. No. 2. ACM, 1995.
485	* <p>
486	* The query {@code item} does <b>not</b> have to be
487	* contained in the tree, but it does
488	* have to be compatible with the {@code itemDist}
489	* distance metric.
490	*
491	* @param env the envelope of the query item
492	* @param item the item to find the nearest neighbour of
493	* @param itemDist a distance metric applicable to the items in this tree and the query item
494	* @param k the K nearest items in kNearestNeighbour
495	* @return the K nearest items in this tree
496	*/
497	public Object[] nearestNeighbour(Envelope env, Object item, ItemDistance itemDist,int k)
498	{
499	Boundable bnd = new ItemBoundable(env, item);
500	BoundablePair bp = new BoundablePair(this.getRoot(), bnd, itemDist);
501	return nearestNeighbourK(bp,k);
502	}
503
504	private Object[] nearestNeighbourK(BoundablePair initBndPair, int k)
505	{
506	return nearestNeighbourK(initBndPair, Double.POSITIVE_INFINITY,k);
507	}
508
509	private Object[] nearestNeighbourK(BoundablePair initBndPair, double maxDistance, int k)
510	{
511	double distanceLowerBound = maxDistance;
512
513	// initialize internal structures
514	PriorityQueue priQ = new PriorityQueue();
515
516	// initialize queue
517	priQ.add(initBndPair);
518
519	PriorityQueue kNearestNeighbors = new PriorityQueue();
520
521	while (! priQ.isEmpty() && distanceLowerBound >= 0.0) {
522	// pop head of queue and expand one side of pair
523	BoundablePair bndPair = (BoundablePair) priQ.poll();
524	double pairDistance = bndPair.getDistance();
525
526
527	/**
528	* If the distance for the first node in the queue
529	* is >= the current maximum distance in the k queue , all other nodes
530	* in the queue must also have a greater distance.
531	* So the current minDistance must be the true minimum,
532	* and we are done.
533	*/
534	if (pairDistance >= distanceLowerBound){
535	break;
536	}
537	/**
538	* If the pair members are leaves
539	* then their distance is the exact lower bound.
540	* Update the distanceLowerBound to reflect this
541	* (which must be smaller, due to the test
542	* immediately prior to this).
543	*/
544	if (bndPair.isLeaves()) {
545	// assert: currentDistance < minimumDistanceFound
546
547	if(kNearestNeighbors.size()<k){
548	kNearestNeighbors.add(bndPair);
549	}
550	else
551	{
552
553	BoundablePair bp1 = (BoundablePair) kNearestNeighbors.peek();
554	if(bp1.getDistance() > pairDistance) {
555	kNearestNeighbors.poll();
556	kNearestNeighbors.add(bndPair);
557	}
558	/*
559	* minDistance should be the farthest point in the K nearest neighbor queue.
560	*/
561	BoundablePair bp2 = (BoundablePair) kNearestNeighbors.peek();
562	distanceLowerBound = bp2.getDistance();
563	}
564	}
565	else {
566	/**
567	* Otherwise, expand one side of the pair,
568	* (the choice of which side to expand is heuristically determined)
569	* and insert the new expanded pairs into the queue
570	*/
571	bndPair.expandToQueue(priQ, distanceLowerBound);
572	}
573	}
574	// done - return items with min distance
575
576	return getItems(kNearestNeighbors);
577	}
578	private static Object[] getItems(PriorityQueue kNearestNeighbors)
579	{
580	/**
581	* Iterate the K Nearest Neighbour Queue and retrieve the item from each BoundablePair
582	* in this queue
583	*/
584	Object[] items = new Object[kNearestNeighbors.size()];
585	int count=0;
586	while( ! kNearestNeighbors.isEmpty() )
587	{
588	BoundablePair bp = (BoundablePair) kNearestNeighbors.poll();
589	items[count]=((ItemBoundable)bp.getBoundable(0)).getItem();
590	count++;
591	}
592	return items;
593	}
594	}
595
596