001: //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/trunk/src/org/deegree/io/quadtree/MemPointNode.java $
002: /*---------------- FILE HEADER ------------------------------------------
003:
004: This file is part of deegree.
005: Copyright (C) 2001-2008 by:
006: EXSE, Department of Geography, University of Bonn
007: http://www.giub.uni-bonn.de/deegree/
008: lat/lon GmbH
009: http://www.lat-lon.de
010:
011: This library is free software; you can redistribute it and/or
012: modify it under the terms of the GNU Lesser General Public
013: License as published by the Free Software Foundation; either
014: version 2.1 of the License, or (at your option) any later version.
015:
016: This library is distributed in the hope that it will be useful,
017: but WITHOUT ANY WARRANTY; without even the implied warranty of
018: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
019: Lesser General Public License for more details.
020:
021: You should have received a copy of the GNU Lesser General Public
022: License along with this library; if not, write to the Free Software
023: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
024:
025: Contact:
026:
027: Andreas Poth
028: lat/lon GmbH
029: Aennchenstr. 19
030: 53115 Bonn
031: Germany
032: E-Mail: poth@lat-lon.de
033:
034: Prof. Dr. Klaus Greve
035: Department of Geography
036: University of Bonn
037: Meckenheimer Allee 166
038: 53115 Bonn
039: Germany
040: E-Mail: greve@giub.uni-bonn.de
041:
042:
043: ---------------------------------------------------------------------------*/
044: package org.deegree.io.quadtree;
045:
046: import java.util.ArrayList;
047: import java.util.List;
048:
049: import org.deegree.model.spatialschema.Envelope;
050: import org.deegree.model.spatialschema.GeometryFactory;
051:
052: /**
053: * <code>MemPointNode</code> is the node class of a memory based implementation of a quadtree.
054: *
055: * @author <a href="mailto:schmitz@lat-lon.de">Andreas Schmitz</a>
056: * @author last edited by: $Author: apoth $
057: *
058: * @version 2.0, $Revision: 9342 $, $Date: 2007-12-27 04:32:57 -0800 (Thu, 27 Dec 2007) $
059: * @param <T>
060: * the datatype to be used as id
061: *
062: * @since 2.0
063: */
064:
065: public class MemPointNode<T> implements Node<T> {
066:
067: private final Envelope envelope;
068:
069: private final int level;
070:
071: private MemPointNode<T>[] subnodes;
072:
073: private List<T> items;
074:
075: private List<Envelope> itemsEnvelope;
076:
077: private Quadtree owner;
078:
079: /**
080: * Constructs a new node with the given envelope, object, location and level.
081: *
082: * @param owner
083: * @param env
084: * the envelope
085: * @param lvl
086: * the level
087: */
088: public MemPointNode(Quadtree owner, Envelope env, int lvl) {
089: envelope = env;
090: level = lvl;
091: this .owner = owner;
092: }
093:
094: /**
095: * @return the deepest level of this subtree
096: */
097: public int getDepth() {
098: if (subnodes == null) {
099: return level;
100: }
101:
102: int max = 0;
103: int d = 0;
104:
105: for (MemPointNode node : subnodes) {
106: if (node != null) {
107: d = node.getDepth();
108: if (d > max) {
109: max = d;
110: }
111: }
112: }
113:
114: return max;
115: }
116:
117: /**
118: * @return the region of this node
119: */
120: public Envelope getEnvelope() {
121: return envelope;
122: }
123:
124: /**
125: * This method does not make sense for the memory implementation.
126: *
127: * @return null
128: */
129: public String getId() {
130: return null;
131: }
132:
133: /**
134: * Inserts the item into the quadtree.
135: *
136: * @param item
137: * the item
138: * @param itemEnv
139: * the envelope of the item
140: */
141: public boolean insert(T item, Envelope itemEnv)
142: throws IndexException {
143:
144: if (!envelope.intersects(itemEnv)) {
145: throw new IndexException(
146: "Item envelope does not intersect with node envelope!");
147: }
148:
149: if (level < ((MemPointQuadtree) owner).maxDepth) {
150: Envelope[] envs = split();
151:
152: if (subnodes == null) {
153: subnodes = (MemPointNode<T>[]) new MemPointNode[4];
154: }
155:
156: for (int i = 0; i < 4; ++i) {
157: if (envs[i].intersects(itemEnv)) {
158: if (subnodes[i] == null) {
159: subnodes[i] = new MemPointNode<T>(owner,
160: envs[i], level + 1);
161: }
162: subnodes[i].insert(item, itemEnv);
163: }
164: }
165: } else {
166: if (items == null) {
167: items = new ArrayList<T>(50);
168: itemsEnvelope = new ArrayList<Envelope>(50);
169: }
170: items.add(item);
171: itemsEnvelope.add(itemEnv);
172: }
173: return true;
174: }
175:
176: /**
177: * Searches for all items intersecting the search envelope.
178: *
179: * @param searchEnv
180: * the search envelope
181: * @param visitor
182: * the resulting list
183: * @param level
184: * unused by this implementation
185: * @return a list with all found items
186: */
187: public List<T> query(Envelope searchEnv, List<T> visitor, int level)
188: throws IndexException {
189:
190: if (subnodes == null) {
191: return visitor;
192: }
193:
194: for (int i = 0; i < 4; ++i) {
195: if (subnodes[i] != null) {
196: MemPointNode<T> node = subnodes[i];
197: if (node.items != null) {
198: if (subnodes[i].envelope.intersects(searchEnv)) {
199: for (int j = 0; j < node.itemsEnvelope.size(); j++) {
200: Envelope env = node.itemsEnvelope.get(j);
201: if (env.intersects(searchEnv)) {
202: visitor.addAll(node.items);
203: }
204: }
205: }
206: } else {
207: if (node.envelope.intersects(searchEnv)) {
208: node.query(searchEnv, visitor, level);
209: }
210: }
211: }
212: }
213:
214: return visitor;
215: }
216:
217: /**
218: * Deletes the item from the quadtree. Untested method!
219: *
220: * @param item
221: * the item to be deleted
222: */
223: public boolean delete(T item, Envelope env) throws IndexException {
224:
225: if (subnodes != null) {
226: for (int i = 0; i < 4; ++i) {
227: if (subnodes[i] != null) {
228: MemPointNode<T> node = subnodes[i];
229: if (node.items.contains(item)) {
230: node.items.remove(item);
231: } else {
232: return node.delete(item, env);
233: }
234: }
235: }
236: }
237: return true;
238:
239: }
240:
241: public boolean update(T item, Envelope newBBox) {
242: throw new UnsupportedOperationException(
243: "This method is not implemented for the mempoint Node, maybe use a delete and insert combination?");
244: }
245:
246: /**
247: * Deletes all items intersecting the envelope. Untested method!
248: *
249: * @param envelope
250: */
251: public void deleteRange(Envelope envelope) {
252:
253: if (subnodes == null) {
254: return;
255: }
256:
257: for (int i = 0; i < 4; ++i) {
258: if (subnodes[i] != null) {
259: MemPointNode node = subnodes[i];
260: if (node.envelope.intersects(envelope)) {
261: subnodes[i] = null;
262: } else {
263: if (node.envelope.intersects(envelope)) {
264: node.deleteRange(envelope);
265: }
266: }
267: }
268: }
269:
270: }
271:
272: // splits the envelope of this node in four pieces
273: private Envelope[] split() {
274: Envelope[] envs = new Envelope[4];
275: double nW = envelope.getWidth() / 2d;
276: double nH = envelope.getHeight() / 2d;
277:
278: envs[0] = GeometryFactory.createEnvelope(envelope.getMin()
279: .getX(), envelope.getMin().getY(), envelope.getMin()
280: .getX()
281: + nW, envelope.getMin().getY() + nH, null);
282: envs[1] = GeometryFactory.createEnvelope(envelope.getMin()
283: .getX()
284: + nW, envelope.getMin().getY(), envelope.getMin()
285: .getX()
286: + (2 * nW), envelope.getMin().getY() + nH, null);
287: envs[2] = GeometryFactory.createEnvelope(envelope.getMin()
288: .getX()
289: + nW, envelope.getMin().getY() + nH, envelope.getMin()
290: .getX()
291: + (2 * nW), envelope.getMin().getY() + (2 * nH), null);
292: envs[3] = GeometryFactory.createEnvelope(envelope.getMin()
293: .getX(), envelope.getMin().getY() + nH, envelope
294: .getMin().getX()
295: + nW, envelope.getMin().getY() + (2 * nH), null);
296:
297: return envs;
298: }
299:
300: }
|