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.contrib.appariement.reseaux.topologie;
028:
029: import java.util.ArrayList;
030: import java.util.Collection;
031: import java.util.HashSet;
032: import java.util.Iterator;
033: import java.util.List;
034:
035: import fr.ign.cogit.geoxygene.contrib.appariement.EnsembleDeLiens;
036: import fr.ign.cogit.geoxygene.contrib.appariement.reseaux.LienReseaux;
037: import fr.ign.cogit.geoxygene.contrib.cartetopo.Arc;
038: import fr.ign.cogit.geoxygene.contrib.cartetopo.Groupe;
039: import fr.ign.cogit.geoxygene.contrib.cartetopo.Noeud;
040:
041: /**
042: * Noeud du reseau à apparier.
043: *
044: * @author Mustiere - IGN / Laboratoire COGIT
045: * @version 1.0
046: *
047: */
048:
049: public class NoeudApp extends Noeud {
050:
051: /** Rayon maximal sur le tarrain de l'objet correpondant au noeud
052: * (rayon de recherche pour l'appariement). */
053: private double taille = 0.0;
054:
055: public double getTaille() {
056: return taille;
057: }
058:
059: public void setTaille(double taille) {
060: this .taille = taille;
061: }
062:
063: /** Evaluation du résultat de l'appariement sur la face. */
064: private String resultatAppariement;
065:
066: public String getResultatAppariement() {
067: return resultatAppariement;
068: }
069:
070: public void setResultatAppariement(String resultat) {
071: resultatAppariement = resultat;
072: }
073:
074: /** Liens qui référencent les objets auquel l'arc est apparié dans un autre réseau. */
075: private List liens = new ArrayList();
076:
077: public List getLiens() {
078: return liens;
079: }
080:
081: public void setLiens(List liens) {
082: this .liens = liens;
083: }
084:
085: public void addLiens(LienReseaux liens) {
086: this .liens.add(liens);
087: }
088:
089: ////////////////////////////////////////////////////
090: // POUR MANIPULER LES LIENS
091: ////////////////////////////////////////////////////
092:
093: /** Renvoie les liens de l'objet qui appartiennent à la liste liensPertinents */
094: public List getLiens(List liensPertinents) {
095: List listeTmp = new ArrayList(this .getLiens());
096: listeTmp.retainAll(liensPertinents);
097: return listeTmp;
098: }
099:
100: /** Renvoie les liens concernant l'objet et portant le nom passé en paramètre.
101: * NB: renvoie une liste vide (et non "Null") si il n'y a pas de tels liens. */
102: public List retrouveLiens(String nom) {
103: List liens = new ArrayList();
104: List tousLiens = new ArrayList();
105:
106: tousLiens = this .getLiens();
107: Iterator it = tousLiens.iterator();
108: while (it.hasNext()) {
109: LienReseaux lien = (LienReseaux) it.next();
110: if (lien.getNom().compareToIgnoreCase(nom) == 0)
111: liens.add(lien);
112: }
113: return liens;
114: }
115:
116: /** Noeuds reliés à this par l'appariement passé en paramètre.
117: * La liste contient des NoeudComp. */
118: public List noeudsCompEnCorrespondance(EnsembleDeLiens liens) {
119: List noeuds = new ArrayList();
120: List liensOK = new ArrayList();
121: LienReseaux lien;
122: int i;
123:
124: liensOK = new ArrayList(this .getLiens());
125: liensOK.retainAll(liens.getElements());
126: for (i = 0; i < liensOK.size(); i++) {
127: lien = (LienReseaux) liensOK.get(i);
128: noeuds.addAll(lien.getNoeuds2());
129: }
130: return noeuds;
131: }
132:
133: /** Groupes reliés à this par l'appariement passé en paramètre
134: * La liste contient des GroupeComp. */
135: public List groupesCompEnCorrespondance(EnsembleDeLiens liens) {
136: List groupes = new ArrayList();
137: List liensOK = new ArrayList();
138: LienReseaux lien;
139: int i;
140:
141: liensOK = new ArrayList(this .getLiens());
142: liensOK.retainAll(liens.getElements());
143: for (i = 0; i < liensOK.size(); i++) {
144: lien = (LienReseaux) liensOK.get(i);
145: groupes.addAll(lien.getGroupes2());
146: }
147: return groupes;
148: }
149:
150: ///////////////////////////////////////////////////
151: // DIVERS
152: ///////////////////////////////////////////////////
153:
154: /** Noeud d'un groupe le plus proche d'un noeud donné */
155: public NoeudApp noeudLePlusProche(Groupe groupe) {
156: NoeudApp noeud, noeudLePlusProche;
157: Iterator itNoeuds = groupe.getListeNoeuds().iterator();
158: double dist, distmin;
159: if (groupe.getListeNoeuds().size() == 0)
160: return null;
161: noeudLePlusProche = (NoeudApp) itNoeuds.next();
162: distmin = this .distance(noeudLePlusProche);
163: while (itNoeuds.hasNext()) {
164: noeud = (NoeudApp) itNoeuds.next();
165: dist = this .distance(noeud);
166: if (distmin > dist) {
167: distmin = dist;
168: noeudLePlusProche = noeud;
169: }
170: }
171: return noeudLePlusProche;
172: }
173:
174: ////////////////////////////////////////////////////
175: // POUR ETUDIER LES CORRESPONDANCES DES ARCS
176: // COEUR DE L'APPARIEMENT DES NOEUDS
177: ////////////////////////////////////////////////////
178:
179: /** Teste la correspondance des arcs de self avec les arcs entrants et sortants des noeuds
180: *
181: * @return
182: * 1 si ca correspond bien
183: * 0 si ca correspond en partie seulement
184: * -1 si rien ne correspond du tout
185: */
186: public int correspCommunicants(NoeudApp noeudcomp,
187: EnsembleDeLiens liensPreappArcs) {
188: List inRef, inComp, outRef, outComp;
189: List arcsRef, arcsComp, arcsRefClasses, arcsCompClasses;
190: List arcsRefClassesArcs, arcsRefClassesOrientations;
191: List arcsCompClassesArcs, arcsCompClassesOrientations;
192: int nbCorresp, i;
193: ArcApp arc;
194: boolean entrantGeom, inOut = false;
195:
196: // 1ers tests sur le nombre
197: arcsRef = this .arcs();
198: arcsComp = noeudcomp.arcs();
199:
200: // 1: est-ce que chaque arc ref a au moins un correspondant autour du noeud comp ?
201: nbCorresp = nbArcsRefAvecCorrespondant(arcsRef, arcsComp,
202: liensPreappArcs);
203: if (nbCorresp == 0)
204: return -1;
205: if (nbCorresp != arcsRef.size())
206: return 0;
207:
208: // 2: est-ce que chaque arc ref a un correspondant pour lui tout seul ?
209: // NB: 1er filtrage pour gérer les cas faciles plus vite,
210: // mais ne gère pas bien tous les cas
211: Iterator itArcsRef = arcsRef.iterator();
212: Collection arcsCompCandidats = new HashSet();
213: while (itArcsRef.hasNext()) {
214: arc = (ArcApp) itArcsRef.next();
215: arcsCompCandidats.addAll(arc
216: .arcsCompEnCorrespondance(liensPreappArcs));
217: }
218: arcsCompCandidats.retainAll(arcsComp);
219: if (arcsCompCandidats.size() < arcsRef.size())
220: return 0;
221:
222: // 3 : plus fin : est-ce qu'on trouve bien des correspondances 1-1 ?
223:
224: // On crée les listes d'arcs in et out (au sens de la circulation),
225: // en tournant autour des noeuds dans le bon sens.
226: inRef = new ArrayList();
227: inComp = new ArrayList();
228: outRef = new ArrayList();
229: outComp = new ArrayList();
230:
231: arcsRefClasses = this .arcsClasses();
232: arcsRefClassesArcs = (List) arcsRefClasses.get(0);
233: arcsRefClassesOrientations = (List) arcsRefClasses.get(1);
234:
235: for (i = 0; i < arcsRefClassesArcs.size(); i++) {
236: arc = (ArcApp) arcsRefClassesArcs.get(i);
237: entrantGeom = ((Boolean) arcsRefClassesOrientations.get(i))
238: .booleanValue();
239: if (entrantGeom) {
240: if ((arc.getOrientation() == 1)
241: || (arc.getOrientation() == 2))
242: inRef.add(arc);
243: if ((arc.getOrientation() == -1)
244: || (arc.getOrientation() == 2))
245: outRef.add(arc);
246: } else {
247: if ((arc.getOrientation() == 1)
248: || (arc.getOrientation() == 2))
249: outRef.add(arc);
250: if ((arc.getOrientation() == -1)
251: || (arc.getOrientation() == 2))
252: inRef.add(arc);
253: }
254: }
255: arcsCompClasses = noeudcomp.arcsClasses();
256: arcsCompClassesArcs = (List) arcsCompClasses.get(0);
257: arcsCompClassesOrientations = (List) arcsCompClasses.get(1);
258:
259: for (i = 0; i < arcsCompClassesArcs.size(); i++) {
260: arc = (ArcApp) arcsCompClassesArcs.get(i);
261: entrantGeom = ((Boolean) arcsCompClassesOrientations.get(i))
262: .booleanValue();
263: if (entrantGeom) {
264: if ((arc.getOrientation() == 1)
265: || (arc.getOrientation() == 2))
266: inComp.add(arc);
267: if ((arc.getOrientation() == -1)
268: || (arc.getOrientation() == 2))
269: outComp.add(arc);
270: } else {
271: if ((arc.getOrientation() == 1)
272: || (arc.getOrientation() == 2))
273: outComp.add(arc);
274: if ((arc.getOrientation() == -1)
275: || (arc.getOrientation() == 2))
276: inComp.add(arc);
277: }
278: }
279:
280: // c'est la même chose en in et out ?
281: if (inRef.size() == outRef.size()
282: && inRef.size() == arcsRef.size())
283: inOut = true;
284:
285: // // on double les liste pour pouvoir tourner comme on veut
286: // incomp.addAll(incomp);
287: // if ( incomp.size() != 0 ) incomp.remove(incomp.size()-1);
288: // outcomp.addAll(outcomp);
289: // if ( outcomp.size() != 0 ) outcomp.remove(outcomp.size()-1);
290:
291: // on teste si chaque arc entrant a au moins un correspondant,
292: // sans compter le même correspondant deux fois,
293: // et en respectant le sens de rotation autour des noeuds
294: if (inRef.size() != 0) {
295: if (!correspondantsArcsClasses(inRef, inComp, 0,
296: liensPreappArcs))
297: return 0;
298: }
299:
300: // si tous les arcs sont entrants et sortant, on ne refait pas 2 fois la même chose
301: if (inOut)
302: return 1;
303:
304: //sinon, on refait la même chose sur les sortants
305: if (outRef.size() != 0) {
306: if (!correspondantsArcsClasses(outRef, outComp, 0,
307: liensPreappArcs))
308: return 0;
309: }
310: return 1;
311: }
312:
313: /** Teste la correspondance des arcs de self avec les arcs entrants et sortants des groupes
314: * EQUIVALENT DE LA METHODE SUR LES NOEUDS, D'UN POINT DE VUE GROUPE = HYPER-NOEUD.
315: *
316: * @return
317: * 1 si ca correspond bien
318: * 0 si ca correspond en partie seulement
319: * -1 si rien ne correspond du tout
320: */
321: public int correspCommunicants(GroupeApp groupecomp,
322: EnsembleDeLiens liensPreappArcs) {
323: List inRef, inComp, outRef, outComp;
324: List arcsRef, arcsComp, arcsRefClasses, arcsCompClasses;
325: List arcsRefClassesArcs, arcsRefClassesOrientations;
326: List arcsCompClassesArcs, arcsCompClassesOrientations;
327: int nbCorresp, i;
328: Arc arc;
329: boolean entrantGeom, inOut = false;
330:
331: // 1ers tests sur le nombre
332: arcsRef = this .arcs();
333: arcsComp = groupecomp.getAdjacents();
334: nbCorresp = nbArcsRefAvecCorrespondant(arcsRef, arcsComp,
335: liensPreappArcs);
336: if (nbCorresp == 0)
337: return -1;
338: if (nbCorresp != arcsRef.size())
339: return 0;
340:
341: // On crée les listes d'arcs in et out (au sens de la circulation),
342: // en tournant autour des noeuds dans le bon sens.
343: inRef = new ArrayList();
344: inComp = new ArrayList();
345: outRef = new ArrayList();
346: outComp = new ArrayList();
347:
348: arcsRefClasses = this .arcsClasses();
349: arcsRefClassesArcs = (List) arcsRefClasses.get(0);
350: arcsRefClassesOrientations = (List) arcsRefClasses.get(1);
351:
352: for (i = 0; i < arcsRefClassesArcs.size(); i++) {
353: arc = (Arc) arcsRefClassesArcs.get(i);
354: entrantGeom = ((Boolean) arcsRefClassesOrientations.get(i))
355: .booleanValue();
356: if (entrantGeom) {
357: if ((arc.getOrientation() == 1)
358: || (arc.getOrientation() == 2))
359: inRef.add(arc);
360: if ((arc.getOrientation() == -1)
361: || (arc.getOrientation() == 2))
362: outRef.add(arc);
363: } else {
364: if ((arc.getOrientation() == 1)
365: || (arc.getOrientation() == 2))
366: outRef.add(arc);
367: if ((arc.getOrientation() == -1)
368: || (arc.getOrientation() == 2))
369: inRef.add(arc);
370: }
371: }
372:
373: arcsCompClasses = groupecomp.arcsClasses();
374: arcsCompClassesArcs = (List) arcsCompClasses.get(0);
375: arcsCompClassesOrientations = (List) arcsCompClasses.get(1);
376:
377: for (i = 0; i < arcsCompClassesArcs.size(); i++) {
378: arc = (Arc) arcsCompClassesArcs.get(i);
379: entrantGeom = ((Boolean) arcsCompClassesOrientations.get(i))
380: .booleanValue();
381: if (entrantGeom) {
382: if ((arc.getOrientation() == 1)
383: || (arc.getOrientation() == 2))
384: inComp.add(arc);
385: if ((arc.getOrientation() == -1)
386: || (arc.getOrientation() == 2))
387: outComp.add(arc);
388: } else {
389: if ((arc.getOrientation() == 1)
390: || (arc.getOrientation() == 2))
391: outComp.add(arc);
392: if ((arc.getOrientation() == -1)
393: || (arc.getOrientation() == 2))
394: inComp.add(arc);
395: }
396: }
397:
398: // c'est la même chose en in et out ?
399: if (inRef.size() == outRef.size()
400: && inRef.size() == arcsRef.size())
401: inOut = true;
402:
403: // on teste si chaque arc entrant a au moins un correspondant, sans compter le même correspondant deux fois
404: if (inRef.size() != 0) {
405: if (!correspondantsArcsClasses(inRef, inComp, 0,
406: liensPreappArcs))
407: return 0;
408: }
409:
410: // si tous les arcs sont entrants et sortant, on ne refait pas 2 fois la même chose
411: if (inOut)
412: return 1;
413:
414: //sinon, on refait la même chose sur les sortants
415: if (outRef.size() != 0) {
416: if (!correspondantsArcsClasses(outRef, outComp, 0,
417: liensPreappArcs))
418: return 0;
419: }
420: return 1;
421: }
422:
423: /** Methode utile à correspCommunicants (pour les noeuds et les groupes)
424: * Renvoie le nb d'éléments de ref ayant au moins un correspondant dans comp par liens
425: */
426: private int nbArcsRefAvecCorrespondant(List ref, List comp,
427: EnsembleDeLiens liens) {
428: int nb = 0;
429: List corresp;
430: ArcApp arcRef;
431: Iterator itRef = ref.iterator();
432: while (itRef.hasNext()) {
433: arcRef = (ArcApp) itRef.next();
434: corresp = arcRef.arcsCompEnCorrespondance(liens);
435: corresp.retainAll(comp);
436: if (corresp.size() != 0)
437: nb = nb + 1;
438: }
439: return nb;
440: }
441:
442: /** Methode utile à correspCommunicants (pour les noeuds et les groupes)
443: * renvoie OK quand tout est bon
444: * @param ref : les arcs du noeud ref qui n'ont pas encore de correspondant
445: * @param comp : les arcs du noeud comp qui n'ont pas encore de correspondant
446: * @param rangRef : rang de l'arc ref en cours de traitement
447: */
448: private boolean correspondantsArcsClasses(List ref, List comp,
449: int rangRef, EnsembleDeLiens liens) {
450:
451: ArcApp arcRef, arcComp;
452: List liensArcRef, arcsCompCandidats, compPourProchain;
453: boolean OK;
454:
455: // si on n'a plus d'arc à traiter, c'est gagné
456: if (rangRef == ref.size())
457: return true;
458:
459: arcRef = (ArcApp) ref.get(rangRef); // arc en cours de traitement
460:
461: // on cherche les candidats à l'appariement de arcRef
462: liensArcRef = new ArrayList(arcRef
463: .getLiens(liens.getElements()));
464: arcsCompCandidats = new ArrayList();
465: for (int i = 0; i < liensArcRef.size(); i++)
466: arcsCompCandidats.addAll(((LienReseaux) liensArcRef.get(i))
467: .getArcs2());
468: arcsCompCandidats.retainAll(comp);
469:
470: // si la liste des candidats est vide, c'est foutu, il faut revenir en arrière
471: if (arcsCompCandidats.size() == 0)
472: return false;
473:
474: // on teste toutes les combinaisons de correspondance possibles
475: for (int i = 0; i < comp.size(); i++) {
476: arcComp = (ArcApp) comp.get(i);
477: if (!arcsCompCandidats.contains(arcComp))
478: continue; // cet arc n'est pas candidat, on essaye avec le suivant
479:
480: //on a un candidat sous la main
481: compPourProchain = new ArrayList();
482: if (rangRef == 0) {
483: for (int j = i + 1; j < comp.size(); j++)
484: compPourProchain.add(comp.get(j));
485: for (int j = 0; j < i; j++)
486: compPourProchain.add(comp.get(j));
487: } else {
488: for (int j = i + 1; j < comp.size(); j++)
489: compPourProchain.add(comp.get(j));
490: }
491: if (compPourProchain.size() < ref.size() - rangRef - 1)
492: continue;
493: OK = correspondantsArcsClasses(ref, compPourProchain,
494: rangRef + 1, liens);
495: if (OK)
496: return true; // une correspondance possible : on continue
497: }
498: return false; // aucune correspondance possible : on remonte d'un cran
499: }
500:
501: }
|