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.cartetopo;
028:
029: import java.util.ArrayList;
030: import java.util.HashSet;
031: import java.util.Iterator;
032: import java.util.List;
033:
034: import fr.ign.cogit.geoxygene.contrib.geometrie.Angle;
035: import fr.ign.cogit.geoxygene.contrib.geometrie.Distances;
036: import fr.ign.cogit.geoxygene.contrib.geometrie.Operateurs;
037: import fr.ign.cogit.geoxygene.spatial.coordgeom.DirectPosition;
038: import fr.ign.cogit.geoxygene.spatial.coordgeom.DirectPositionList;
039: import fr.ign.cogit.geoxygene.spatial.coordgeom.GM_LineString;
040: import fr.ign.cogit.geoxygene.spatial.geomprim.GM_Point;
041:
042: /**
043: * Classe des noeuds de la carte topo.
044: * Les arcs ont pour géométrie un GM_Point.
045: *
046: * English: nodes of topological map
047: * @author Mustière/Bonin
048: * @version 1.0
049: */
050:
051: public class Noeud extends ElementCarteTopo {
052:
053: public Noeud() {
054: }
055:
056: /////////////////////////////////////////////////////////////////////////////////////////////////
057: // Géométrie
058: /////////////////////////////////////////////////////////////////////////////////////////////////
059: /** Renvoie le GM_Point qui définit la géométrie de self */
060: public GM_Point getGeometrie() {
061: return (GM_Point) geom;
062: }
063:
064: /** Définit le GM_Point qui définit la géométrie de self */
065: public void setGeometrie(GM_Point geometrie) {
066: this .setGeom(geometrie);
067: }
068:
069: /** Renvoie le DirectPosition qui définit les coordonnées de self */
070: public DirectPosition getCoord() {
071: return (DirectPosition) this .getGeometrie().getPosition();
072: }
073:
074: /** Définit le DirectPosition qui définit les coordonnées de self */
075: public void setCoord(DirectPosition dp) {
076: geom = new GM_Point(dp);
077: }
078:
079: /////////////////////////////////////////////////////////////////////////////////////////////////
080: // Topologie de réseau arcs / noeuds
081: /////////////////////////////////////////////////////////////////////////////////////////////////
082: private List entrants = new ArrayList();
083:
084: /** Renvoie la liste (non ordonnée) des arcs entrants de self.
085: * La distinction entrant/sortant s'entend au sens du codage de la géométrie.
086: * (et non au sens de l'orientation du graphe, comme avec les attributs entrantsOrientation)
087: */
088: public List getEntrants() {
089: return entrants;
090: }
091:
092: /** Ajoute un arc entrant à la liste des arcs entrants de self */
093: public void addEntrant(Arc arc) {
094: if (arc != null && !entrants.contains(arc)) {
095: entrants.add(arc);
096: if (arc.getNoeudFin() != this )
097: arc.setNoeudFin(this );
098: }
099: }
100:
101: /** Enlève un arc entrant à la liste des arcs entrants de self */
102: public void enleveEntrant(Arc arc) {
103: if (arc == null)
104: return;
105: if (!entrants.contains(arc))
106: return;
107: entrants.remove(arc);
108: arc.setNoeudFin(null);
109: }
110:
111: private List sortants = new ArrayList();
112:
113: /** Renvoie la liste (non ordonnée) des arcs sortants de self
114: * La distinction entrant/sortant s'entend au sens du codage de la géométrie.
115: * (et non au sens de l'orientation du graphe, comme avec les attributs entrantsOrientation)
116: */
117: public List getSortants() {
118: return sortants;
119: }
120:
121: /** Ajoute un arc sortant à la liste des arcs sortants de self */
122: public void addSortant(Arc arc) {
123: if (arc != null && !sortants.contains(arc)) {
124: sortants.add(arc);
125: if (arc.getNoeudIni() != this )
126: arc.setNoeudIni(this );
127: }
128: }
129:
130: /** Enlève un arc sortant à la liste des arcs entrants de self */
131: public void enleveSortant(Arc arc) {
132: if (arc == null)
133: return;
134: if (!sortants.contains(arc))
135: return;
136: sortants.remove(arc);
137: arc.setNoeudIni(null);
138: }
139:
140: /** Renvoie la liste (non ordonnée) de tous les arcs entrants et sortants de self.
141: * NB : si un arc est à la fois entrant et sortant (boucle), il est 2 fois dans la liste
142: */
143: public List arcs() {
144: List Arcs = new ArrayList();
145: Arcs.addAll(this .getSortants());
146: Arcs.addAll(this .getEntrants());
147: return Arcs;
148: }
149:
150: /** Renvoie la liste des noeuds voisins de self dans le réseau
151: * sans tenir compte de l'orientation (i.e. tous les arcs sont considérés en double sens) */
152: public List voisins() {
153: List voisins = new ArrayList();
154: List entrants = this .getEntrants();
155: Arc arc;
156: Iterator iterentrants = entrants.iterator();
157: while (iterentrants.hasNext()) {
158: arc = (Arc) iterentrants.next();
159: voisins.add(arc.getNoeudIni());
160: }
161: List sortants = this .getSortants();
162: Iterator itersortants = sortants.iterator();
163: while (itersortants.hasNext()) {
164: arc = (Arc) itersortants.next();
165: voisins.add(arc.getNoeudFin());
166: }
167: return voisins;
168: }
169:
170: /////////////////////////////////////////////////////////////////////////////////////////////////
171: // Gestion de graphe noeuds / faces
172: /////////////////////////////////////////////////////////////////////////////////////////////////
173: /** Renvoie la liste des faces s'appuyant sur self */
174: public List faces() {
175: HashSet faces = new HashSet();
176: List arcs = this .arcs();
177: Arc arc;
178: Iterator iterarcs = arcs.iterator();
179: while (iterarcs.hasNext()) {
180: arc = (Arc) iterarcs.next();
181: faces.addAll(arc.faces());
182: }
183: return new ArrayList(faces);
184: }
185:
186: /////////////////////////////////////////////////////////////////////////////////////////////////
187: // Gestion de réseau orienté
188: /////////////////////////////////////////////////////////////////////////////////////////////////
189:
190: /** les entrants du noeud, au sens de l'orientation,
191: * (alors que pour getEntrants c'est au sens de la géométrie) **/
192: public List entrantsOrientes() {
193: List arcsEntrants = this .getEntrants();
194: List arcsSortants = this .getSortants();
195: List arcs = new ArrayList();
196: Arc arc;
197: int i;
198:
199: for (i = 0; i < arcsEntrants.size(); i++) {
200: arc = (Arc) arcsEntrants.get(i);
201: if ((arc.getOrientation() == 1)
202: || (arc.getOrientation() == 2))
203: arcs.add(arc);
204: }
205: for (i = 0; i < arcsSortants.size(); i++) {
206: arc = (Arc) arcsSortants.get(i);
207: if ((arc.getOrientation() == -1)
208: || (arc.getOrientation() == 2))
209: arcs.add(arc);
210: }
211: return arcs;
212: }
213:
214: /** les sortants du noeud, au sens de l'orientation,
215: * (alors que pour getSortants c'est au sens de la géométrie) **/
216: public List sortantsOrientes() {
217: List arcsEntrants = this .getEntrants();
218: List arcsSortants = this .getSortants();
219: List arcs = new ArrayList();
220: Arc arc;
221: int i;
222:
223: for (i = 0; i < arcsEntrants.size(); i++) {
224: arc = (Arc) arcsEntrants.get(i);
225: if ((arc.getOrientation() == -1)
226: || (arc.getOrientation() == 2))
227: arcs.add(arc);
228: }
229: for (i = 0; i < arcsSortants.size(); i++) {
230: arc = (Arc) arcsSortants.get(i);
231: if ((arc.getOrientation() == 1)
232: || (arc.getOrientation() == 2))
233: arcs.add(arc);
234: }
235: return arcs;
236: }
237:
238: /////////////////////////////////////////////////////////////////////////////////////////////////
239: // Gestion de type carte topologique
240: /////////////////////////////////////////////////////////////////////////////////////////////////
241: // Les arcs sont classés autour d'un noeud en fonction de leur géométrie.
242: // Ceci permet en particulier de parcourir facilement les cycles d'un graphe.
243: /////////////////////////////////////////////////////////////////////////////////////////////////
244:
245: /** Arcs incidents à un noeuds, classés en tournant autour du noeud dans l'ordre trigonométrique,
246: * et qualifiés d'entrants ou sortants, au sens de la géoémtrie (utile particulièrement à la gestion des boucles).
247: *
248: * NB : renvoie une liste de liste:
249: * Liste.get(0) = liste des arcs (de la classe 'Arc')
250: * Liste.get(1) = liste des orientations de type Boolean,
251: * true = entrant, false = sortant)
252: * NB : Classement effectué sur la direction donnée par le premier point de l'arc après le noeud.
253: * NB : Le premier arc est celui dont la direction est la plus proche de l'axe des X, en tournant dans le sens trigo.
254: * NB : Ce classement est recalculé en fonction de la géométrie à chaque appel de la méthode.
255: */
256: public List arcsClasses() {
257: List arcsClasses = new ArrayList();
258: List arcsClassesOrientation = new ArrayList();
259: List arcsEntrants = new ArrayList(this .getEntrants());
260: List arcsSortants = new ArrayList(this .getSortants());
261: List arcs = new ArrayList();
262: List angles = new ArrayList();
263: List orientations = new ArrayList();
264: List resultat = new ArrayList();
265: Arc arc;
266: Angle angle;
267: double angleMin, angleCourant;
268: int imin;
269: Iterator itArcs;
270: int i;
271:
272: // recherche de l'angle de départ de chaque arc sortant
273: itArcs = arcsSortants.iterator();
274: while (itArcs.hasNext()) {
275: arc = (Arc) itArcs.next();
276: angle = new Angle((DirectPosition) arc.getCoord().get(0),
277: (DirectPosition) arc.getCoord().get(1));
278: arcs.add(arc);
279: angles.add(angle);
280: orientations.add(new Boolean(false));
281: }
282: // recherche de l'angle de départ de chaque arc entrant
283: itArcs = arcsEntrants.iterator();
284: while (itArcs.hasNext()) {
285: arc = (Arc) itArcs.next();
286: angle = new Angle((DirectPosition) arc.getCoord().get(
287: arc.getCoord().size() - 1), (DirectPosition) arc
288: .getCoord().get(arc.getCoord().size() - 2));
289: arcs.add(arc);
290: angles.add(angle);
291: orientations.add(new Boolean(true));
292: }
293: // classement des arcs
294: while (!(arcs.isEmpty())) {
295: angleMin = ((Angle) angles.get(0)).getAngle();
296: imin = 0;
297: for (i = 1; i < arcs.size(); i++) {
298: angleCourant = ((Angle) angles.get(i)).getAngle();
299: if (angleCourant < angleMin) {
300: angleMin = angleCourant;
301: imin = i;
302: }
303: }
304: arcsClasses.add(arcs.get(imin));
305: arcsClassesOrientation.add(orientations.get(imin));
306: arcs.remove(imin);
307: angles.remove(imin);
308: orientations.remove(imin);
309: }
310: //retour du résultat
311: resultat.add(arcsClasses);
312: resultat.add(arcsClassesOrientation);
313: return resultat;
314: }
315:
316: /////////////////////////////////////////////////////////////////////////////////////////////////
317: // Gestion des groupes
318: /////////////////////////////////////////////////////////////////////////////////////////////////
319: /** Groupes auquels self appartient */
320: private List listeGroupes = new ArrayList();
321:
322: /** Renvoie la liste des groupes de self*/
323: public List getListeGroupes() {
324: return this .listeGroupes;
325: }
326:
327: /** Définit la liste des groupes de self*/
328: public void setListeGroupes(List liste) {
329: this .listeGroupes = liste;
330: }
331:
332: /** Ajoute un groupe à self*/
333: public void addGroupe(Groupe groupe) {
334: if (groupe != null && !listeGroupes.contains(groupe)) {
335: this .listeGroupes.add(groupe);
336: if (!groupe.getListeNoeuds().contains(this ))
337: groupe.addNoeud(this );
338: }
339: }
340:
341: /** Liste des noeuds voisins de self au sein d'un groupe.
342: * Renvoie une liste vide si il n'y en a pas */
343: public List voisins(Groupe groupe) {
344: List arcsDuGroupe = new ArrayList();
345: List arcsVoisins = new ArrayList();
346: Arc arcVoisin;
347: List noeudsDuGroupe = new ArrayList();
348: List noeudsVoisins = new ArrayList();
349: Noeud noeudVoisin;
350: int i;
351:
352: noeudsDuGroupe = groupe.getListeNoeuds();
353: arcsDuGroupe = groupe.getListeArcs();
354:
355: // gestion des arcs entrants
356: arcsVoisins = this .getEntrants();
357: for (i = 0; i < arcsVoisins.size(); i++) {
358: arcVoisin = (Arc) arcsVoisins.get(i);
359: if (arcsDuGroupe.contains(arcVoisin)) {
360: noeudVoisin = arcVoisin.getNoeudIni();
361: if (noeudVoisin == null)
362: continue;
363: if (noeudsDuGroupe.contains(noeudVoisin)
364: && !noeudsVoisins.contains(noeudVoisin)) {
365: noeudsVoisins.add(noeudVoisin);
366: }
367: }
368: }
369: // gestion des arcs sortants
370: arcsVoisins = this .getSortants();
371: for (i = 0; i < arcsVoisins.size(); i++) {
372: arcVoisin = (Arc) arcsVoisins.get(i);
373: if (arcsDuGroupe.contains(arcVoisin)) {
374: noeudVoisin = arcVoisin.getNoeudFin();
375: if (noeudVoisin == null)
376: continue;
377: if (noeudsDuGroupe.contains(noeudVoisin)
378: && !noeudsVoisins.contains(noeudVoisin)) {
379: noeudsVoisins.add(noeudVoisin);
380: }
381: }
382: }
383: return noeudsVoisins;
384: };
385:
386: /////////////////////////////////////////////////////////////////////////////////////////////////
387: // Opérateurs de calculs sur les noeuds
388: /////////////////////////////////////////////////////////////////////////////////////////////////
389: /** Distance euclidienne. Valable pour des coordonnées en 2 ou 3D. */
390: public double distance(Noeud noeud) {
391: return Distances.distance(this .getCoord(), noeud.getCoord());
392: }
393:
394: /** Distance euclidienne dans le plan (x,y). */
395: public double distance2D(Noeud noeud) {
396: return Distances.distance2D(this .getCoord(), noeud.getCoord());
397: }
398:
399: /** Distance euclidienne à un arc. */
400: public double distance(Arc arc) {
401: return Distances.distance(this .getCoord(), arc.getGeometrie());
402: }
403:
404: ///////////////////////////////////////////////////////////////////////////////////////////////////////
405: ///////////////////////////////////////////////////////////////////////////////////////////////////////
406: // Différentes variantes du plus court chemin
407: ///////////////////////////////////////////////////////////////////////////////////////////////////////
408: ///////////////////////////////////////////////////////////////////////////////////////////////////////
409:
410: // attributs internes utiles pour les calculs de plus court chemin
411: /** utilisation interne : ne pas utiliser */
412: private double _distance;
413: /** utilisation interne : ne pas utiliser */
414: private Arc _arcPrecedent;
415: /** utilisation interne : ne pas utiliser */
416: private Noeud _noeudPrecedent;
417:
418: /** Plus court chemin de this vers arrivée, en tenant compte du sens de circulation.
419: * Le pcc s'appuie sur l'attribut 'poids' des arcs, qui doit être rempli auparavant.
420: *
421: * @param maxLongueur
422: * Pour optimiser: on arrête de chercher et on renvoie null si il n'y a pas de pcc
423: * de taille inférieure à maxLongueur (inactif si maxLongueur = 0).
424: *
425: * @return
426: * Renvoie un groupe, qui contient (dans l'ordre) les noeuds et arcs du plus court chemin.
427: * Cas particuliers :
428: * Si this = arrivée, renvoie un groupe contenant uniquement self;
429: * Si this et arrivée sont sur 2 composantes connexes distinctes (pas de pcc), renvoie null.
430: *
431: * NB : l'attribut orientation DOIT etre renseigné.
432: * NB : ce groupe contient le noeud de départ et le noeud d'arrivée.
433: */
434: public Groupe plusCourtChemin(Noeud arrivee, double maxLongueur) {
435: List noeudsFinaux = new ArrayList();
436: List arcsFinaux = new ArrayList();
437: List noeudsVoisins = new ArrayList();
438: List arcsVoisins = new ArrayList();
439: List distancesVoisins = new ArrayList();
440: List traites = new ArrayList();
441: List aTraiter = new ArrayList();
442: int i;
443: Arc arcVoisin;
444: Noeud noeudVoisin, plusProche, suivant;
445: double dist;
446:
447: try {
448: if (this .getCarteTopo() == null) {
449: System.out.println("ATTENTION : le noeud " + this
450: + " ne fait pas partie d'une carte topo");
451: System.out
452: .println(" Impossible de calculer un plus court chemin ");
453: return null;
454: }
455: if (this .getCarteTopo().getPopGroupes() == null) {
456: System.out
457: .println("ATTENTION : le noeud "
458: + this
459: + " fait partie d'une carte topo sans population de groupes");
460: System.out
461: .println(" Impossible de calculer un plus court chemin ");
462: return null;
463: }
464: Groupe plusCourtChemin = (Groupe) this .getCarteTopo()
465: .getPopGroupes().nouvelElement();
466:
467: if (this == arrivee) {
468: plusCourtChemin.addNoeud(this );
469: this .addGroupe(plusCourtChemin);
470: return plusCourtChemin;
471: }
472: this ._distance = 0;
473: this .chercheArcsNoeudsVoisins(noeudsVoisins,
474: distancesVoisins, arcsVoisins);
475:
476: for (i = 0; i < noeudsVoisins.size(); i++) {
477: noeudVoisin = (Noeud) noeudsVoisins.get(i);
478: arcVoisin = (Arc) arcsVoisins.get(i);
479: dist = ((Double) distancesVoisins.get(i)).doubleValue();
480: noeudVoisin._distance = dist;
481: noeudVoisin._arcPrecedent = arcVoisin;
482: noeudVoisin._noeudPrecedent = this ;
483: }
484: aTraiter.addAll(noeudsVoisins);
485:
486: // Phase "avant"
487: while (aTraiter.size() != 0) {
488: // choisi le noeud à marquer comme traité parmi les voisins
489: plusProche = (Noeud) aTraiter.get(0);
490: for (i = 1; i < aTraiter.size(); i++) {
491: if (((Noeud) aTraiter.get(i))._distance < plusProche._distance) {
492: plusProche = (Noeud) aTraiter.get(i);
493: }
494: }
495: traites.add(plusProche);
496: aTraiter.remove(plusProche);
497: if (plusProche == arrivee)
498: break; //il s'agit du noeud d'arrivée
499: if (maxLongueur != 0) {
500: if (plusProche._distance > maxLongueur)
501: return null; // heuristique pour stopper la recherche
502: }
503: plusProche.chercheArcsNoeudsVoisins(noeudsVoisins,
504: distancesVoisins, arcsVoisins);
505: for (i = 0; i < noeudsVoisins.size(); i++) {
506: noeudVoisin = (Noeud) noeudsVoisins.get(i);
507: arcVoisin = (Arc) arcsVoisins.get(i);
508: dist = ((Double) distancesVoisins.get(i))
509: .doubleValue();
510: if (traites.contains(noeudVoisin))
511: continue; // Noeud déjà traité
512: if (aTraiter.contains(noeudVoisin)) { // Noeud déjà atteint, on voit si on a trouvé un chemin plus court pour y accéder
513: if (noeudVoisin._distance > (plusProche._distance + dist)) {
514: noeudVoisin._distance = plusProche._distance
515: + dist;
516: noeudVoisin._arcPrecedent = arcVoisin;
517: noeudVoisin._noeudPrecedent = plusProche;
518: }
519: continue;
520: }
521: // Nouveau noeud atteint, on l'initialise
522: noeudVoisin._distance = plusProche._distance + dist;
523: noeudVoisin._arcPrecedent = arcVoisin;
524: noeudVoisin._noeudPrecedent = plusProche;
525: aTraiter.add(noeudVoisin);
526: }
527: }
528:
529: // Phase "arriere"
530: if (!traites.contains(arrivee))
531: return null;
532: suivant = arrivee;
533: while (true) {
534: arcsFinaux.add(0, suivant._arcPrecedent);
535: ((Arc) suivant._arcPrecedent)
536: .addGroupe(plusCourtChemin);
537: suivant = (Noeud) suivant._noeudPrecedent;
538: if (suivant == this )
539: break;
540: noeudsFinaux.add(0, suivant);
541: suivant.addGroupe(plusCourtChemin);
542: }
543:
544: noeudsFinaux.add(0, this );
545: this .addGroupe(plusCourtChemin);
546: noeudsFinaux.add(arrivee);
547: arrivee.addGroupe(plusCourtChemin);
548:
549: plusCourtChemin.setListeArcs(arcsFinaux);
550: plusCourtChemin.setListeNoeuds(noeudsFinaux);
551: return plusCourtChemin;
552:
553: } catch (Exception e) {
554: System.out
555: .println("----- ERREUR dans calcul de plus court chemin. ");
556: e.printStackTrace();
557: return null;
558: }
559: }
560:
561: // Méthode utile au plus court chemin
562: private void chercheArcsNoeudsVoisins(List noeudsVoisins,
563: List distancesVoisins, List arcsVoisins) {
564: List arcsEntrants = new ArrayList(); // au sens de la geometrie
565: List arcsSortants = new ArrayList(); // au sens de la geometrie
566: List arcsSortants2 = new ArrayList(); // au sens de la circulation
567: List noeudsSortants2 = new ArrayList(); // au sens de la circulation
568: List distancesSortants2 = new ArrayList(); // au sens de la circulation
569: Noeud noeud;
570: Arc arc;
571: Double distance;
572: int i, j;
573:
574: noeudsVoisins.clear();
575: distancesVoisins.clear();
576: arcsVoisins.clear();
577:
578: try {
579: arcsEntrants = this .getEntrants();
580: arcsSortants = this .getSortants();
581: } catch (Exception e) {
582: e.printStackTrace();
583: }
584:
585: // transformation du sens géométrique au sens de circulation
586: for (i = 0; i < arcsEntrants.size(); i++) {
587: arc = (Arc) arcsEntrants.get(i);
588: if ((arc.getOrientation() == -1)
589: || (arc.getOrientation() == 2)) {
590: if (arc.getNoeudIni() != null) {
591: arcsSortants2.add(arc);
592: noeudsSortants2.add((Noeud) arc.getNoeudIni());
593: distancesSortants2.add(new Double(arc.getPoids()));
594: }
595: }
596: }
597: for (i = 0; i < arcsSortants.size(); i++) {
598: arc = (Arc) arcsSortants.get(i);
599: if ((arc.getOrientation() == 1)
600: || (arc.getOrientation() == 2)) {
601: if (arc.getNoeudFin() != null) {
602: arcsSortants2.add(arc);
603: noeudsSortants2.add((Noeud) arc.getNoeudFin());
604: distancesSortants2.add(new Double(arc.getPoids()));
605: }
606: }
607: }
608:
609: // en choisissant l'arc le plus court, si il existe des arcs parallèles (mêmes noeuds ini et fin)
610: for (i = 0; i < noeudsSortants2.size(); i++) {
611: // choix du plus court arc menant au noeud sortant
612: noeud = (Noeud) noeudsSortants2.get(i);
613: if (noeudsVoisins.contains(noeud))
614: continue;
615: arc = (Arc) arcsSortants2.get(i);
616: distance = (Double) distancesSortants2.get(i);
617: for (j = i + 1; j < noeudsSortants2.size(); j++) {
618: if (noeud == (Noeud) noeudsSortants2.get(j)) {
619: if (((Double) distancesSortants2.get(j))
620: .doubleValue() < distance.doubleValue()) {
621: distance = (Double) distancesSortants2.get(j);
622: arc = (Arc) arcsSortants2.get(j);
623: }
624: }
625: }
626: arcsVoisins.add(arc);
627: noeudsVoisins.add(noeud);
628: distancesVoisins.add(distance);
629: }
630: }
631:
632: /** Plus court chemin de this vers arrivée, en tenant compte du sens de circulation,
633: * au sein d'un groupe d'arcs et de noeuds.
634: * Le pcc s'appuie sur l'attribut 'poids' des arcs, qui doit être rempli auparavant.
635: *
636: * @param maxLongueur
637: * Pour optimiser: on arrête de chercher et on renvoie null si il n'y a pas de pcc
638: * de taille inférieure à maxLongueur (inactif si maxLongueur = 0).
639: *
640: * @return:
641: * Renvoie un groupe, qui contient (dans l'ordre) les noeuds et arcs du plus court chemin.
642: * Cas particuliers :
643: * Si this = arrivée, renvoie un groupe contenant uniquement self;
644: * Si this et arrivée sont sur 2 composantes connexes distinctes (pas de pcc), renvoie null.
645: *
646: * NB : l'attribut orientation DOIT etre renseigné.
647: * NB : ce groupe contient le noeud de départ et le noeud d'arrivée.
648: */
649: public Groupe plusCourtChemin(Noeud arrivee, Groupe groupe,
650: double maxLongueur) {
651: List noeudsFinaux = new ArrayList();
652: List arcsFinaux = new ArrayList();
653: List noeudsVoisins = new ArrayList();
654: List arcsVoisins = new ArrayList();
655: List distancesVoisins = new ArrayList();
656: List traites = new ArrayList();
657: List aTraiter = new ArrayList();
658: int i;
659: Arc arcVoisin;
660: Noeud noeudVoisin, plusProche, suivant;
661: double dist;
662:
663: try {
664: if (this .getCarteTopo() == null) {
665: System.out.println("ATTENTION : le noeud " + this
666: + " ne fait pas partie d'une carte topo");
667: System.out
668: .println(" Impossible de calculer un plus court chemin ");
669: return null;
670: }
671: if (this .getCarteTopo().getPopGroupes() == null) {
672: System.out
673: .println("ATTENTION : le noeud "
674: + this
675: + " fait partie d'une carte topo sans population de groupes");
676: System.out
677: .println(" Impossible de calculer un plus court chemin ");
678: return null;
679: }
680: Groupe plusCourtChemin = (Groupe) this .getCarteTopo()
681: .getPopGroupes().nouvelElement();
682:
683: if (this == arrivee) {
684: plusCourtChemin.addNoeud(this );
685: this .addGroupe(plusCourtChemin);
686: return plusCourtChemin;
687: }
688: this ._distance = 0;
689: this .chercheArcsNoeudsVoisins(groupe, noeudsVoisins,
690: distancesVoisins, arcsVoisins);
691: for (i = 0; i < noeudsVoisins.size(); i++) {
692: noeudVoisin = (Noeud) noeudsVoisins.get(i);
693: arcVoisin = (Arc) arcsVoisins.get(i);
694: dist = ((Double) distancesVoisins.get(i)).doubleValue();
695: noeudVoisin._distance = dist;
696: noeudVoisin._arcPrecedent = arcVoisin;
697: noeudVoisin._noeudPrecedent = this ;
698: }
699: aTraiter.addAll(noeudsVoisins);
700:
701: // Phase "avant"
702: while (aTraiter.size() != 0) {
703:
704: // choisi le noeud à marquer comme traité parmi les voisins
705: plusProche = (Noeud) aTraiter.get(0);
706: for (i = 1; i < aTraiter.size(); i++) {
707: if (((Noeud) aTraiter.get(i))._distance < plusProche._distance) {
708: plusProche = (Noeud) aTraiter.get(i);
709: }
710: }
711:
712: traites.add(plusProche);
713: aTraiter.remove(plusProche);
714: if (plusProche == arrivee)
715: break; //il s'agit du noeud d'arrivée
716: if (maxLongueur != 0) {
717: if (plusProche._distance > maxLongueur)
718: return null; // heuristique pour stopper la recherche
719: }
720:
721: plusProche.chercheArcsNoeudsVoisins(groupe,
722: noeudsVoisins, distancesVoisins, arcsVoisins);
723: for (i = 0; i < noeudsVoisins.size(); i++) {
724: noeudVoisin = (Noeud) noeudsVoisins.get(i);
725: arcVoisin = (Arc) arcsVoisins.get(i);
726: dist = ((Double) distancesVoisins.get(i))
727: .doubleValue();
728: if (traites.contains(noeudVoisin))
729: continue; // Noeud déjà traité
730: if (aTraiter.contains(noeudVoisin)) { // Noeud déjà atteint, on voit si on a trouvé un chemin plus court pour y accéder
731: if (noeudVoisin._distance > (plusProche._distance + dist)) {
732: noeudVoisin._distance = plusProche._distance
733: + dist;
734: noeudVoisin._arcPrecedent = arcVoisin;
735: noeudVoisin._noeudPrecedent = plusProche;
736: }
737: continue;
738: }
739: // Nouveau noeud atteint, on l'initialise
740: noeudVoisin._distance = plusProche._distance + dist;
741: noeudVoisin._arcPrecedent = arcVoisin;
742: noeudVoisin._noeudPrecedent = plusProche;
743: aTraiter.add(noeudVoisin);
744: }
745: }
746:
747: // Phase "arriere"
748: if (!traites.contains(arrivee))
749: return null;
750: suivant = arrivee;
751: while (true) {
752: arcsFinaux.add(0, suivant._arcPrecedent);
753: suivant._arcPrecedent.addGroupe(plusCourtChemin);
754: suivant = (Noeud) suivant._noeudPrecedent;
755: if (suivant == this )
756: break;
757: noeudsFinaux.add(0, suivant);
758: suivant.addGroupe(plusCourtChemin);
759: }
760:
761: noeudsFinaux.add(0, this );
762: this .addGroupe(plusCourtChemin);
763: noeudsFinaux.add(arrivee);
764: arrivee.addGroupe(plusCourtChemin);
765:
766: plusCourtChemin.setListeArcs(arcsFinaux);
767: plusCourtChemin.setListeNoeuds(noeudsFinaux);
768: return plusCourtChemin;
769: } catch (Exception e) {
770: System.out
771: .println("----- ERREUR dans calcul de plus court chemin. ");
772: e.printStackTrace();
773: return null;
774: }
775: }
776:
777: // Méthode utile au plus court chemin
778: private void chercheArcsNoeudsVoisins(Groupe groupe,
779: List noeudsVoisins, List distancesVoisins, List arcsVoisins) {
780: List arcsEntrants = new ArrayList(); // au sens de la geometrie
781: List arcsSortants = new ArrayList(); // au sens de la geometrie
782: List arcsSortants2 = new ArrayList(); // au sens de la circulation
783: List noeudsSortants2 = new ArrayList(); // au sens de la circulation
784: List distancesSortants2 = new ArrayList(); // au sens de la circulation
785: Noeud noeud;
786: Arc arc;
787: Double distance;
788: int i, j;
789:
790: noeudsVoisins.clear();
791: distancesVoisins.clear();
792: arcsVoisins.clear();
793:
794: arcsEntrants = this .getEntrants();
795: arcsSortants = this .getSortants();
796:
797: // transformation du sens géométrique au sens de circulation
798: for (i = 0; i < arcsEntrants.size(); i++) {
799: arc = (Arc) arcsEntrants.get(i);
800: if (groupe.getListeArcs().contains(arc)) {
801: if ((arc.getOrientation() == -1)
802: || (arc.getOrientation() == 2)) {
803: if (arc.getNoeudIni() != null) {
804: arcsSortants2.add(arc);
805: noeudsSortants2.add((Noeud) arc.getNoeudIni());
806: distancesSortants2.add(new Double(arc
807: .getPoids()));
808: }
809: }
810: }
811: }
812: for (i = 0; i < arcsSortants.size(); i++) {
813: arc = (Arc) arcsSortants.get(i);
814: if (groupe.getListeArcs().contains(arc)) {
815: if ((arc.getOrientation() == 1)
816: || (arc.getOrientation() == 2)) {
817: if (arc.getNoeudFin() != null) {
818: arcsSortants2.add(arc);
819: noeudsSortants2.add((Noeud) arc.getNoeudFin());
820: distancesSortants2.add(new Double(arc
821: .getPoids()));
822: }
823: }
824: }
825: }
826:
827: // en choisissant l'arc le plus court, si il existe des arcs parallèles (mêmes noeuds ini et fin)
828: for (i = 0; i < noeudsSortants2.size(); i++) {
829: // choix du plus court arc menant au noeud sortant
830: noeud = (Noeud) noeudsSortants2.get(i);
831: if (noeudsVoisins.contains(noeud))
832: continue;
833: arc = (Arc) arcsSortants2.get(i);
834: distance = (Double) distancesSortants2.get(i);
835: for (j = i + 1; j < noeudsSortants2.size(); j++) {
836: if (noeud == (Noeud) noeudsSortants2.get(j)) {
837: if (((Double) distancesSortants2.get(j))
838: .doubleValue() < distance.doubleValue()) {
839: distance = (Double) distancesSortants2.get(j);
840: arc = (Arc) arcsSortants2.get(j);
841: }
842: }
843: }
844: arcsVoisins.add(arc);
845: noeudsVoisins.add(noeud);
846: distancesVoisins.add(distance);
847: }
848: }
849:
850: ///////////////////////////////////////////////////////
851: // DIVERS
852: ///////////////////////////////////////////////////////
853:
854: /** Direction (Angle entre 0 et 2PI) de l'arc à la sortie du noeud this.
855: * Cette direction est calculée à partir d'une partie de l'arc d'une certaine
856: * longueur (paramètre), et en ré-échantillonant l'arc (paramètre).
857: * Si l'arc n'a pas pour noeud initial ou final this: renvoie null.
858: *
859: * @param longueurEspaceTravail :
860: * Longueur curviligne qui détermine l'espace de travail autour du noeud,
861: * Si elle est égale à 0: les deux premiers points de l'arc sont considérés.
862: *
863: * @param pasEchantillonage :
864: * Avant le calcul de la direction moyenne des points, la ligne est rééchantillonée à ce pas.
865: * Si égal à 0: aucun échantillonage n'est effectué
866: *
867: */
868: public Angle directionArc(Arc arc, double longueurEspaceTravail,
869: double pasEchantillonage) {
870: DirectPositionList listePts, arcEchantillone;
871: int nbPts;
872: if (arc.getNoeudFin() == this ) {
873: listePts = Operateurs.derniersPoints(arc.getGeometrie(),
874: longueurEspaceTravail);
875: if (listePts.size() < 2) {
876: nbPts = arc.getGeometrie().coord().size();
877: listePts.add(arc.getGeometrie().coord().get(nbPts - 2));
878: }
879: } else if (arc.getNoeudIni() == this ) {
880: listePts = Operateurs.premiersPoints(arc.getGeometrie(),
881: longueurEspaceTravail);
882: if (listePts.size() < 2) {
883: listePts.add(arc.getGeometrie().coord().get(1));
884: }
885: } else
886: return null;
887:
888: if (pasEchantillonage == 0)
889: arcEchantillone = listePts;
890: else
891: arcEchantillone = Operateurs.echantillonePasVariable(
892: new GM_LineString(listePts), pasEchantillonage)
893: .coord();
894: return Operateurs.directionPrincipaleOrientee(arcEchantillone);
895: }
896:
897: }
|