root / tags / v1_0_2_Build_900 / libraries / libFMap / src / com / iver / cit / gvsig / fmap / spatialindex / QuadtreeGt2.java @ 10562
History | View | Annotate | Download (9.68 KB)
1 | 5417 | azabala | /*
|
---|---|---|---|
2 | * Created on 16-may-2006
|
||
3 | *
|
||
4 | * gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana
|
||
5 | *
|
||
6 | * Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.
|
||
7 | *
|
||
8 | * This program is free software; you can redistribute it and/or
|
||
9 | * modify it under the terms of the GNU General Public License
|
||
10 | * as published by the Free Software Foundation; either version 2
|
||
11 | * of the License, or (at your option) any later version.
|
||
12 | *
|
||
13 | * This program is distributed in the hope that it will be useful,
|
||
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
16 | * GNU General Public License for more details.
|
||
17 | *
|
||
18 | * You should have received a copy of the GNU General Public License
|
||
19 | * along with this program; if not, write to the Free Software
|
||
20 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
||
21 | *
|
||
22 | * For more information, contact:
|
||
23 | *
|
||
24 | * Generalitat Valenciana
|
||
25 | * Conselleria d'Infraestructures i Transport
|
||
26 | * Av. Blasco Ib??ez, 50
|
||
27 | * 46010 VALENCIA
|
||
28 | * SPAIN
|
||
29 | *
|
||
30 | * +34 963862235
|
||
31 | * gvsig@gva.es
|
||
32 | * www.gvsig.gva.es
|
||
33 | *
|
||
34 | * or
|
||
35 | *
|
||
36 | * IVER T.I. S.A
|
||
37 | * Salamanca 50
|
||
38 | * 46005 Valencia
|
||
39 | * Spain
|
||
40 | *
|
||
41 | * +34 963163400
|
||
42 | * dac@iver.es
|
||
43 | */
|
||
44 | /* CVS MESSAGES:
|
||
45 | *
|
||
46 | * $Id$
|
||
47 | * $Log$
|
||
48 | 9108 | azabala | * Revision 1.1.6.1 2006-11-29 19:22:25 azabala
|
49 | * bug fixed with envelopes that are similar -or greater- to the full extent of a layer
|
||
50 | *
|
||
51 | * Revision 1.1 2006/05/24 21:58:04 azabala
|
||
52 | 5417 | azabala | * *** empty log message ***
|
53 | *
|
||
54 | *
|
||
55 | */
|
||
56 | package com.iver.cit.gvsig.fmap.spatialindex; |
||
57 | |||
58 | import java.awt.geom.Rectangle2D; |
||
59 | import java.io.File; |
||
60 | import java.io.IOException; |
||
61 | import java.util.ArrayList; |
||
62 | import java.util.Collection; |
||
63 | import java.util.List; |
||
64 | import java.util.Stack; |
||
65 | |||
66 | import org.geotools.data.DataSourceException; |
||
67 | import org.geotools.index.TreeException; |
||
68 | import org.geotools.index.quadtree.Node; |
||
69 | import org.geotools.index.quadtree.QuadTree; |
||
70 | import org.geotools.index.quadtree.StoreException; |
||
71 | import org.geotools.index.quadtree.fs.FileSystemIndexStore; |
||
72 | import org.geotools.index.quadtree.fs.IndexHeader; |
||
73 | |||
74 | import com.vividsolutions.jts.geom.Envelope; |
||
75 | /**
|
||
76 | * This Quadtree spatial index implementation is based
|
||
77 | * in a fork of org.geotools.index.quadtree.Quadtree implementation.
|
||
78 | * <br>
|
||
79 | * This implementation offers us:
|
||
80 | * <ol>
|
||
81 | * <li>Persistence of spatial index</li>
|
||
82 | * </ol>
|
||
83 | * We had to fork geotools quadtree for many reasons:
|
||
84 | * <ol>
|
||
85 | * <li>It was strongly dependent of SHP format, so it returned not only
|
||
86 | * a num of rectangle, it also returned byte offset of this rectangle in shp file</li>
|
||
87 | * <li>
|
||
88 | * Query artifact wasnt run well at all
|
||
89 | * </li>
|
||
90 | * </ol>
|
||
91 | * @author azabala
|
||
92 | *
|
||
93 | */
|
||
94 | public class QuadtreeGt2 implements IPersistentSpatialIndex { |
||
95 | /**
|
||
96 | * Geotools quadtree implementation
|
||
97 | */
|
||
98 | QuadTree quadtree; |
||
99 | /**
|
||
100 | * Persistent storage
|
||
101 | */
|
||
102 | String quadtreeFile;
|
||
103 | /**
|
||
104 | * Spatial index file extension
|
||
105 | */
|
||
106 | final String qExt = ".qix"; |
||
107 | /**
|
||
108 | * qix format has many versions, and allows
|
||
109 | * different byte orders.
|
||
110 | */
|
||
111 | String byteOrder;
|
||
112 | /**
|
||
113 | * Bounds of the layer to index
|
||
114 | */
|
||
115 | Envelope bounds; |
||
116 | /**
|
||
117 | * Number of records of the layer to index
|
||
118 | */
|
||
119 | int numRecs = 0; |
||
120 | |||
121 | boolean inMemory = false; |
||
122 | /**
|
||
123 | * Constructor.
|
||
124 | * You must say a qix file path, and if you want to overwrite this file
|
||
125 | * if exists. Also, you must specify how many geometries are going to index,
|
||
126 | * and the bounding box of all the geometries.
|
||
127 | *
|
||
128 | *
|
||
129 | * @param quadtreeFile qix file path
|
||
130 | * @param byteOrder byte order (bigendian, etc)
|
||
131 | * @param bounds Rectangle2D of all the geometries to index
|
||
132 | * @param numRecords num of geometries to index
|
||
133 | * @param overwrite if we want to overwrite a possible existing qix file
|
||
134 | * @throws SpatialIndexException
|
||
135 | */
|
||
136 | public QuadtreeGt2(String quadtreeFile, |
||
137 | String byteOrder,
|
||
138 | Rectangle2D bounds,
|
||
139 | int numRecords,
|
||
140 | boolean overwrite) throws SpatialIndexException{ |
||
141 | |||
142 | this.quadtreeFile = quadtreeFile + qExt;
|
||
143 | this.byteOrder = byteOrder;
|
||
144 | this.bounds = toJtsEnvelope(bounds);
|
||
145 | this.numRecs = numRecords;
|
||
146 | |||
147 | if(exists()){
|
||
148 | if(!overwrite){
|
||
149 | load(); |
||
150 | return;
|
||
151 | } |
||
152 | } |
||
153 | quadtree = new QuadTree(numRecs, this.bounds); |
||
154 | } |
||
155 | |||
156 | /**
|
||
157 | * If the spatial index file exists and has content
|
||
158 | */
|
||
159 | public boolean exists(){ |
||
160 | return (new File(quadtreeFile).length() != 0); |
||
161 | } |
||
162 | |||
163 | public void load() throws SpatialIndexException{ |
||
164 | try {
|
||
165 | // openQuadTreeInMemory();
|
||
166 | openQuadTree(); |
||
167 | } catch (StoreException e) {
|
||
168 | throw new SpatialIndexException("Error al cargar el fichero qix", e); |
||
169 | } |
||
170 | |||
171 | } |
||
172 | |||
173 | |||
174 | public List query(Rectangle2D rect) { |
||
175 | try {
|
||
176 | return (List) queryQuadTree(toJtsEnvelope(rect)); |
||
177 | } catch (IOException e) { |
||
178 | // TODO Auto-generated catch block
|
||
179 | e.printStackTrace(); |
||
180 | } catch (TreeException e) {
|
||
181 | // TODO Auto-generated catch block
|
||
182 | e.printStackTrace(); |
||
183 | } catch (StoreException e) {
|
||
184 | // TODO Auto-generated catch block
|
||
185 | e.printStackTrace(); |
||
186 | } |
||
187 | return new ArrayList(); |
||
188 | } |
||
189 | |||
190 | |||
191 | public void insert(Rectangle2D rect, int index) { |
||
192 | try {
|
||
193 | quadtree.insert(index, toJtsEnvelope(rect)); |
||
194 | } catch (StoreException e) {
|
||
195 | // TODO Auto-generated catch block
|
||
196 | e.printStackTrace(); |
||
197 | } |
||
198 | } |
||
199 | |||
200 | public Envelope toJtsEnvelope(Rectangle2D rect){ |
||
201 | double xmin = rect.getMinX();
|
||
202 | double xmax = rect.getMaxX();
|
||
203 | double ymin = rect.getMinY();
|
||
204 | double ymax = rect.getMaxY();
|
||
205 | return new Envelope(xmin, xmax, ymin, ymax); |
||
206 | } |
||
207 | |||
208 | |||
209 | public void delete(Rectangle2D rect, int index) { |
||
210 | if(inMemory)
|
||
211 | quadtree.delete(toJtsEnvelope(rect), index); |
||
212 | } |
||
213 | |||
214 | void openQuadTree() throws StoreException{ |
||
215 | if (quadtree == null) { |
||
216 | File file = new File(quadtreeFile); |
||
217 | //Intento de cargar todo el quadtree en memoria
|
||
218 | FileSystemIndexStore store = new FileSystemIndexStore(file);
|
||
219 | quadtree = store.load(); |
||
220 | } |
||
221 | } |
||
222 | |||
223 | void openQuadTreeInMemory() throws StoreException { |
||
224 | if (quadtree == null) { |
||
225 | File file = new File(quadtreeFile); |
||
226 | //Intento de cargar todo el quadtree en memoria
|
||
227 | FileSystemIndexStore store = new FileSystemIndexStore(file);
|
||
228 | QuadTree filequadtree = store.load(); |
||
229 | quadtree = new QuadTree(filequadtree.getNumShapes(),
|
||
230 | filequadtree.getMaxDepth(), |
||
231 | filequadtree.getRoot().getBounds()); |
||
232 | Stack nodes = new Stack(); |
||
233 | nodes.push(filequadtree.getRoot()); |
||
234 | while(nodes.size() != 0){ |
||
235 | Node node = (Node) nodes.pop(); |
||
236 | Envelope nodeEnv = node.getBounds(); |
||
237 | int[] shapeIds = node.getShapesId(); |
||
238 | for(int i = 0; i < shapeIds.length; i++){ |
||
239 | quadtree.insert(shapeIds[i], nodeEnv); |
||
240 | } |
||
241 | int numSubnodes = node.getNumSubNodes();
|
||
242 | for(int i = 0; i < numSubnodes; i++){ |
||
243 | nodes.push(node.getSubNode(i)); |
||
244 | } |
||
245 | }//while
|
||
246 | filequadtree.close(); |
||
247 | } |
||
248 | } |
||
249 | |||
250 | /**
|
||
251 | * QuadTree Query
|
||
252 | *
|
||
253 | * @param bbox
|
||
254 | *
|
||
255 | * @return
|
||
256 | *
|
||
257 | * @throws DataSourceException
|
||
258 | * @throws IOException
|
||
259 | * @throws TreeException
|
||
260 | * DOCUMENT ME!
|
||
261 | * @throws StoreException
|
||
262 | */
|
||
263 | private Collection queryQuadTree(Envelope bbox) throws |
||
264 | IOException, TreeException, StoreException {
|
||
265 | |||
266 | List solution = null; |
||
267 | 9108 | azabala | if ((quadtree != null) ) { |
268 | 5417 | azabala | solution = quadtree.query(bbox); |
269 | // tmp = quadtree.search(bbox);
|
||
270 | // if( tmp==null || !tmp.isEmpty())
|
||
271 | // return tmp;
|
||
272 | |||
273 | }else
|
||
274 | solution = new ArrayList(); |
||
275 | // if( quadtree!=null )
|
||
276 | // quadtree.close();
|
||
277 | // return null;
|
||
278 | return solution;
|
||
279 | } |
||
280 | |||
281 | public void flush() { |
||
282 | byte order = 0; |
||
283 | if ((byteOrder == null) || byteOrder.equalsIgnoreCase("NM")) { |
||
284 | order = IndexHeader.NEW_MSB_ORDER; |
||
285 | } else if (byteOrder.equalsIgnoreCase("NL")) { |
||
286 | order = IndexHeader.NEW_LSB_ORDER; |
||
287 | } |
||
288 | File file = new File(quadtreeFile); |
||
289 | FileSystemIndexStore store = new FileSystemIndexStore(file, order);
|
||
290 | try {
|
||
291 | store.store(quadtree); |
||
292 | } catch (StoreException e) {
|
||
293 | // TODO Auto-generated catch block
|
||
294 | e.printStackTrace(); |
||
295 | } |
||
296 | } |
||
297 | |||
298 | public void close() { |
||
299 | try {
|
||
300 | quadtree.close(); |
||
301 | } catch (StoreException e) {
|
||
302 | // TODO Auto-generated catch block
|
||
303 | e.printStackTrace(); |
||
304 | } |
||
305 | } |
||
306 | |||
307 | |||
308 | |||
309 | |||
310 | |||
311 | // private void buildQuadTree() throws TreeException {
|
||
312 | // ShapeFileIndexer indexer = new ShapeFileIndexer();
|
||
313 | // indexer.setIdxType(ShapeFileIndexer.QUADTREE);
|
||
314 | // indexer.setShapeFileName(shpURL.getPath());
|
||
315 | //
|
||
316 | // try {
|
||
317 | // indexer.index(false, readWriteLock);
|
||
318 | // } catch (MalformedURLException e) {
|
||
319 | // throw new TreeException(e);
|
||
320 | // } catch (LockTimeoutException e) {
|
||
321 | // throw new TreeException(e);
|
||
322 | // } catch (Exception e) {
|
||
323 | // File f = new File(treeURL.getPath());
|
||
324 | //
|
||
325 | // if (f.exists()) {
|
||
326 | // f.delete();
|
||
327 | // }
|
||
328 | //
|
||
329 | // if (e instanceof TreeException) {
|
||
330 | // throw (TreeException) e;
|
||
331 | // } else {
|
||
332 | // throw new TreeException(e);
|
||
333 | // }
|
||
334 | // }
|
||
335 | // }
|
||
336 | } |
||
337 | |||
338 | |||
339 | |||
340 | |||
341 | /**
|
||
342 | private int buildRTree(ShapefileReader reader, File rtreeFile,
|
||
343 | boolean verbose)
|
||
344 | throws TreeException, LockTimeoutException, IOException {
|
||
345 | DataDefinition keyDef = new DataDefinition("US-ASCII");
|
||
346 | keyDef.addField(Integer.class);
|
||
347 | keyDef.addField(Long.class);
|
||
348 | |||
349 | FileSystemPageStore fps = new FileSystemPageStore(rtreeFile, keyDef,
|
||
350 | this.max, this.min, this.split);
|
||
351 | org.geotools.index.rtree.RTree rtree = new org.geotools.index.rtree.RTree(fps);
|
||
352 | Record record = null;
|
||
353 | Data data = null;
|
||
354 | |||
355 | int cnt = 0;
|
||
356 | |||
357 | while (reader.hasNext()) {
|
||
358 | record = reader.nextRecord();
|
||
359 | data = new Data(keyDef);
|
||
360 | |||
361 | //Aqu? estamos indexando a partir del n?mero de rectangulo
|
||
362 | //luego creo que el segundo valor lo podemos obviar.
|
||
363 | data.addValue(new Integer(++cnt));
|
||
364 | data.addValue(new Long(record.offset()));
|
||
365 | |||
366 | rtree.insert(new Envelope(record.minX, record.maxX, record.minY,
|
||
367 | record.maxY), data);
|
||
368 | |||
369 | if (verbose && ((cnt % 500) == 0)) {
|
||
370 | System.out.print('.');
|
||
371 | }
|
||
372 | }
|
||
373 | |||
374 | rtree.close();
|
||
375 | |||
376 | return cnt;
|
||
377 | }
|
||
378 | */
|