001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-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.caching.quatree;
017:
018: import org.geotools.caching.spatialindex.spatialindex.IData;
019: import org.geotools.caching.spatialindex.spatialindex.INearestNeighborComparator;
020: import org.geotools.caching.spatialindex.spatialindex.INodeCommand;
021: import org.geotools.caching.spatialindex.spatialindex.IQueryStrategy;
022: import org.geotools.caching.spatialindex.spatialindex.IShape;
023: import org.geotools.caching.spatialindex.spatialindex.ISpatialIndex;
024: import org.geotools.caching.spatialindex.spatialindex.IStatistics;
025: import org.geotools.caching.spatialindex.spatialindex.IVisitor;
026: import org.geotools.caching.spatialindex.spatialindex.Region;
027: import org.geotools.caching.spatialindex.storagemanager.PropertySet;
028:
029: import java.util.Stack;
030: import java.util.logging.Logger;
031:
032: /** A QuadTree implementation, inspired by the shapefile quadtree in org.geotools.index.quadtree,
033: * but using visitors and query strategies to customize how the tree is visited or run specialized queries.
034: *
035: * Other noticeable changes from original QuadTree :
036: * <ul><li>tree delegates splitting to nodes
037: * </ul>
038: *
039: * @see org.geotools.index.quadtree.QuadTree
040: * @see http://research.att.com/~marioh/spatialindex
041: *
042: * @author Christophe Rousson, SoC 2007, CRG-ULAVAL
043: *
044: * 2007-07-10: implemented maximum depth : allow to specify that the tree must not grow more than n levels
045: * TODO: implement full interface
046: * 2007-07-11: allowed to extend the tree from top, by changing root node
047: * TODO: make tree serializable or loadable from disk
048: *
049: */
050: public class QuadTree implements ISpatialIndex {
051: /**
052: * Control how much sub-quadrants do overlap.
053: * if ratio = 0.5, quadrants will not overlap at all.
054: * I guess that we want quadrants to overlap a bit, due to roundoff errors.
055: * Defaults to orginial value picked in org.geotools.index.quadtree.QuadTree
056: */
057: protected static final double SPLITRATIO = 0.55d;
058: protected static final Logger LOGGER = org.geotools.util.logging.Logging
059: .getLogger("org.geotools.caching.quadtree");
060:
061: /**
062: * First node of the tree, pointing recursively to all other nodes.
063: */
064: protected Node root;
065:
066: // Constructors
067:
068: /** Creates a new QuadTree with first node with given bounds.
069: *
070: * @param bounds root node bounds.
071: * @param maxHeight is the maximum height of the tree
072: */
073: public QuadTree(Region bounds, int maxHeight) {
074: this .root = new Node(new Region(bounds), 0, maxHeight);
075: }
076:
077: /** Creates a new QuadTree with first node with given bounds.
078: * Tree height defaults to 20 levels.
079: * Use @see QuadTree(Region, int) to specify height.
080: *
081: * @param root node bounds
082: */
083: public QuadTree(Region bounds) {
084: this (bounds, 20);
085: }
086:
087: // Interface
088: public void addDeleteNodeCommand(INodeCommand nc) {
089: // TODO Auto-generated method stub
090: }
091:
092: public void addReadNodeCommand(INodeCommand nc) {
093: // TODO Auto-generated method stub
094: }
095:
096: public void addWriteNodeCommand(INodeCommand nc) {
097: // TODO Auto-generated method stub
098: }
099:
100: public void containmentQuery(IShape query, IVisitor v) {
101: Node current = this .root;
102: current.visited = false;
103:
104: Stack nodes = new Stack();
105:
106: if (current.getShape().contains(query)) {
107: nodes.push(current);
108: }
109:
110: while (!nodes.isEmpty()) {
111: current = (Node) nodes.pop();
112:
113: if (!current.visited) {
114: v.visitNode(current);
115:
116: for (int i = 0; i < current.getChildrenCount(); i++) {
117: current.getSubNode(i).visited = false;
118: }
119:
120: for (int i = 0; i < current.numShapes; i++) {
121: v.visitData(new Data(current.shapesData[i], null,
122: current.shapesId[i]));
123: }
124:
125: current.visited = true;
126: }
127:
128: for (int i = 0; i < current.getChildrenCount(); i++) {
129: Node child = current.getSubNode(i);
130:
131: if (!child.visited) {
132: if (child.getShape().contains(query)) {
133: // we will go back to this one to examine other children
134: nodes.push(current);
135: nodes.push(child);
136:
137: break;
138: } else {
139: child.visited = true;
140: }
141: }
142: }
143: }
144: }
145:
146: public boolean deleteData(IShape shape, int id) {
147: // TODO Auto-generated method stub
148: return false;
149: }
150:
151: public void flush() throws IllegalStateException {
152: // TODO Auto-generated method stub
153: }
154:
155: public PropertySet getIndexProperties() {
156: // TODO Auto-generated method stub
157: return null;
158: }
159:
160: public IStatistics getStatistics() {
161: // TODO Auto-generated method stub
162: return null;
163: }
164:
165: public void insertData(byte[] data, IShape shape, int id) {
166: if (this .root.getShape().contains(shape)) {
167: insertData(this .root, data, shape, id);
168: } else {
169: createNewRoot(shape);
170: assert (this .root.getShape().contains(shape));
171: insertData(this .root, data, shape, id);
172: }
173: }
174:
175: public void intersectionQuery(IShape query, IVisitor v) {
176: Node current = this .root;
177: current.visited = false;
178:
179: Stack nodes = new Stack();
180:
181: if (current.getShape().intersects(query)) {
182: nodes.push(current);
183: }
184:
185: while (!nodes.isEmpty()) {
186: current = (Node) nodes.pop();
187:
188: if (!current.visited) {
189: v.visitNode(current);
190:
191: for (int i = 0; i < current.getChildrenCount(); i++) {
192: current.getSubNode(i).visited = false;
193: }
194:
195: for (int i = 0; i < current.numShapes; i++) {
196: v.visitData(new Data(current.shapesData[i], null,
197: current.shapesId[i]));
198: }
199:
200: current.visited = true;
201: }
202:
203: for (int i = 0; i < current.getChildrenCount(); i++) {
204: Node child = current.getSubNode(i);
205:
206: if (!child.visited) {
207: if (child.getShape().intersects(query)) {
208: // we will go back to this one later to examine other children
209: nodes.push(current);
210: // meanwhile, we put one child at a time into stack, so we do not waste space
211: nodes.push(child);
212:
213: break;
214: } else {
215: // we won't have to compute intersection again and again
216: child.visited = true;
217: }
218: }
219: }
220: }
221: }
222:
223: public boolean isIndexValid() {
224: // TODO Auto-generated method stub
225: return false;
226: }
227:
228: public void nearestNeighborQuery(int k, IShape query, IVisitor v,
229: INearestNeighborComparator nnc) {
230: // TODO Auto-generated method stub
231: }
232:
233: public void nearestNeighborQuery(int k, IShape query, IVisitor v) {
234: // TODO Auto-generated method stub
235: }
236:
237: public void pointLocationQuery(IShape query, IVisitor v) {
238: // TODO Auto-generated method stub
239: }
240:
241: public void queryStrategy(IQueryStrategy qs) {
242: int[] next = new int[] { this .root.id };
243:
244: Node current = this .root;
245:
246: while (true) {
247: boolean[] hasNext = new boolean[] { false };
248: qs.getNextEntry(current, next, hasNext);
249:
250: if (!hasNext[0]) {
251: break;
252: } else {
253: if (next[0] < 0) {
254: current = current.parent;
255: } else {
256: current = current.getSubNode(next[0]);
257: }
258: }
259: }
260: }
261:
262: /** This a variant of the original interface method, using nodes directly rather than references to nodes using ids,
263: * as in this implementation nodes does not have a unique ID in the tree, they have a unique ID in their quadrant.
264: *
265: * @see org.geotools.caching.spatialindex.spatialindex.ISpatialIndex#queryStrategy(IQueryStrategy) ;
266: *
267: * @param qs
268: */
269: public void queryStrategy(QueryStrategy qs) {
270: Node current = this .root;
271:
272: while (true) {
273: boolean[] hasNext = new boolean[] { false };
274: current = qs.getNextNode(current, hasNext);
275:
276: if (hasNext[0] == false) {
277: break;
278: }
279: }
280: }
281:
282: // Internals
283:
284: /** Insert new data into node.
285: * Does not check data MBR fits into node MBR,
286: * but this is what is expected. This is why method is kept private.
287: *
288: * @param n target node
289: * @param data to insert
290: * @param MBR of new data
291: * @param id of data
292: */
293: private void insertData(Node n, byte[] data, IShape shape, int id) {
294: if (n.isIndex()) {
295: /* If there are subnodes, then consider whether this object
296: * will fit in them.
297: */
298: for (int i = 0; i < n.getChildrenCount(); i++) {
299: Node subNode = n.getSubNode(i);
300: boolean done = false;
301:
302: if (subNode.getShape().contains(shape)) {
303: insertData(subNode, data, shape, id);
304: // we allow for multiple insertion, so we postpone returning from method
305: done = true;
306: }
307:
308: if (done) {
309: return;
310: }
311: }
312: } else if (n.level > 0) { // we do not want the tree to grow much too tall
313: // if level == 0, we will add data to this node rather than splitting
314: /* Otherwise, consider creating four subnodes if could fit into
315: * them, and adding to the appropriate subnode.
316: */
317: n.split(SPLITRATIO);
318: // recurse
319: insertData(n, data, shape, id);
320:
321: return;
322: }
323:
324: // If none of that worked, just add it to this nodes list.
325: n.insertData(data, id);
326: }
327:
328: private void createNewRoot(IShape s) {
329: // TODO: take care of tree maximum height
330: final Region old = this .root.getShape().getMBR();
331: final Region r = enlargeRootRegion(old, s.getMBR());
332: final Node oldRoot = this .root;
333: this .root = new Node(r, 0, this .root.level);
334: this .queryStrategy(new QueryStrategy() {
335: Stack nodes = new Stack();
336: boolean insertionMode = true;
337: boolean inserted = false;
338: int targetNode = -1;
339:
340: public Node getNextNode(Node current, boolean[] hasNext) {
341: if (!insertionMode) {
342: if (!inserted) {
343: assert (targetNode > -1);
344: current.subNodes.remove(targetNode);
345: current.addSubNode(oldRoot);
346: hasNext[0] = true;
347: oldRoot.parent = current;
348: inserted = true;
349:
350: return oldRoot;
351: } else {
352: current.level = current.parent.level - 1;
353:
354: for (int i = 0; i < current.getChildrenCount(); i++) {
355: nodes.add(0, current.getSubNode(i));
356: }
357:
358: if (!nodes.isEmpty()) {
359: hasNext[0] = true;
360:
361: return (Node) nodes.pop();
362: } else {
363: hasNext[0] = false;
364:
365: return null;
366: }
367: }
368: } else if (current.getShape().contains(old)) {
369: if (current.isLeaf()) {
370: current.split(SPLITRATIO);
371: }
372:
373: insertionMode = false;
374:
375: for (int i = 0; i < current.getChildrenCount(); i++) {
376: if (current.getSubNode(i).getShape().contains(
377: old)) {
378: hasNext[0] = true;
379: insertionMode = true;
380: targetNode = i;
381:
382: return current.getSubNode(i);
383: }
384: }
385:
386: hasNext[0] = true;
387:
388: return current.parent;
389: } else {
390: hasNext[0] = false;
391:
392: return null;
393: }
394: }
395: });
396: }
397:
398: private Region enlargeRootRegion(Region old,
399: final Region regionToInclude) {
400: Region r = old.combinedRegion(regionToInclude);
401:
402: /* we actually make tiles a little bigger than how nodes do normally split
403: so we use a slightly smaller ratio */
404: double SPLITRATIO = QuadTree.SPLITRATIO - 0.02d;
405:
406: /*double xmin = (r.getLow(0) == old.getLow(0)) ? old.getLow(0) : old.getHigh(0) - (old.getHigh(0) - old.getLow(0))/SPLITRATIO ;
407: double ymin = (r.getLow(1) == old.getLow(1)) ? old.getLow(1) : old.getHigh(1) - (old.getHigh(1) - old.getLow(1))/SPLITRATIO ;
408: double xmax = (r.getHigh(0) == old.getHigh(0)) ? old.getHigh(0) : old.getLow(0) + (old.getHigh(0) - old.getLow(0))/SPLITRATIO ;
409: double ymax = (r.getHigh(1) == old.getHigh(1)) ? old.getHigh(1) : old.getLow(1) + (old.getHigh(1) - old.getLow(1))/SPLITRATIO ;
410: r = new Region(new double[] {xmin, ymin}, new double[] {xmax, ymax}) ;*/
411: if ((r.getLow(0) == old.getLow(0))
412: && (r.getLow(1) == old.getLow(1))) {
413: double xmin = old.getLow(0);
414: double ymin = old.getLow(1);
415: double xmax = old.getLow(0)
416: + ((old.getHigh(0) - old.getLow(0)) / SPLITRATIO);
417: double ymax = old.getLow(1)
418: + ((old.getHigh(1) - old.getLow(1)) / SPLITRATIO);
419: r = new Region(new double[] { xmin, ymin }, new double[] {
420: xmax, ymax });
421: } else if ((r.getLow(0) == old.getLow(0))
422: && (r.getHigh(1) == old.getHigh(1))) {
423: double xmin = old.getLow(0);
424: double ymin = old.getHigh(1)
425: - ((old.getHigh(1) - old.getLow(1)) / SPLITRATIO);
426: double xmax = old.getLow(0)
427: + ((old.getHigh(0) - old.getLow(0)) / SPLITRATIO);
428: double ymax = old.getHigh(1);
429: r = new Region(new double[] { xmin, ymin }, new double[] {
430: xmax, ymax });
431: } else if ((r.getHigh(0) == old.getHigh(0))
432: && (r.getHigh(1) == old.getHigh(1))) {
433: double xmin = old.getHigh(0)
434: - ((old.getHigh(0) - old.getLow(0)) / SPLITRATIO);
435: double ymin = old.getHigh(1)
436: - ((old.getHigh(1) - old.getLow(1)) / SPLITRATIO);
437: double xmax = old.getHigh(0);
438: double ymax = old.getHigh(1);
439: r = new Region(new double[] { xmin, ymin }, new double[] {
440: xmax, ymax });
441: } else {
442: assert ((r.getHigh(0) == old.getHigh(0)) && (r.getLow(1) == old
443: .getLow(1)));
444:
445: double xmin = old.getHigh(0)
446: - ((old.getHigh(0) - old.getLow(0)) / SPLITRATIO);
447: double ymin = old.getLow(1);
448: double xmax = old.getHigh(0);
449: double ymax = old.getLow(1)
450: + ((old.getHigh(1) - old.getLow(1)) / SPLITRATIO);
451: r = new Region(new double[] { xmin, ymin }, new double[] {
452: xmax, ymax });
453: }
454:
455: if (r.contains(regionToInclude)) {
456: return r;
457: } else {
458: return enlargeRootRegion(r, regionToInclude);
459: }
460: }
461:
462: /** Utility class to expose data records outside of the tree.
463: *
464: * @author Christophe Rousson, SoC 2007, CRG-ULAVAL
465: *
466: */
467: class Data implements IData {
468: private byte[] data;
469: private int id;
470: private IShape shape;
471:
472: public Data(byte[] data, Region mbr, int id) {
473: this .data = data;
474: this .shape = mbr;
475: this .id = id;
476: }
477:
478: public byte[] getData() {
479: return data;
480: }
481:
482: public int getIdentifier() {
483: return id;
484: }
485:
486: public IShape getShape() {
487: return shape;
488: }
489: }
490: }
|