001: /*
002: * This file is part of the GeOxygene project source files.
003: *
004: * GeOxygene aims at providing an open framework which implements OGC/ISO specifications for
005: * the development and deployment of geographic (GIS) applications. It is a open source
006: * contribution of the COGIT laboratory at the Institut Géographique National (the French
007: * National Mapping Agency).
008: *
009: * See: http://oxygene-project.sourceforge.net
010: *
011: * Copyright (C) 2005 Institut Géographique National
012: *
013: * This library is free software; you can redistribute it and/or modify it under the terms
014: * of the GNU Lesser General Public License as published by the Free Software Foundation;
015: * either version 2.1 of the License, or any later version.
016: *
017: * This library is distributed in the hope that it will be useful, but WITHOUT ANY
018: * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
019: * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
020: *
021: * You should have received a copy of the GNU Lesser General Public License along with
022: * this library (see file LICENSE if present); if not, write to the Free Software
023: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
024: *
025: */
026:
027: package fr.ign.cogit.geoxygene.util.index;
028:
029: import java.util.ArrayList;
030: import java.util.HashSet;
031: import java.util.Iterator;
032: import java.util.List;
033: import java.util.Set;
034:
035: import fr.ign.cogit.geoxygene.feature.FT_Feature;
036: import fr.ign.cogit.geoxygene.feature.FT_FeatureCollection;
037: import fr.ign.cogit.geoxygene.spatial.coordgeom.DirectPosition;
038: import fr.ign.cogit.geoxygene.spatial.coordgeom.GM_Envelope;
039: import fr.ign.cogit.geoxygene.spatial.coordgeom.GM_Polygon;
040: import fr.ign.cogit.geoxygene.spatial.geomprim.GM_Point;
041: import fr.ign.cogit.geoxygene.spatial.geomroot.GM_Object;
042:
043: /**
044: * Index spatial par simple dallage.
045: *
046: * @author Thierry Badard, Arnaud Braun & Sébastien Mustière
047: * @version 1.0
048: */
049:
050: public class Tiling implements SpatialIndex {
051:
052: // ===============================================
053: /** Renvoie les paramètres du dallage.
054: *
055: * ArrayList de 4 éléments:
056: * - 1er élément : Class égal à Dallage.class
057: * - 2ème élément : Boolean indiquant si l'index est en mode MAJ automatique ou non
058: * - 3ème élément : GM_Envelope décrivant les limites de la zone couverte
059: * - 4ème élément : Integer exprimant le nombre de cases en X et Y.
060: *
061: *
062: */
063: public List getParametres() {
064: List param = new ArrayList();
065: param.add(Tiling.class);
066: param.add(new Boolean(automaticUpdate));
067: param.add(new GM_Envelope(xmin, xmax, ymin, ymax));
068: param.add(new Integer(size));
069: return param;
070: }
071:
072: // ===============================================
073: /** Tableau de collections de features appartenant a chaque dalle.
074: * Un feature peut appartenir a plusieurs dalles. */
075: private Set[][] index;
076:
077: // ===============================================
078: /** Taille du dallage (nombre de rectangles par cote). */
079: private int size;
080:
081: /** Taille du dallage (nombre de rectangles par cote). */
082: public int getSize() {
083: return size;
084: }
085:
086: // xmin, xmax, ymin, ymax
087: /** paramètre interne du dallage */
088: private double xmin;
089: /** paramètre interne du dallage */
090: private double xmax;
091: /** paramètre interne du dallage */
092: private double ymin;
093: /** paramètre interne du dallage */
094: private double ymax;
095:
096: // calcul de dX et dY
097: /** paramètre interne du dallage */
098: private double dX;
099: /** paramètre interne du dallage */
100: private double dY;
101:
102: /** Tableau à deux dimensions des dalles sous forme de Polygones. */
103: private GM_Polygon[][] dallesPolygones;
104:
105: // ===============================================
106: /** Indique si l'on a demande une mise a jour automatique. */
107: private boolean automaticUpdate;
108:
109: /** Indique si l'on a demande une mise a jour automatique. */
110: public boolean hasAutomaticUpdate() {
111: return automaticUpdate;
112: }
113:
114: /** Demande une mise a jour automatique.
115: * NB: Cette méthode ne fait pas les éventuelles MAJ qui
116: * auriant ête faites alors que le mode MAJ automatique n'était
117: * pas activé.
118: */
119: public void setAutomaticUpdate(boolean auto) {
120: automaticUpdate = auto;
121: }
122:
123: // ===============================================
124: /** Tableau à deux dimensions des dalles. */
125: private GM_Envelope[][] dallage;
126:
127: /** Renvoie le tableau à 2 dimensions des dalles. */
128: public GM_Envelope[][] getDallage() {
129: return dallage;
130: }
131:
132: /** renvoie la dalle d'indice i,j. */
133: public GM_Envelope getDallage(int i, int j) {
134: return dallage[i][j];
135: }
136:
137: /** Tableau des dalles contenant le feature. */
138: public GM_Envelope[] getDallage(FT_Feature feat) {
139: List result = new ArrayList();
140: for (int i = 0; i < size; i++)
141: for (int j = 0; j < size; j++)
142: if (index[i][j].contains(feat))
143: result.add(dallage[i][j]);
144: GM_Envelope[] array = new GM_Envelope[result.size()];
145: for (int k = 0; k < result.size(); k++)
146: array[k] = (GM_Envelope) result.get(k);
147: return array;
148: }
149:
150: /** Tableau des numéros des dalles contenant le feature. */
151: public List getNumDallage(FT_Feature feat) {
152: List result = new ArrayList();
153: for (int i = 0; i < size; i++) {
154: for (int j = 0; j < size; j++) {
155: if (index[i][j].contains(feat)) {
156: List couple = new ArrayList();
157: couple.add(new Integer(i));
158: couple.add(new Integer(j));
159: result.add(couple);
160: }
161: }
162: }
163: return result;
164: }
165:
166: /** Dalle couvrant le point passe en parametre.
167: * Renvoie NULL si aucune dalle ne couvre ce point.*/
168: public GM_Envelope getDallage(DirectPosition dp) {
169: for (int i = 0; i < size; i++)
170: for (int j = 0; j < size; j++)
171: if (dallage[i][j].contains(dp))
172: return dallage[i][j];
173: return null;
174: }
175:
176: /** Etant donné une enveloppe, renvoie les indices min et max des
177: * dalles qui intersectent cette enveloppe
178: * (dans l'ordre: imin, imax, jmin, jmax)
179: */
180: private int[] dallesIntersectees(GM_Envelope env) {
181: int i, imin = 0, imax = size - 1, jmin = 0, jmax = size - 1;
182: boolean min = true;
183: for (i = 0; i < size; i++) {
184: if (min) {
185: if (env.getLowerCorner().getX() <= dallage[i][0]
186: .getUpperCorner().getX()) {
187: imin = i;
188: min = false;
189: }
190: }
191: if (!min) {
192: if (env.getUpperCorner().getX() <= dallage[i][0]
193: .getUpperCorner().getX()) {
194: imax = i;
195: break;
196: }
197: }
198: }
199: min = true;
200: for (i = 0; i < size; i++) {
201: if (min) {
202: if (env.getLowerCorner().getY() <= dallage[0][i]
203: .getUpperCorner().getY()) {
204: jmin = i;
205: min = false;
206: }
207: }
208: if (!min) {
209: if (env.getUpperCorner().getY() <= dallage[0][i]
210: .getUpperCorner().getY()) {
211: jmax = i;
212: break;
213: }
214: }
215: }
216: int tab[] = { imin, imax, jmin, jmax };
217: return tab;
218:
219: /* AUTRE METHODE POSSIBLE POUR FAIRE LA MEME CHOSE MAIS BIZARREMENT CA A L'AIR MOINS RAPIDE
220: int imin, imax, jmin, jmax;
221: double imind, jmind, imindf, imaxdf,jmindf,jmaxdf;
222:
223: imind = (env.getLowerCorner().getX()-xmin)/dX;
224: imindf = Math.floor(imind);
225: if (imindf == imind ) {if (imindf != 0) imindf = imindf -1;}
226: imin = (new Double(imindf)).intValue();
227:
228: imaxdf = Math.floor((env.getUpperCorner().getX()-xmin)/dX);
229: if ( imaxdf == size ) imaxdf = size-1;
230: imax = (new Double(imaxdf)).intValue();
231:
232: jmind = (env.getLowerCorner().getY()-ymin)/dY;
233: jmindf = Math.floor(jmind);
234: if (jmindf == jmind ) {if (jmindf != 0) jmindf = jmindf -1;}
235: jmin = (new Double(jmindf)).intValue();
236:
237: jmaxdf = Math.floor((env.getUpperCorner().getY()-ymin)/dY);
238: if ( jmaxdf == size ) jmaxdf = size-1;
239: jmax = (new Double(jmaxdf)).intValue();
240: */
241: }
242:
243: // ===============================================
244: /** Features appartenant a la dalle d'indice i,j.*/
245: public FT_FeatureCollection select(int i, int j) {
246: return new FT_FeatureCollection(index[i][j]);
247: }
248:
249: // ===============================================
250: /** Selection a l'aide d'un rectangle. */
251: public FT_FeatureCollection select(GM_Envelope env) {
252: int tab[];
253: Set result = new HashSet();
254: GM_Object geometry = new GM_Polygon(env);
255: if (env.getUpperCorner().getX() == env.getLowerCorner().getX())
256: if (env.getUpperCorner().getY() == env.getLowerCorner()
257: .getY())
258: geometry = new GM_Point(env.getUpperCorner());
259:
260: tab = this .dallesIntersectees(env);
261: for (int i = tab[0]; i <= tab[1]; i++) {
262: for (int j = tab[2]; j <= tab[3]; j++) {
263: Iterator it = index[i][j].iterator();
264: while (it.hasNext()) {
265: FT_Feature feature = (FT_Feature) it.next();
266: GM_Object geom = feature.getGeom();
267: GM_Envelope envCourante = geom.envelope();
268: if (env.overlaps(envCourante))
269: if (geometry.intersects(geom))
270: result.add(feature);
271: }
272: }
273: }
274: FT_FeatureCollection collectionresult = new FT_FeatureCollection();
275: collectionresult.setElements(new ArrayList(result));
276: return collectionresult;
277: }
278:
279: // ===============================================
280: /** Selection dans le carre dont P est le centre, de cote D.
281: * NB: D peut être nul.*/
282: public FT_FeatureCollection select(DirectPosition P, double D) {
283: return select(new GM_Envelope(P, D));
284: }
285:
286: // ===============================================
287: /** Selection des objets qui intersectent un objet geometrique quelconque. */
288: public FT_FeatureCollection select(GM_Object geometry) {
289: int tab[];
290: Set result = new HashSet();
291: GM_Envelope envGeometry = geometry.envelope();
292: tab = this .dallesIntersectees(envGeometry);
293: for (int i = tab[0]; i <= tab[1]; i++) {
294: for (int j = tab[2]; j <= tab[3]; j++) {
295: if (geometry.intersects(dallesPolygones[i][j])) {
296: Iterator it = index[i][j].iterator();
297: while (it.hasNext()) {
298: FT_Feature feature = (FT_Feature) it.next();
299: GM_Object geom = feature.getGeom();
300: GM_Envelope envCourante = geom.envelope();
301: if (envGeometry.overlaps(envCourante))
302: if (geometry.intersects(geom))
303: result.add(feature);
304: }
305: }
306: }
307: }
308: FT_FeatureCollection collectionresult = new FT_FeatureCollection();
309: collectionresult.setElements(new ArrayList(result));
310: return collectionresult;
311: }
312:
313: /** Selection des objets qui croisent ou intersectent un objet geometrique quelconque.
314: *
315: * @param strictlyCrosses
316: * Si c'est TRUE : ne retient que les objets qui croisent (CROSS au sens JTS)
317: * Si c'est FALSE : ne retient que les objets qui intersectent (INTERSECT au sens JTS)
318: * Exemple : si 1 ligne touche "geometry" juste sur une extrémité,
319: * alors avec TRUE cela ne renvoie pas la ligne, avec FALSE cela la renvoie
320: */
321: public FT_FeatureCollection select(GM_Object geometry,
322: boolean strictlyCrosses) {
323: int tab[];
324: Set result = new HashSet();
325: GM_Envelope envGeometry = geometry.envelope();
326: tab = this .dallesIntersectees(envGeometry);
327: for (int i = tab[0]; i <= tab[1]; i++) {
328: for (int j = tab[2]; j <= tab[3]; j++) {
329: if (!geometry.intersects(dallesPolygones[i][j]))
330: continue;
331: Iterator it = index[i][j].iterator();
332: while (it.hasNext()) {
333: FT_Feature feature = (FT_Feature) it.next();
334: GM_Object geom = feature.getGeom();
335: GM_Envelope envCourante = geom.envelope();
336: if (envGeometry.overlaps(envCourante))
337: if (strictlyCrosses) {
338: if (geometry.crosses(geom))
339: result.add(feature);
340: } else if (geometry.intersects(geom))
341: result.add(feature);
342: }
343: }
344: }
345: FT_FeatureCollection collectionresult = new FT_FeatureCollection();
346: collectionresult.setElements(new ArrayList(result));
347: return collectionresult;
348: }
349:
350: // ===============================================
351: /** Selection a l'aide d'un objet geometrique quelconque et d'une distance.
352: * NB: D peut être nul.*/
353: public FT_FeatureCollection select(GM_Object geometry,
354: double distance) {
355: if (distance == 0)
356: return select(geometry);
357: return select(geometry.buffer(distance));
358: }
359:
360: // ===============================================
361: // CONSTRUCTEURS
362: // ===============================================
363:
364: /** Crée et instancie un dallage d'une collection de FT_Feature,
365: * en fonction des limites de la zone
366: * et du nombre de cases souhaitées sur la zone.
367: *
368: * @param fc
369: * La liste de Features à indexer
370: *
371: * @param automaticUpd
372: * Spéciifie si l'index doit être mis à jour automatiquement
373: * quand on modifie les objets de fc
374: *
375: * @param envelope
376: * Enveloppe décrivant les limites de l'index spatial.
377: * NB: Tout objet hors de ces limites ne sera pas traité lors des requêtes spatiales !!!!!
378: *
379: * @param n
380: * Nombre de dalles en X et en Y, du dallage.
381: */
382: public Tiling(FT_FeatureCollection fc, Boolean automaticUpd,
383: GM_Envelope envelope, Integer n) {
384: int tab[];
385: // initialisation des variables
386: size = n.intValue();
387: dallage = new GM_Envelope[size][size];
388: automaticUpdate = automaticUpd.booleanValue();
389: index = new Set[size][size];
390: for (int i = 0; i < size; i++)
391: for (int j = 0; j < size; j++)
392: index[i][j] = new HashSet();
393:
394: // xmin, xmax, ymin, ymax
395: xmin = envelope.minX();
396: xmax = envelope.maxX();
397: ymin = envelope.minY();
398: ymax = envelope.maxY();
399:
400: // calcul de dX et dY
401: dX = (xmax - xmin) / size;
402: dY = (ymax - ymin) / size;
403:
404: // ecriture des dalles
405: for (int i = 0; i < size; i++) {
406: for (int j = 0; j < size; j++) {
407: GM_Envelope env = new GM_Envelope();
408: env.setLowerCorner(new DirectPosition(xmin + (i * dX),
409: ymin + (j * dY)));
410: env.setUpperCorner(new DirectPosition(xmin
411: + ((i + 1) * dX), ymin + ((j + 1) * dY)));
412: dallage[i][j] = env;
413: }
414: }
415:
416: // initialisation d'un tableau de polygones
417: dallesPolygones = new GM_Polygon[size][size];
418: for (int i = 0; i < size; i++) {
419: for (int j = 0; j < size; j++) {
420: dallesPolygones[i][j] = new GM_Polygon(dallage[i][j]);
421: }
422: }
423:
424: // calcul de l'index
425: fc.initIterator();
426: while (fc.hasNext()) {
427: FT_Feature feature = fc.next();
428: GM_Object geom = feature.getGeom();
429: GM_Envelope envObjet = geom.envelope();
430: tab = this .dallesIntersectees(envObjet);
431: for (int i = tab[0]; i <= tab[1]; i++) {
432: for (int j = tab[2]; j <= tab[3]; j++) {
433: if (geom.intersects(dallesPolygones[i][j])) {
434: index[i][j].add(feature);
435: }
436: }
437: }
438: }
439: }
440:
441: /** Crée et instancie un dallage d'une collection de FT_Feature,
442: * en fonction du nombre de cases souhaitées sur la zone.
443: * NB: les limites de la zone de l'index sont celles de la collection traitée.
444: * Il est donc impossible de rajouter ensuite dans la collection un objet
445: * en dehors de cette zone.
446: *
447: * @param fc
448: * La liste de Features à indexer
449: *
450: * @param automaticUpd
451: * Spéciifie si l'index doit être mis à jour automatiquement
452: * quand on modifie les objets de fc
453: *
454: * @param n
455: * Nombre de dalles en X et en Y, du dallage.
456: */
457: public Tiling(FT_FeatureCollection fc, Boolean automaticUpd,
458: Integer n) {
459: this (fc, automaticUpd, fc.envelope(), n);
460: }
461:
462: /** Crée et instancie un dallage d'une collection de FT_Feature.
463: * Les paramètres sont définis par la collection en entrée:
464: * 1/ Les limites de la zone de l'index sont celles de la collection traitée.
465: * Il est donc impossible de rajouter ensuite dans la collection un objet
466: * en dehors de cette zone.
467: * 2/ Le nombre de cases est défini automatiquement pour qu'il y ait
468: * de l'ordre de 50 objets par dalle en moyennne (approximatif)
469: *
470: * @param fc
471: * La liste de Features à indexer
472: *
473: * @param automaticUpd
474: * Spéciifie si l'index doit être mis à jour automatiquement
475: * quand on modifie les objets de fc
476: *
477: */
478: public Tiling(FT_FeatureCollection fc, Boolean automaticUpd) {
479: this (fc, automaticUpd, new Integer(nbDallesXY(fc)));
480: }
481:
482: private static int nbDallesXY(FT_FeatureCollection fc) {
483: int nb = (int) Math.sqrt(fc.size() / 50);
484: if (nb == 0)
485: nb = 1;
486: return nb;
487: }
488:
489: /** Crée et instancie un dallage en reprenant les paramètres d'un autre dallage.
490: */
491: public Tiling(FT_FeatureCollection fc, Tiling spIdx) {
492: this (fc, (Boolean) spIdx.getParametres().get(1),
493: (GM_Envelope) spIdx.getParametres().get(2),
494: (Integer) spIdx.getParametres().get(3));
495: }
496:
497: // ===============================================
498: // MISE A JOUR
499: // ===============================================
500:
501: /** Met a jour l'index avec le FT_Feature.
502: * Si cas vaut +1 : on ajoute le feature.
503: * Si cas vaut -1 : on enleve le feature.
504: * Si cas vaut 0 : on modifie le feature.*/
505: public void update(FT_Feature value, int cas) {
506: int tab[];
507: if (cas == 1) {
508: if (value == null)
509: return;
510: GM_Object geom = value.getGeom();
511: if (geom == null)
512: return;
513: GM_Envelope envObjet = geom.envelope();
514: tab = this .dallesIntersectees(envObjet);
515: for (int i = tab[0]; i <= tab[1]; i++) {
516: for (int j = tab[2]; j <= tab[3]; j++) {
517: if (geom.intersects(dallesPolygones[i][j])) {
518: index[i][j].add(value);
519: }
520: }
521: }
522: } else if (cas == -1) {
523: GM_Envelope[] envs = getDallage(value);
524: for (int k = 0; k < envs.length; k++) {
525: Iterator itDallesConcernees = this .getNumDallage(value)
526: .iterator();
527: while (itDallesConcernees.hasNext()) {
528: List num = (List) itDallesConcernees.next();
529: index[((Integer) num.get(0)).intValue()][((Integer) num
530: .get(1)).intValue()].remove(value);
531: }
532: }
533: } else if (cas == 0) {
534: this .update(value, -1);
535: this .update(value, +1);
536: } else {
537: System.out
538: .println("spatialIndex.update(value, cas) : \"cas\" doit valoir +1, -1 ou 0.");
539: }
540: }
541:
542: }
|