001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/tags/2.1/src/org/deegree/io/quadtree/MemPointQuadtree.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 import org.deegree.model.spatialschema.Point;
042
043 /**
044 * <code>MemPointQuadtree</code> is a memory based quadtree implementation for points.
045 *
046 * @author <a href="mailto:schmitz@lat-lon.de">Andreas Schmitz</a>
047 * @author last edited by: $Author: apoth $
048 *
049 * @version 2.0, $Revision: 6812 $, $Date: 2007-05-04 15:35:27 +0200 (Fr, 04 Mai 2007) $
050 *
051 * @since 2.0
052 */
053
054 public class MemPointQuadtree implements Quadtree {
055
056 private MemPointNode root;
057
058 private double accuracyX = 0.0001;
059
060 private double accuracyY = 0.0001;
061
062 int maxDepth = 8;
063
064 /**
065 * Creates a new instance with the specified region. This envelope cannot be changed.
066 *
067 * @param region
068 */
069 public MemPointQuadtree( Envelope region ) {
070 root = new MemPointNode( this, region, 0 );
071 }
072
073 /**
074 * Creates a new instance with the specified region. This envelope cannot be changed.
075 *
076 * @param region
077 * @param accuracyX
078 * @param accuracyY
079 */
080 public MemPointQuadtree( Envelope region, double accuracyX, double accuracyY ) {
081 root = new MemPointNode( this, region, 0 );
082 this.accuracyX = accuracyX;
083 this.accuracyY = accuracyY;
084 }
085
086 /**
087 * Inserts the item with the envelope into the quadtree.
088 *
089 * @param item
090 * @param envelope
091 */
092 public void insert( Object item, Envelope envelope )
093 throws IndexException {
094 root.insert( item, envelope );
095 }
096
097 /**
098 * Inserts the item with the given point as envelope.
099 *
100 * @param item
101 * @param point
102 */
103 public void insert( Object item, Point point )
104 throws IndexException {
105 Envelope envelope = GeometryFactory.createEnvelope( point.getX() - accuracyX, point.getY() - accuracyY,
106 point.getX() + accuracyX, point.getY() + accuracyY, null );
107 root.insert( item, envelope );
108 }
109
110 /**
111 * Searches for all items intersecting with the envelope.
112 *
113 * @param envelope
114 * @return a list with the resulting items
115 */
116 public List query( Envelope envelope )
117 throws IndexException {
118 return root.query( envelope, new ArrayList<Object>( 1000 ), 0 );
119 }
120
121 /**
122 * Deletes the item from the quadtree. Untested method!
123 *
124 * @param item
125 * the item to be deleted
126 */
127 public void deleteItem( Object item ) {
128 root.deleteItem( item );
129 }
130
131 /**
132 * Deletes all items intersecting the envelope. Untested method!
133 *
134 * @param envelope
135 */
136 public void deleteRange( Envelope envelope ) {
137 root.deleteRange( envelope );
138 }
139
140 /**
141 * @return the deepest level of this subtree
142 */
143 public int getDepth() {
144 return root.getDepth();
145 }
146
147 /**
148 * @return the root bounding box
149 */
150 public Envelope getRootBoundingBox()
151 throws IndexException {
152 return root.getEnvelope();
153 }
154
155 }