Class Quadtree

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.quadtree;
14
15	import java.io.Serializable;
16	import java.util.ArrayList;
17	import java.util.List;
18
19	import org.locationtech.jts.geom.Envelope;
20	import org.locationtech.jts.geom.Geometry;
21	import org.locationtech.jts.index.ArrayListVisitor;
22	import org.locationtech.jts.index.ItemVisitor;
23	import org.locationtech.jts.index.SpatialIndex;
24	/**
25	* A Quadtree is a spatial index structure for efficient range querying
26	* of items bounded by 2D rectangles.
27	* {@link Geometry}s can be indexed by using their
28	* {@link Envelope}s.
29	* Any type of Object can also be indexed as
30	* long as it has an extent that can be represented by an {@link Envelope}.
31	* <p>
32	* This Quadtree index provides a <b>primary filter</b>
33	* for range rectangle queries. The various query methods return a list of
34	* all items which <i>may</i> intersect the query rectangle. Note that
35	* it may thus return items which do <b>not</b> in fact intersect the query rectangle.
36	* A secondary filter is required to test for actual intersection
37	* between the query rectangle and the envelope of each candidate item.
38	* The secondary filter may be performed explicitly,
39	* or it may be provided implicitly by subsequent operations executed on the items
40	* (for instance, if the index query is followed by computing a spatial predicate
41	* between the query geometry and tree items,
42	* the envelope intersection check is performed automatically.
43	* <p>
44	* This implementation does not require specifying the extent of the inserted
45	* items beforehand. It will automatically expand to accommodate any extent
46	* of dataset.
47	* <p>
48	* This data structure is also known as an <i>MX-CIF quadtree</i>
49	* following the terminology of Samet and others.
50	*
51	* @version 1.7
52	*/
53	public class Quadtree
54	implements SpatialIndex, Serializable
55	{
56	private static final long serialVersionUID = -7461163625812743604L;
57
58	/**
59	* Ensure that the envelope for the inserted item has non-zero extents.
60	* Use the current minExtent to pad the envelope, if necessary
61	*/
62	public static Envelope ensureExtent(Envelope itemEnv, double minExtent)
63	{
64	//The names "ensureExtent" and "minExtent" are misleading -- sounds like
65	//this method ensures that the extents are greater than minExtent.
66	//Perhaps we should rename them to "ensurePositiveExtent" and "defaultExtent".
67	//[Jon Aquino]
68	double minx = itemEnv.getMinX();
69	double maxx = itemEnv.getMaxX();
70	double miny = itemEnv.getMinY();
71	double maxy = itemEnv.getMaxY();
72	// has a non-zero extent
73	if (minx != maxx && miny != maxy) return itemEnv;
74
75	// pad one or both extents
76	if (minx == maxx) {
77	minx = minx - minExtent / 2.0;
78	maxx = maxx + minExtent / 2.0;
79	}
80	if (miny == maxy) {
81	miny = miny - minExtent / 2.0;
82	maxy = maxy + minExtent / 2.0;
83	}
84	return new Envelope(minx, maxx, miny, maxy);
85	}
86
87	private Root root;
88	/**
89
90	* minExtent is the minimum envelope extent of all items
91	* inserted into the tree so far. It is used as a heuristic value
92	* to construct non-zero envelopes for features with zero X and/or Y extent.
93	* Start with a non-zero extent, in case the first feature inserted has
94	* a zero extent in both directions. This value may be non-optimal, but
95	* only one feature will be inserted with this value.
96	**/
97	private double minExtent = 1.0;
98
99	/**
100	* Constructs a Quadtree with zero items.
101	*/
102	public Quadtree()
103	{
104	root = new Root();
105	}
106
107	/**
108	* Returns the number of levels in the tree.
109	*/
110	public int depth()
111	{
112	//I don't think it's possible for root to be null. Perhaps we should
113	//remove the check. [Jon Aquino]
114	//Or make an assertion [Jon Aquino 10/29/2003]
115	if (root != null) return root.depth();
116	return 0;
117	}
118
119	/**
120	* Tests whether the index contains any items.
121	*
122	* @return true if the index does not contain any items
123	*/
124	public boolean isEmpty()
125	{
126	if (root == null) return true;
127	return root.isEmpty();
128	}
129
130	/**
131	* Returns the number of items in the tree.
132	*
133	* @return the number of items in the tree
134	*/
135	public int size()
136	{
137	if (root != null) return root.size();
138	return 0;
139	}
140
141	public void insert(Envelope itemEnv, Object item)
142	{
143	collectStats(itemEnv);
144	Envelope insertEnv = ensureExtent(itemEnv, minExtent);
145	root.insert(insertEnv, item);
146	}
147
148	/**
149	* Removes a single item from the tree.
150	*
151	* @param itemEnv the Envelope of the item to be removed
152	* @param item the item to remove
153	* @return <code>true</code> if the item was found (and thus removed)
154	*/
155	public boolean remove(Envelope itemEnv, Object item)
156	{
157	Envelope posEnv = ensureExtent(itemEnv, minExtent);
158	return root.remove(posEnv, item);
159	}
160
161	/*
162	public List OLDquery(Envelope searchEnv)
163	{
164	/**
165	* the items that are matched are the items in quads which
166	* overlap the search envelope
167	*/
168	/*
169	List foundItems = new ArrayList();
170	root.addAllItemsFromOverlapping(searchEnv, foundItems);
171	return foundItems;
172	}
173	*/
174
175	/**
176	* Queries the tree and returns items which may lie in the given search envelope.
177	* Precisely, the items that are returned are all items in the tree
178	* whose envelope <b>may</b> intersect the search Envelope.
179	* Note that some items with non-intersecting envelopes may be returned as well;
180	* the client is responsible for filtering these out.
181	* In most situations there will be many items in the tree which do not
182	* intersect the search envelope and which are not returned - thus
183	* providing improved performance over a simple linear scan.
184	*
185	* @param searchEnv the envelope of the desired query area.
186	* @return a List of items which may intersect the search envelope
187	*/
188	public List query(Envelope searchEnv)
189	{
190	/**
191	* the items that are matched are the items in quads which
192	* overlap the search envelope
193	*/
194	ArrayListVisitor visitor = new ArrayListVisitor();
195	query(searchEnv, visitor);
196	return visitor.getItems();
197	}
198
199	/**
200	* Queries the tree and visits items which may lie in the given search envelope.
201	* Precisely, the items that are visited are all items in the tree
202	* whose envelope <b>may</b> intersect the search Envelope.
203	* Note that some items with non-intersecting envelopes may be visited as well;
204	* the client is responsible for filtering these out.
205	* In most situations there will be many items in the tree which do not
206	* intersect the search envelope and which are not visited - thus
207	* providing improved performance over a simple linear scan.
208	*
209	* @param searchEnv the envelope of the desired query area.
210	* @param visitor a visitor object which is passed the visited items
211	*/
212	public void query(Envelope searchEnv, ItemVisitor visitor)
213	{
214	/**
215	* the items that are matched are the items in quads which
216	* overlap the search envelope
217	*/
218	root.visit(searchEnv, visitor);
219	}
220
221	/**
222	* Return a list of all items in the Quadtree
223	*/
224	public List queryAll()
225	{
226	List foundItems = new ArrayList();
227	root.addAllItems(foundItems);
228	return foundItems;
229	}
230
231	private void collectStats(Envelope itemEnv)
232	{
233	double delX = itemEnv.getWidth();
234	if (delX < minExtent && delX > 0.0)
235	minExtent = delX;
236
237	double delY = itemEnv.getHeight();
238	if (delY < minExtent && delY > 0.0)
239	minExtent = delY;
240	}
241
242	}
243