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