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.graphe;
028:
029: import java.util.Iterator;
030:
031: import fr.ign.cogit.geoxygene.contrib.cartetopo.Arc;
032: import fr.ign.cogit.geoxygene.contrib.cartetopo.CarteTopo;
033: import fr.ign.cogit.geoxygene.contrib.cartetopo.Noeud;
034: import fr.ign.cogit.geoxygene.feature.FT_Feature;
035: import fr.ign.cogit.geoxygene.feature.FT_FeatureCollection;
036: import fr.ign.cogit.geoxygene.spatial.coordgeom.GM_LineString;
037: import fr.ign.cogit.geoxygene.spatial.geomprim.GM_Point;
038:
039: /**
040: * Méthodes statiques pour la création d'un ARM (Arbre de Recouvrement Minimal,
041: * Minimal Spanning Tree)
042: *
043: * @author Mustiere - IGN / Laboratoire COGIT
044: * version 1.0
045: *
046: */
047: public class ARM {
048:
049: /** Création d'un ARM à partir d'un ensemble de points
050: *
051: * Cette méthode est très brutale: adaptée pour quelques points seulement.
052: * On fait des calculs de distance beaucoup trop souvent.
053: * L'ARM étant un sous-graphe de Delaunay, cela peut être grandement optimisé en
054: * effectuant un Delaunay d'abord.
055: *
056: * @param points
057: * Liste d'objets en entrée: ils doivent avoir une géométrie de type point
058: *
059: * @return
060: * Une carte topo contenant un noeud pour chaque point,
061: * et un arc pour chaque tronçon du ARM
062: * ("correspondant" est instancié pour relier les noeuds et les points).
063: */
064: public static CarteTopo creeARM(FT_FeatureCollection points) {
065: Noeud noeud, nouveauNoeud;
066: Arc arc;
067: FT_Feature point;
068: double dist, distMin;
069: CarteTopo arm = new CarteTopo("AMR");
070: int i, j, imin = 0, jmin = 0;
071: GM_LineString trait;
072: FT_FeatureCollection pointsCopie = new FT_FeatureCollection(
073: points);
074:
075: if (pointsCopie.size() == 0)
076: return null;
077:
078: // Amorce, on prend un point au hasard: le premier
079: point = pointsCopie.get(0);
080: if (!(point.getGeom() instanceof GM_Point)) {
081: System.out
082: .println("Un des objets en entrée n'est pas un point, renvoie Null");
083: return null;
084: }
085: pointsCopie.remove(point);
086: nouveauNoeud = (Noeud) arm.getPopNoeuds().nouvelElement();
087: nouveauNoeud.setGeom(point.getGeom());
088: nouveauNoeud.addCorrespondant(point);
089: // Ajout des points un à un
090: while (true) {
091: if (pointsCopie.size() == 0)
092: break; //ça y est, on a relié tous les points
093:
094: //on cherche le couple noeud-point le pus proche (TRES bourrin)
095: distMin = Double.MAX_VALUE;
096: for (i = 0; i < pointsCopie.size(); i++) {
097: point = (FT_Feature) pointsCopie.get(i);
098: if (!(point.getGeom() instanceof GM_Point)) {
099: System.out
100: .println("Un des objets en entrée n'est pas un point, renvoie Null");
101: return null;
102: }
103:
104: for (j = 0; j < arm.getPopNoeuds().size(); j++) {
105: noeud = (Noeud) arm.getPopNoeuds().get(j);
106: dist = noeud.getGeom().distance(point.getGeom());
107: if (dist < distMin) {
108: distMin = dist;
109: imin = i;
110: jmin = j;
111: }
112: }
113: }
114: point = (FT_Feature) pointsCopie.get(imin);
115: noeud = (Noeud) arm.getPopNoeuds().get(jmin);
116:
117: // on remplit l'ARM
118: pointsCopie.remove(point);
119: nouveauNoeud = (Noeud) arm.getPopNoeuds().nouvelElement();
120: nouveauNoeud.setGeom(point.getGeom());
121: nouveauNoeud.addCorrespondant(point);
122: arc = (Arc) arm.getPopArcs().nouvelElement();
123: arc.setNoeudIni(noeud);
124: arc.setNoeudFin(nouveauNoeud);
125: trait = new GM_LineString();
126: trait.addControlPoint(arc.getNoeudIni().getGeometrie()
127: .getPosition());
128: trait.addControlPoint(arc.getNoeudFin().getGeometrie()
129: .getPosition());
130: arc.setGeometrie(trait);
131: }
132:
133: return arm;
134:
135: }
136:
137: /** Methode pour créer un ARM à partir des centroides d'un ensemble d'objets.
138: *
139: * @param objets
140: * Liste d'objets en entrée: ils doivent avoir une géométrie quelconque
141: *
142: * @return
143: * Une carte topo contenant un noeud pour chaque point,
144: * et un arc pour chaque tronçon du ARM
145: * ("correspondant" est instancié pour relier les noeuds et les points).
146: *
147: */
148: public static CarteTopo creeARMsurObjetsQuelconques(
149: FT_FeatureCollection objets) {
150: FT_FeatureCollection points = new FT_FeatureCollection();
151:
152: Iterator itObjets = objets.getElements().iterator();
153: while (itObjets.hasNext()) {
154: FT_Feature objet = (FT_Feature) itObjets.next();
155: if (objet.getGeom() == null) {
156: System.out
157: .println("Un des objets en entrée n'a pas de géométrie, renvoie Null");
158: return null;
159: }
160: Noeud objet2 = new Noeud();
161: objet2.setGeom(objet.getGeom().centroid());
162: points.add(objet2);
163: }
164: return creeARM(points);
165: }
166:
167: }
|