001 //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.3_testing/src/org/deegree/io/quadtree/MemPointQuadtree.java $
002 /*----------------------------------------------------------------------------
003 This file is part of deegree, http://deegree.org/
004 Copyright (C) 2001-2009 by:
005 Department of Geography, University of Bonn
006 and
007 lat/lon GmbH
008
009 This library is free software; you can redistribute it and/or modify it under
010 the terms of the GNU Lesser General Public License as published by the Free
011 Software Foundation; either version 2.1 of the License, or (at your option)
012 any later version.
013 This library is distributed in the hope that it will be useful, but WITHOUT
014 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
015 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
016 details.
017 You should have received a copy of the GNU Lesser General Public License
018 along with this library; if not, write to the Free Software Foundation, Inc.,
019 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020
021 Contact information:
022
023 lat/lon GmbH
024 Aennchenstr. 19, 53177 Bonn
025 Germany
026 http://lat-lon.de/
027
028 Department of Geography, University of Bonn
029 Prof. Dr. Klaus Greve
030 Postfach 1147, 53001 Bonn
031 Germany
032 http://www.geographie.uni-bonn.de/deegree/
033
034 e-mail: info@deegree.org
035 ----------------------------------------------------------------------------*/
036 package org.deegree.io.quadtree;
037
038 import java.util.ArrayList;
039 import java.util.List;
040
041 import org.deegree.model.spatialschema.Envelope;
042 import org.deegree.model.spatialschema.GeometryFactory;
043 import org.deegree.model.spatialschema.Point;
044
045 /**
046 * <code>MemPointQuadtree</code> is a memory based quadtree implementation for points.
047 *
048 * @author <a href="mailto:schmitz@lat-lon.de">Andreas Schmitz</a>
049 * @author last edited by: $Author: mschneider $
050 *
051 * @version 2.0, $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18. Jun 2009) $
052 * @param <T>
053 * the datatype to be used as id
054 *
055 * @since 2.0
056 */
057
058 public class MemPointQuadtree<T> implements Quadtree<T> {
059
060 private MemPointNode<T> root;
061
062 private double accuracyX = 0.0001;
063
064 private double accuracyY = 0.0001;
065
066 int maxDepth = 8;
067
068 /**
069 * Creates a new instance with the specified region. This envelope cannot be changed.
070 *
071 * @param region
072 */
073 public MemPointQuadtree( Envelope region ) {
074 root = new MemPointNode<T>( this, region, 0 );
075 }
076
077 /**
078 * Creates a new instance with the specified region. This envelope cannot be changed.
079 *
080 * @param region
081 * @param accuracyX
082 * @param accuracyY
083 */
084 public MemPointQuadtree( Envelope region, double accuracyX, double accuracyY ) {
085 root = new MemPointNode<T>( this, region, 0 );
086 this.accuracyX = accuracyX;
087 this.accuracyY = accuracyY;
088 }
089
090 /**
091 * Inserts the item with the envelope into the quadtree.
092 *
093 * @param item
094 * @param envelope
095 */
096 public void insert( T item, Envelope envelope )
097 throws IndexException {
098 root.insert( item, envelope );
099 }
100
101 /**
102 * Inserts the item with the given point as envelope.
103 *
104 * @param item
105 * @param point
106 */
107 public void insert( T item, Point point )
108 throws IndexException {
109 Envelope envelope = GeometryFactory.createEnvelope( point.getX() - accuracyX, point.getY() - accuracyY,
110 point.getX() + accuracyX, point.getY() + accuracyY, null );
111 root.insert( item, envelope );
112 }
113
114 /**
115 * Searches for all items intersecting with the envelope.
116 *
117 * @param envelope
118 * @return a list with the resulting items
119 */
120 public List<T> query( Envelope envelope )
121 throws IndexException {
122 return root.query( envelope, new ArrayList<T>( 1000 ), 0 );
123 }
124
125 /**
126 * Deletes the item from the quadtree. Untested method!
127 *
128 * @param item
129 * the item to be deleted
130 * @throws IndexException
131 */
132 public void deleteItem( T item )
133 throws IndexException {
134 root.delete( item, root.getEnvelope() );
135 }
136
137 /**
138 * Deletes all items intersecting the envelope. Untested method!
139 *
140 * @param envelope
141 */
142 public void deleteRange( Envelope envelope ) {
143 root.deleteRange( envelope );
144 }
145
146 /**
147 * @return the deepest level of this subtree
148 */
149 public int getDepth() {
150 return root.getDepth();
151 }
152
153 /**
154 * @return the root bounding box
155 */
156 public Envelope getRootBoundingBox()
157 throws IndexException {
158 return root.getEnvelope();
159 }
160
161 public void update( T item, Envelope newBBox ) {
162 throw new UnsupportedOperationException(
163 "This method is not implemented for the mempoint quatree, maybe use a delete and insert combination?" );
164 }
165
166 }