001: package org.geotools.caching.quatree;
002:
003: import org.geotools.caching.QueryTracker;
004: import org.geotools.caching.spatialindex.spatialindex.Region;
005:
006: import org.geotools.data.DefaultQuery;
007: import org.geotools.data.Query;
008:
009: import org.geotools.feature.FeatureType;
010:
011: import org.geotools.filter.FilterFactoryImpl;
012: import org.geotools.filter.spatial.BBOXImpl;
013:
014: import org.opengis.filter.Filter;
015:
016: import java.util.ArrayList;
017: import java.util.Iterator;
018: import java.util.Stack;
019:
020: public class QuadTreeQueryTracker implements QueryTracker {
021: int max_tiles = 10;
022: QuadTree tree;
023: FeatureType type;
024:
025: public QuadTreeQueryTracker(Region r, FeatureType type) {
026: this .tree = new QuadTree(r);
027: this .type = type;
028: }
029:
030: public void clear() {
031: // TODO Auto-generated method stub
032: }
033:
034: public Filter match(Filter f) {
035: //TODO: change Filter to BBOXImpl in interface,
036: // this is the only type of feature we should accept
037: // then next line is useless
038: BBOXImpl filter = (BBOXImpl) f;
039:
040: //
041: Region r = new Region(new double[] { filter.getMinX(),
042: filter.getMinY() }, new double[] { filter.getMaxX(),
043: filter.getMaxY() });
044: ValidTileVisitor v = new ValidTileVisitor();
045: tree.containmentQuery(r, v);
046:
047: if (v.isCovered) {
048: // we do not need extra data
049: return Filter.EXCLUDE;
050: } else { // we need extra data
051: // find missing tiles
052: //
053: // case 1: outside of quadtree, ie of root node MBR
054:
055: if (v.lastNode == null) {
056: return f; // in first approximation, we can't answer this query
057: // TODO: handle in a more subtle manner
058: }
059:
060: // case 2: inside of quadtree, ie of root node MBR
061: Stack regions = new Stack();
062: searchMissingTiles(r, v.lastNode, regions);
063:
064: if (regions.size() > 1) {
065: ArrayList filters = new ArrayList();
066: FilterFactoryImpl ff = new FilterFactoryImpl();
067:
068: while (!regions.isEmpty()) {
069: Region rg = (Region) regions.pop();
070: Filter missing = ff.bbox(filter.getPropertyName(),
071: rg.getLow(0), rg.getLow(1), rg.getHigh(0),
072: rg.getHigh(1), filter.getSRS());
073: filters.add(missing);
074: }
075:
076: return ff.and(filters);
077: } else if (regions.size() == 1) {
078: FilterFactoryImpl ff = new FilterFactoryImpl();
079: Region rg = (Region) regions.pop();
080:
081: return ff.bbox(filter.getPropertyName(), rg.getLow(0),
082: rg.getLow(1), rg.getHigh(0), rg.getHigh(1),
083: filter.getSRS());
084: } else {
085: return Filter.EXCLUDE;
086: }
087: }
088: }
089:
090: public Query match(Query q) {
091: if (accept(q)) {
092: Filter f = match(q.getFilter());
093:
094: return new DefaultQuery(q.getTypeName(), f);
095: } else {
096: return q;
097: }
098: }
099:
100: public void register(Query q) {
101: if (accept(q)) {
102: register(q.getFilter());
103: }
104: }
105:
106: public void register(Filter f) {
107: // TODO: change Filter to BBOXImpl in interface,
108: // this is the only type of feature we should accept
109: // then next line is useless
110: BBOXImpl filter = (BBOXImpl) f;
111:
112: //
113: Region r = new Region(new double[] { filter.getMinX(),
114: filter.getMinY() }, new double[] { filter.getMaxX(),
115: filter.getMaxY() });
116: tree.insertData(null, r, filter.hashCode());
117:
118: ValidatingVisitor v = new ValidatingVisitor(r);
119: tree.intersectionQuery(r, v);
120: }
121:
122: public void unregister(Query q) {
123: if (accept(q)) {
124: unregister(q.getFilter());
125: }
126: }
127:
128: public void unregister(Filter f) {
129: BBOXImpl filter = (BBOXImpl) f;
130: InvalidatingVisitor v = new InvalidatingVisitor();
131: Region r = getRegion(filter);
132: tree.containmentQuery(r, v);
133: v.updateTree();
134: }
135:
136: // Internals
137: protected boolean accept(Query q) {
138: return (q.getTypeName().equals(type.getTypeName()));
139: }
140:
141: protected void searchMissingTiles(final Region r, Node current,
142: Stack s) {
143: if (current.isLeaf()) {
144: // we have no data
145: // we must get corresponding normalized region from DataStore
146: Region normalized = normalize(r, current);
147: // add region to stack of regions to retrieve
148: s.push(normalized);
149: } else {
150: int new_missing_tiles = s.size();
151:
152: for (int i = 0; i < current.getChildrenCount(); i++) {
153: Node child = current.getSubNode(i);
154:
155: if (child.getShape().intersects(r)) { // falls within our search criteria
156: // if valid, we don't need this tile,
157: // otherwise recurse to find missing children
158:
159: if (!child.isValid()) {
160: searchMissingTiles(r, child, s);
161: }
162: }
163: }
164:
165: // check for new missing tiles and group before returning
166: new_missing_tiles = s.size() - new_missing_tiles;
167:
168: if (new_missing_tiles > max_tiles) {
169: // we have too many new sub-tiles
170: for (int i = 0; i < new_missing_tiles; i++) {
171: s.pop();
172: }
173:
174: // we will fetch whole tile
175: s.push(current.getShape());
176: } else if (new_missing_tiles > 1) {
177: // we have 2 or more new tiles
178: // trying to group what can be grouped
179: Stack newtiles = new Stack();
180:
181: for (int i = 0; i < new_missing_tiles; i++) {
182: newtiles.push(s.pop());
183: }
184:
185: groupRegions(newtiles, s);
186: }
187: }
188: }
189:
190: /** Group intersecting tiles in a list.
191: * Brute force algo returning with time n!,
192: * we expect a small number of tiles in list ...
193: *
194: * @param tiles list of tiles to group
195: * @param stack where to put resulting grouped tiles
196: */
197: protected static void groupRegions(Stack tiles, Stack s) {
198: assert (tiles.size() > 1);
199:
200: while (!tiles.isEmpty()) {
201: Region r1 = (Region) tiles.pop();
202: boolean combinationHappened = false;
203:
204: for (Iterator it = tiles.iterator(); it.hasNext();) {
205: Region r2 = (Region) it.next();
206:
207: if (r1.intersects(r2)) {
208: it.remove();
209: r1 = r1.combinedRegion(r2);
210: combinationHappened = true;
211: }
212: }
213:
214: if (combinationHappened) {
215: // we reinject for other matches
216: tiles.push(r1);
217: } else {
218: s.push(r1);
219: }
220: }
221: }
222:
223: protected static Region normalize(final Region r, final Node node) {
224: Region noderegion = (Region) node.getShape();
225: Region inter = intersection(r, noderegion);
226: int level = node.getLevel();
227:
228: while (level > 0) {
229: boolean done = true;
230: Region[] splits = getSplits(noderegion);
231:
232: for (int i = 0; i < splits.length; i++) {
233: if (splits[i].contains(inter)) {
234: noderegion = splits[i];
235: done = false;
236:
237: break;
238: }
239: }
240:
241: if (done) {
242: break;
243: }
244:
245: level--;
246: }
247:
248: return noderegion;
249: }
250:
251: protected static Region[] getSplits(Region r) {
252: Region[] ret = new Region[4];
253: Region[] tmp = Node.splitBounds(r, QuadTree.SPLITRATIO);
254: ret[0] = tmp[0];
255: ret[2] = tmp[1];
256: tmp = Node.splitBounds(ret[0], QuadTree.SPLITRATIO);
257: ret[0] = tmp[0];
258: ret[1] = tmp[1];
259: tmp = Node.splitBounds(ret[2], QuadTree.SPLITRATIO);
260: ret[2] = tmp[0];
261: ret[3] = tmp[1];
262:
263: return ret;
264: }
265:
266: protected static Region intersection(final Region r1,
267: final Region r2) {
268: double xmin = (r1.getLow(0) > r2.getLow(0)) ? r1.getLow(0) : r2
269: .getLow(0);
270: double ymin = (r1.getLow(1) > r2.getLow(1)) ? r1.getLow(1) : r2
271: .getLow(1);
272: double xmax = (r1.getHigh(0) < r2.getHigh(0)) ? r1.getHigh(0)
273: : r2.getHigh(0);
274: double ymax = (r1.getHigh(1) < r2.getHigh(1)) ? r1.getHigh(1)
275: : r2.getHigh(1);
276:
277: return new Region(new double[] { xmin, ymin }, new double[] {
278: xmax, ymax });
279: }
280:
281: protected static Region getRegion(BBOXImpl f) {
282: return new Region(new double[] { f.getMinX(), f.getMinY() },
283: new double[] { f.getMaxX(), f.getMaxY() });
284: }
285: }
|