001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/branches/2.2_testing/src/org/deegree/io/quadtree/MemPointQuadtree.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 import org.deegree.model.spatialschema.Point;
052
053 /**
054 * <code>MemPointQuadtree</code> is a memory based quadtree implementation for points.
055 *
056 * @author <a href="mailto:schmitz@lat-lon.de">Andreas Schmitz</a>
057 * @author last edited by: $Author: apoth $
058 *
059 * @version 2.0, $Revision: 9342 $, $Date: 2007-12-27 13:32:57 +0100 (Do, 27 Dez 2007) $
060 * @param <T> the datatype to be used as id
061 *
062 * @since 2.0
063 */
064
065 public class MemPointQuadtree<T> implements Quadtree<T> {
066
067 private MemPointNode<T> root;
068
069 private double accuracyX = 0.0001;
070
071 private double accuracyY = 0.0001;
072
073 int maxDepth = 8;
074
075 /**
076 * Creates a new instance with the specified region. This envelope cannot be changed.
077 *
078 * @param region
079 */
080 public MemPointQuadtree( Envelope region ) {
081 root = new MemPointNode<T>( this, region, 0 );
082 }
083
084 /**
085 * Creates a new instance with the specified region. This envelope cannot be changed.
086 *
087 * @param region
088 * @param accuracyX
089 * @param accuracyY
090 */
091 public MemPointQuadtree( Envelope region, double accuracyX, double accuracyY ) {
092 root = new MemPointNode<T>( this, region, 0 );
093 this.accuracyX = accuracyX;
094 this.accuracyY = accuracyY;
095 }
096
097 /**
098 * Inserts the item with the envelope into the quadtree.
099 *
100 * @param item
101 * @param envelope
102 */
103 public void insert( T item, Envelope envelope )
104 throws IndexException {
105 root.insert( item, envelope );
106 }
107
108 /**
109 * Inserts the item with the given point as envelope.
110 *
111 * @param item
112 * @param point
113 */
114 public void insert( T item, Point point )
115 throws IndexException {
116 Envelope envelope = GeometryFactory.createEnvelope( point.getX() - accuracyX,
117 point.getY() - accuracyY,
118 point.getX() + accuracyX,
119 point.getY() + accuracyY,
120 null );
121 root.insert( item, envelope );
122 }
123
124 /**
125 * Searches for all items intersecting with the envelope.
126 *
127 * @param envelope
128 * @return a list with the resulting items
129 */
130 public List<T> query( Envelope envelope )
131 throws IndexException {
132 return root.query( envelope, new ArrayList<T>( 1000 ), 0 );
133 }
134
135 /**
136 * Deletes the item from the quadtree. Untested method!
137 *
138 * @param item
139 * the item to be deleted
140 * @throws IndexException
141 */
142 public void deleteItem( T item ) throws IndexException {
143 root.delete( item, root.getEnvelope() );
144 }
145
146 /**
147 * Deletes all items intersecting the envelope. Untested method!
148 *
149 * @param envelope
150 */
151 public void deleteRange( Envelope envelope ) {
152 root.deleteRange( envelope );
153 }
154
155 /**
156 * @return the deepest level of this subtree
157 */
158 public int getDepth() {
159 return root.getDepth();
160 }
161
162 /**
163 * @return the root bounding box
164 */
165 public Envelope getRootBoundingBox()
166 throws IndexException {
167 return root.getEnvelope();
168 }
169
170 public void update( T item, Envelope newBBox ) {
171 throw new UnsupportedOperationException( "This method is not implemented for the mempoint quatree, maybe use a delete and insert combination?" );
172 }
173
174 }