001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2005-2006, GeoTools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation;
009: * version 2.1 of the License.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.index.quadtree;
017:
018: import java.io.IOException;
019: import java.util.Collection;
020: import java.util.HashSet;
021: import java.util.Iterator;
022: import java.util.Set;
023: import java.util.logging.Level;
024: import java.util.logging.Logger;
025:
026: import org.geotools.data.shapefile.shp.IndexFile;
027:
028: import com.vividsolutions.jts.geom.Envelope;
029:
030: /**
031: * Java porting of mapserver quadtree implementation.<br><br>
032: * Note that this implementation is <b>not thread safe</b>, so don't share the
033: * same instance across two or more threads.
034: *
035: * TODO: example of typical use...
036: *
037: * @author Tommaso Nolli
038: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/plugin/shapefile/src/main/java/org/geotools/index/quadtree/QuadTree.java $
039: */
040: public class QuadTree {
041:
042: private static final double SPLITRATIO = 0.55d;
043:
044: private static final Logger LOGGER = org.geotools.util.logging.Logging
045: .getLogger("org.geotools.index.quadtree");
046:
047: private Node root;
048: private int numShapes;
049: private int maxDepth;
050:
051: private IndexFile indexfile;
052:
053: private Set iterators = new HashSet();
054:
055: /**
056: * Constructor.
057: * The maxDepth will be calculated.
058: * @param numShapes The total number of shapes to index
059: * @param maxBounds The bounds of all geometries to be indexed
060: */
061: public QuadTree(int numShapes, Envelope maxBounds, IndexFile file) {
062: this (numShapes, 0, maxBounds, file);
063: }
064:
065: /**
066: * Constructor.
067: * @param numShapes The total number of shapes to index
068: * @param maxDepth The max depth of the index, must be <= 65535
069: * @param maxBounds The bounds of all geometries to be indexed
070: */
071: public QuadTree(int numShapes, int maxDepth, Envelope maxBounds,
072: IndexFile file) {
073: if (maxDepth > 65535) {
074: throw new IllegalArgumentException(
075: "maxDepth must be <= 65535");
076: }
077:
078: this .numShapes = numShapes;
079: this .maxDepth = maxDepth;
080:
081: if (maxBounds != null)
082: this .root = new Node(new Envelope(maxBounds), 0, null);
083:
084: if (maxDepth < 1) {
085: /* No max depth was defined, try to select a reasonable one
086: * that implies approximately 8 shapes per node.
087: */
088: int numNodes = 1;
089: this .maxDepth = 0;
090:
091: while (numNodes * 4 < numShapes) {
092: this .maxDepth += 1;
093: numNodes = numNodes * 2;
094: }
095: }
096: this .indexfile = file;
097: }
098:
099: /**
100: * Constructor.
101: * WARNING: using this constructor, you have to manually set the root
102: * @param numShapes The total number of shapes to index
103: * @param maxDepth The max depth of the index, must be <= 65535
104: */
105: public QuadTree(int numShapes, int maxDepth, IndexFile file) {
106: this (numShapes, maxDepth, null, file);
107: }
108:
109: /**
110: * Inserts a shape record id in the quadtree
111: * @param recno The record number
112: * @param bounds The bounding box
113: */
114: public void insert(int recno, Envelope bounds)
115: throws StoreException {
116: this .insert(this .root, recno, bounds, this .maxDepth);
117: }
118:
119: /**
120: * Inserts a shape record id in the quadtree
121: * @param node
122: * @param recno
123: * @param bounds
124: * @param md
125: * @throws StoreException
126: */
127: private void insert(Node node, int recno, Envelope bounds, int md)
128: throws StoreException {
129:
130: if (md > 1 && node.getNumSubNodes() > 0) {
131: /* If there are subnodes, then consider whether this object
132: * will fit in them.
133: */
134: Node subNode = null;
135: for (int i = 0; i < node.getNumSubNodes(); i++) {
136: subNode = node.getSubNode(i);
137: if (subNode.getBounds().contains(bounds)) {
138: this .insert(subNode, recno, bounds, md - 1);
139: return;
140: }
141: }
142: } else if (md > 1 && node.getNumSubNodes() == 0) {
143: /* Otherwise, consider creating four subnodes if could fit into
144: * them, and adding to the appropriate subnode.
145: */
146: Envelope half1, half2, quad1, quad2, quad3, quad4;
147:
148: Envelope[] tmp = this .splitBounds(node.getBounds());
149: half1 = tmp[0];
150: half2 = tmp[1];
151:
152: tmp = this .splitBounds(half1);
153: quad1 = tmp[0];
154: quad2 = tmp[1];
155:
156: tmp = this .splitBounds(half2);
157: quad3 = tmp[0];
158: quad4 = tmp[1];
159:
160: if (quad1.contains(bounds) || quad2.contains(bounds)
161: || quad3.contains(bounds) || quad4.contains(bounds)) {
162: node.addSubNode(new Node(quad1, 0, node));
163: node.addSubNode(new Node(quad2, 1, node));
164: node.addSubNode(new Node(quad3, 2, node));
165: node.addSubNode(new Node(quad4, 3, node));
166:
167: // recurse back on this node now that it has subnodes
168: this .insert(node, recno, bounds, md);
169: return;
170: }
171: }
172:
173: // If none of that worked, just add it to this nodes list.
174: node.addShapeId(recno);
175: }
176:
177: /**
178: *
179: * @param bounds
180: * @return A List of Integer
181: */
182: public Collection search(Envelope bounds) throws StoreException {
183: if (LOGGER.isLoggable(Level.FINEST)) {
184: LOGGER.log(Level.FINEST, "Querying " + bounds);
185: }
186:
187: LazySearchCollection lazySearchCollection;
188: try {
189: lazySearchCollection = new LazySearchCollection(this ,
190: bounds);
191: } catch (RuntimeException e) {
192: LOGGER.warning("IOException occurred while reading root");
193: return null;
194: }
195: return lazySearchCollection;
196: }
197:
198: /**
199: * Closes this QuadTree after use...
200: * @throws StoreException
201: */
202: public void close(Iterator iter) throws StoreException {
203: iterators.remove(iter);
204: if (iter instanceof LazySearchIterator)
205: ((LazySearchIterator) iter).close();
206: }
207:
208: /**
209: *
210: */
211: public boolean trim() throws StoreException {
212: LOGGER.fine("Trimming the tree...");
213: return this .trim(this .root);
214: }
215:
216: /**
217: * Trim subtrees, and free subnodes that come back empty.
218: * @param node The node to trim
219: * @return true if this node has been trimmed
220: */
221: private boolean trim(Node node) throws StoreException {
222: Node[] dummy = new Node[node.getNumSubNodes()];
223: for (int i = 0; i < node.getNumSubNodes(); i++) {
224: dummy[i] = node.getSubNode(i);
225: }
226:
227: for (int i = 0; i < dummy.length; i++) {
228: if (this .trim(dummy[i])) {
229: node.removeSubNode(dummy[i]);
230: }
231: }
232:
233: /* If I have only 1 subnode and no shape records, promote that
234: * subnode to my position.
235: */
236: if (node.getNumSubNodes() == 1 && node.getNumShapeIds() == 0) {
237: Node subNode = node.getSubNode(0);
238:
239: node.clearSubNodes();
240: for (int i = 0; i < subNode.getNumSubNodes(); i++) {
241: node.addSubNode(subNode.getSubNode(i));
242: }
243:
244: node.setShapesId(subNode.getShapesId());
245: node.setBounds(subNode.getBounds());
246: }
247:
248: return (node.getNumSubNodes() == 0 && node.getNumShapeIds() == 0);
249: }
250:
251: /**
252: * Splits the specified Envelope
253: * @param in an Envelope to split
254: * @return an array of 2 Envelopes
255: */
256: private Envelope[] splitBounds(Envelope in) {
257: Envelope[] ret = new Envelope[2];
258: double range, calc;
259:
260: if ((in.getMaxX() - in.getMinX()) > (in.getMaxY() - in
261: .getMinY())) {
262: // Split in X direction
263: range = in.getMaxX() - in.getMinX();
264:
265: calc = in.getMinX() + range * SPLITRATIO;
266: ret[0] = new Envelope(in.getMinX(), calc, in.getMinY(), in
267: .getMaxY());
268:
269: calc = in.getMaxX() - range * SPLITRATIO;
270: ret[1] = new Envelope(calc, in.getMaxX(), in.getMinY(), in
271: .getMaxY());
272: } else {
273: // Split in Y direction
274: range = in.getMaxY() - in.getMinY();
275:
276: calc = in.getMinY() + range * SPLITRATIO;
277: ret[0] = new Envelope(in.getMinX(), in.getMaxX(), in
278: .getMinY(), calc);
279:
280: calc = in.getMaxY() - range * SPLITRATIO;
281: ret[1] = new Envelope(in.getMinX(), in.getMaxX(), calc, in
282: .getMaxY());
283: }
284:
285: return ret;
286: }
287:
288: /**
289: * @return Returns the maxDepth.
290: */
291: public int getMaxDepth() {
292: return this .maxDepth;
293: }
294:
295: /**
296: * @param maxDepth The maxDepth to set.
297: */
298: public void setMaxDepth(int maxDepth) {
299: this .maxDepth = maxDepth;
300: }
301:
302: /**
303: * @return Returns the numShapes.
304: */
305: public int getNumShapes() {
306: return this .numShapes;
307: }
308:
309: /**
310: * @param numShapes The numShapes to set.
311: */
312: public void setNumShapes(int numShapes) {
313: this .numShapes = numShapes;
314: }
315:
316: /**
317: * @return Returns the root.
318: */
319: public Node getRoot() {
320: return this .root;
321: }
322:
323: /**
324: * @param root The root to set.
325: */
326: public void setRoot(Node root) {
327: this .root = root;
328: }
329:
330: public void close() throws StoreException {
331: try {
332: indexfile.close();
333: } catch (IOException e) {
334: throw new StoreException("error closing indexfile", e
335: .getCause());
336: }
337: if (!iterators.isEmpty()) {
338: throw new StoreException("There are still open iterators!!");
339: }
340: }
341:
342: public void registerIterator(Iterator object) {
343: iterators.add(object);
344: }
345:
346: public IndexFile getIndexfile() {
347: return indexfile;
348: }
349: }
|