svn-gvsig-desktop / trunk / extensions / extGraph / src / com / iver / cit / gvsig / graph / solvers / ShortestPathSolverAStar.java @ 14780
History | View | Annotate | Download (15.6 KB)
1 |
/* gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana
|
---|---|
2 |
*
|
3 |
* Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.
|
4 |
*
|
5 |
* This program is free software; you can redistribute it and/or
|
6 |
* modify it under the terms of the GNU General Public License
|
7 |
* as published by the Free Software Foundation; either version 2
|
8 |
* of the License, or (at your option) any later version.
|
9 |
*
|
10 |
* This program is distributed in the hope that it will be useful,
|
11 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
12 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
13 |
* GNU General Public License for more details.
|
14 |
*
|
15 |
* You should have received a copy of the GNU General Public License
|
16 |
* along with this program; if not, write to the Free Software
|
17 |
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
18 |
*
|
19 |
* For more information, contact:
|
20 |
*
|
21 |
* Generalitat Valenciana
|
22 |
* Conselleria d'Infraestructures i Transport
|
23 |
* Av. Blasco Ib??ez, 50
|
24 |
* 46010 VALENCIA
|
25 |
* SPAIN
|
26 |
*
|
27 |
* +34 963862235
|
28 |
* gvsig@gva.es
|
29 |
* www.gvsig.gva.es
|
30 |
*
|
31 |
* or
|
32 |
*
|
33 |
* IVER T.I. S.A
|
34 |
* Salamanca 50
|
35 |
* 46005 Valencia
|
36 |
* Spain
|
37 |
*
|
38 |
* +34 963163400
|
39 |
* dac@iver.es
|
40 |
*/
|
41 |
package com.iver.cit.gvsig.graph.solvers; |
42 |
|
43 |
import java.util.ArrayList; |
44 |
import java.util.Stack; |
45 |
|
46 |
import org.gvsig.exceptions.BaseException; |
47 |
|
48 |
import com.hardcode.gdbms.driver.exceptions.ReadDriverException; |
49 |
import com.hardcode.gdbms.engine.data.driver.DriverException; |
50 |
import com.iver.cit.gvsig.fmap.core.IFeature; |
51 |
import com.iver.cit.gvsig.fmap.core.IGeometry; |
52 |
import com.iver.cit.gvsig.fmap.core.v02.FConverter; |
53 |
import com.iver.cit.gvsig.fmap.layers.VectorialAdapter; |
54 |
import com.iver.cit.gvsig.graph.NetworkUtils; |
55 |
import com.iver.cit.gvsig.graph.core.AbstractNetSolver; |
56 |
import com.iver.cit.gvsig.graph.core.GlobalCounter; |
57 |
import com.iver.cit.gvsig.graph.core.GraphException; |
58 |
import com.iver.cit.gvsig.graph.core.GvEdge; |
59 |
import com.iver.cit.gvsig.graph.core.GvFlag; |
60 |
import com.iver.cit.gvsig.graph.core.GvNode; |
61 |
import com.iver.cit.gvsig.graph.core.IGraph; |
62 |
import com.vividsolutions.jts.geom.Coordinate; |
63 |
import com.vividsolutions.jts.geom.Geometry; |
64 |
import com.vividsolutions.jts.geom.GeometryFactory; |
65 |
import com.vividsolutions.jts.geom.LineString; |
66 |
import com.vividsolutions.jts.geom.MultiLineString; |
67 |
|
68 |
/**
|
69 |
* @author fjp Este es ?til solo cuando podemos calcular la distancia estimada
|
70 |
* entre 2 nodos. (Es decir, para temas de cartograf?a). Para analizar
|
71 |
* relaciones creo que no servir?a).
|
72 |
*/
|
73 |
public class ShortestPathSolverAStar extends AbstractNetSolver { |
74 |
|
75 |
protected Route route = new Route(); |
76 |
|
77 |
private int fieldIndexStreetName; |
78 |
|
79 |
private class InfoShp { |
80 |
public int idArc; |
81 |
|
82 |
public double pct; |
83 |
|
84 |
public double cost; |
85 |
|
86 |
public double distance; |
87 |
|
88 |
public int direction; |
89 |
|
90 |
public boolean bFlip; |
91 |
|
92 |
} |
93 |
|
94 |
public void setFielStreetName(String name) { |
95 |
try {
|
96 |
int aux = net.getLayer().getRecordset().getFieldIndexByName(name);
|
97 |
if (aux == -1) |
98 |
throw new RuntimeException("Field " + name + " not found."); |
99 |
fieldIndexStreetName = aux; |
100 |
} catch (BaseException e) {
|
101 |
// TODO Auto-generated catch block
|
102 |
e.printStackTrace(); |
103 |
} |
104 |
|
105 |
} |
106 |
|
107 |
/**
|
108 |
* @return a list of features
|
109 |
* @throws GraphException
|
110 |
*/
|
111 |
public Route calculateRoute() throws GraphException { |
112 |
GvFlag[] flags = net.getFlags();
|
113 |
if (flags.length == 0) |
114 |
throw new RuntimeException("Please, add flags before"); |
115 |
int desde = 0; |
116 |
int hasta = 1; |
117 |
double elCoste1 = 0; |
118 |
route = new Route();
|
119 |
GvFlag fFrom = flags[0];
|
120 |
fFrom.setCost(0);
|
121 |
for (int i = 0; i < flags.length - 1; i++) { |
122 |
fFrom = flags[desde]; |
123 |
GvFlag fTo = flags[hasta]; |
124 |
|
125 |
if (fFrom != fTo) {
|
126 |
int idStart = net.creaArcosVirtuales(fFrom);
|
127 |
int idStop = net.creaArcosVirtuales(fTo);
|
128 |
|
129 |
double newCost = AStar(idStart, idStop);
|
130 |
|
131 |
elCoste1 += newCost; |
132 |
fTo.setCost(elCoste1); |
133 |
|
134 |
if (newCost != Double.MAX_VALUE) { |
135 |
try {
|
136 |
populateRoute(fFrom, fTo, idStart, idStop); |
137 |
} catch (DriverException e) {
|
138 |
e.printStackTrace(); |
139 |
throw new GraphException(e); |
140 |
} |
141 |
} else {
|
142 |
// No way
|
143 |
} |
144 |
|
145 |
net.reconstruyeTramo(fFrom.getIdArc()); |
146 |
net.reconstruyeTramo(fTo.getIdArc()); |
147 |
desde = hasta; |
148 |
} // if son puntos distintos
|
149 |
hasta++; |
150 |
} |
151 |
|
152 |
return route;
|
153 |
} |
154 |
|
155 |
private void populateRouteSimple(int idStart, int idEnd) |
156 |
throws ReadDriverException {
|
157 |
int idEnlace;
|
158 |
GvNode node; |
159 |
GvEdge link; |
160 |
double costeEntrada;
|
161 |
|
162 |
// Trazar el camino desde idEnd hasta idStart hacia atr?s marcando los
|
163 |
// Enlaces
|
164 |
double Coste = 0; |
165 |
double Coste2 = 0; |
166 |
IGraph graph = net.getGraph(); |
167 |
node = graph.getNodeByID(idEnd); |
168 |
int from_link = node.getFromLink();
|
169 |
VectorialAdapter va = (VectorialAdapter) net.getLayer().getSource(); |
170 |
while (node.getIdNode() != idStart) {
|
171 |
if (from_link == -1) { |
172 |
throw new RuntimeException( |
173 |
"Fallo al recorrer de manera inversa la soluci?n. Encontrado arco con -1");
|
174 |
// break; // FALLO!!
|
175 |
} |
176 |
link = graph.getEdgeByID(from_link); |
177 |
IFeature feat = va.getFeature(link.getIdArc()); |
178 |
route.addRouteFeature(feat.getGeometry(), link.getIdArc(), link |
179 |
.getWeight(), link.getDistance(), feat.getAttribute( |
180 |
getFieldIndexStreetName()).toString()); |
181 |
|
182 |
node = graph.getNodeByID(link.getIdNodeOrig()); |
183 |
|
184 |
Coste = Coste + link.getWeight(); |
185 |
Coste2 = Coste2 + link.getDistance(); |
186 |
|
187 |
// TODO:
|
188 |
// from_link = node.get_from_link(idEnlace, &costeEntrada);
|
189 |
from_link = node.getFromLink(); |
190 |
|
191 |
} |
192 |
System.out.println("Salgo con node = " + node.getIdNode()); |
193 |
} |
194 |
|
195 |
private void populateRoute(GvFlag origin, GvFlag dest, int idStart, |
196 |
int idEnd) throws DriverException { |
197 |
int idEnlace;
|
198 |
GvNode node; |
199 |
GvEdge link; |
200 |
double costeEntrada;
|
201 |
|
202 |
// Trazar el camino desde idEnd hasta idStart hacia atr?s marcando los
|
203 |
// Enlaces
|
204 |
|
205 |
if (idStart == idEnd)
|
206 |
return;
|
207 |
IGraph graph = net.getGraph(); |
208 |
node = graph.getNodeByID(idEnd); |
209 |
int from_link = node.getFromLink();
|
210 |
VectorialAdapter va = (VectorialAdapter) net.getLayer().getSource(); |
211 |
try {
|
212 |
va.start(); |
213 |
/*
|
214 |
* Miramos los nodos de los tramos inicio y final, y cogemos el nodo
|
215 |
* que tenga el from_link rellenado. E IGUAL A NUMSOLUCGLOBAL!!!! A
|
216 |
* partir de ah?, recorremos hacia atr?s y tenemos el cuerpo
|
217 |
* principal del shape. Luego, para las puntas hay que tener en
|
218 |
* cuenta los porcentajes, viendo el trozo que est? pegando a los
|
219 |
* nodos que sabemos que est?n en el path
|
220 |
*/
|
221 |
|
222 |
/*
|
223 |
* 22/9/2003 Corregimos el fallo que hab?a de escribir el shape de
|
224 |
* atr?s adelante. Guardamos lo que necesitamos en listaShapes y
|
225 |
* recorremos esa lista guardando los tramos con el sentido
|
226 |
* adecuado.
|
227 |
*/
|
228 |
|
229 |
/*
|
230 |
* 3/Febrero/2005 Limpieza de c?digo superfluo y correci?n de un
|
231 |
* fallo raro. Ahora es m?s simple y parece que no falla. A ver si
|
232 |
* dura. IDEA: quiz?s se necesite meter el porcentaje en los arcos
|
233 |
* partidos.
|
234 |
*/
|
235 |
|
236 |
// Define a template class for a vector of IDs.
|
237 |
InfoShp infoShp; |
238 |
Stack pilaShapes = new Stack(); |
239 |
// typedef stack<CInfoShp> PILAINFO;
|
240 |
// PILAINFO pilaShapes;
|
241 |
|
242 |
double costeTramoFinal = -1; |
243 |
GvNode nodeEnd = graph.getNodeByID(idEnd); |
244 |
GvEdge finalEdge = graph.getEdgeByID(nodeEnd.getFromLink()); |
245 |
costeTramoFinal = finalEdge.getWeight(); |
246 |
|
247 |
GvNode pNodo; |
248 |
GvEdge pEnlace; |
249 |
|
250 |
boolean bFlipearShape = false; |
251 |
|
252 |
double pctMax, pctMin;
|
253 |
|
254 |
// ////////////////////////////////////////////////////////////////////////////////////
|
255 |
// Trozo del final
|
256 |
// El shape va de idStop1 a idStop2, y el porcentaje viene en ese
|
257 |
// sentido.
|
258 |
// Si el idEnd es idStop1, quiere decir que el tramo que falta va en
|
259 |
// ese sentido tambi?n,
|
260 |
// as? que recorremos ese shape desde idStop1 hasta que rebasemos o
|
261 |
// igualemos ese porcentaje.
|
262 |
// Si no, hemos pasado por idStop2 y la parte que hay que meter es
|
263 |
// desde el pto interior a idStop2
|
264 |
// /////////////////////////////////////////////////////////////////////////////////////
|
265 |
IFeature feat = va.getFeature(finalEdge.getIdArc()); |
266 |
MultiLineString jtsGeom = (MultiLineString) feat.getGeometry() |
267 |
.toJTSGeometry(); |
268 |
// CoordinateFilter removeDuplicates = new
|
269 |
// UniqueCoordinateArrayFilter();
|
270 |
// jtsGeom.apply(removeDuplicates);
|
271 |
// jtsGeom.geometryChanged();
|
272 |
|
273 |
// SI ESTAMOS SOBRE EL MISMO TRAMO, CASO PARTICULAR
|
274 |
// y el sentido de circulaci?n es correcto
|
275 |
if ((origin.getIdArc() == dest.getIdArc())
|
276 |
&& (nodeEnd.getBestCost() <= costeTramoFinal)) { |
277 |
if (dest.getPct() > origin.getPct()) {
|
278 |
pctMax = dest.getPct(); |
279 |
pctMin = origin.getPct(); |
280 |
} else {
|
281 |
pctMax = origin.getPct(); |
282 |
pctMin = dest.getPct(); |
283 |
bFlipearShape = true;
|
284 |
} |
285 |
|
286 |
LineString line = NetworkUtils.getPartialLineString(jtsGeom, |
287 |
dest.getPct(), 1);
|
288 |
|
289 |
pctMin = pctMin / pctMax; // Porque ha cambiado la longitud
|
290 |
// del shape
|
291 |
|
292 |
line = NetworkUtils.getPartialLineString(line, pctMin, 0);
|
293 |
|
294 |
if (bFlipearShape)
|
295 |
line = line.reverse(); |
296 |
|
297 |
IGeometry geom = FConverter.jts_to_igeometry(line); |
298 |
// TODO: Calcular bien el length de este arco,
|
299 |
// basandonos en el porcentaje costeTramoFinal / costeOriginal
|
300 |
route.addRouteFeature(geom, origin.getIdArc(), costeTramoFinal, |
301 |
line.getLength(), feat.getAttribute( |
302 |
getFieldIndexStreetName()).toString()); |
303 |
|
304 |
return; // Deber?a sacar el coste |
305 |
} |
306 |
|
307 |
// Trazar el camino desde idEnd hasta idStart hacia atr?s marcando
|
308 |
// los Enlaces
|
309 |
pNodo = graph.getNodeByID(idEnd); |
310 |
|
311 |
while ((pNodo.getIdNode() != idStart)) {
|
312 |
idEnlace = pNodo.getFromLink(); |
313 |
pEnlace = graph.getEdgeByID(idEnlace); |
314 |
|
315 |
pNodo = graph.getNodeByID(pEnlace.getIdNodeOrig()); |
316 |
|
317 |
infoShp = new InfoShp();
|
318 |
infoShp.distance = pEnlace.getDistance(); |
319 |
infoShp.cost = pEnlace.getWeight(); |
320 |
|
321 |
if ((pEnlace.getIdArc() == origin.getIdArc())
|
322 |
|| (pEnlace.getIdArc() == dest.getIdArc())) { |
323 |
if (pEnlace.getIdArc() == origin.getIdArc()) {
|
324 |
infoShp.pct = origin.getPct(); |
325 |
infoShp.idArc = origin.getIdArc(); |
326 |
if (pEnlace.getDirec() == 0) { |
327 |
infoShp.direction = 1;
|
328 |
infoShp.bFlip = true;
|
329 |
} else // Hemos pasado por el 2 |
330 |
{ |
331 |
infoShp.direction = 0;
|
332 |
infoShp.bFlip = false;
|
333 |
} // if else */
|
334 |
} else {
|
335 |
infoShp.pct = dest.getPct(); |
336 |
infoShp.idArc = dest.getIdArc(); |
337 |
if (pEnlace.getDirec() == 0) { |
338 |
infoShp.direction = 0;
|
339 |
infoShp.bFlip = true;
|
340 |
} else {
|
341 |
infoShp.direction = 1;
|
342 |
infoShp.bFlip = false;
|
343 |
} // if else */
|
344 |
} |
345 |
} else {
|
346 |
infoShp.pct = 1.0;
|
347 |
infoShp.idArc = pEnlace.getIdArc(); |
348 |
|
349 |
infoShp.direction = 1;
|
350 |
if (pEnlace.getDirec() == 1) |
351 |
infoShp.bFlip = false;
|
352 |
else
|
353 |
infoShp.bFlip = true;
|
354 |
} |
355 |
|
356 |
pilaShapes.push(infoShp); |
357 |
} |
358 |
|
359 |
// Y ahora recorremos hacia atr?s el vector y escribimos los shapes.
|
360 |
// VECTORINFO::iterator theIterator;
|
361 |
int auxC = 0; |
362 |
|
363 |
while (!pilaShapes.empty()) {
|
364 |
infoShp = (InfoShp) pilaShapes.peek(); |
365 |
feat = va.getFeature(infoShp.idArc); |
366 |
MultiLineString line = (MultiLineString) feat.getGeometry() |
367 |
.toJTSGeometry(); |
368 |
// line.apply(removeDuplicates);
|
369 |
// line.geometryChanged();
|
370 |
|
371 |
LineString aux = null;
|
372 |
if (infoShp.pct < 1.0) |
373 |
aux = NetworkUtils.getPartialLineString(line, infoShp.pct, |
374 |
infoShp.direction); |
375 |
|
376 |
IGeometry geom = null;
|
377 |
if (aux == null) { |
378 |
if (infoShp.bFlip)
|
379 |
line = line.reverse(); |
380 |
geom = FConverter.jts_to_igeometry(line); |
381 |
} else {
|
382 |
if (infoShp.bFlip)
|
383 |
aux = aux.reverse(); |
384 |
geom = FConverter.jts_to_igeometry(aux); |
385 |
} |
386 |
|
387 |
route.addRouteFeature(geom, infoShp.idArc, infoShp.cost, |
388 |
infoShp.distance, feat.getAttribute( |
389 |
getFieldIndexStreetName()).toString()); |
390 |
|
391 |
pilaShapes.pop(); |
392 |
auxC++; |
393 |
|
394 |
} |
395 |
va.stop(); |
396 |
} catch (BaseException e) {
|
397 |
// TODO Auto-generated catch block
|
398 |
e.printStackTrace(); |
399 |
} |
400 |
|
401 |
return;
|
402 |
|
403 |
} |
404 |
|
405 |
|
406 |
private int getFieldIndexStreetName() { |
407 |
return fieldIndexStreetName;
|
408 |
} |
409 |
|
410 |
private double AStar(int idStart, int idStop) { |
411 |
int nodeNum;
|
412 |
int linkNum;
|
413 |
double newCost;
|
414 |
int idSiguienteNodo;
|
415 |
GvNode node, toNode, finalNode, bestNode; // , *pNodoProv;
|
416 |
GvEdge link; |
417 |
boolean bExit = false; |
418 |
|
419 |
boolean bGiroProhibido;
|
420 |
ArrayList candidatos = new ArrayList(); |
421 |
|
422 |
// char Mensaje[200];
|
423 |
|
424 |
IGraph graph = net.getGraph(); |
425 |
|
426 |
// NUEVO: 27-6-2003
|
427 |
// Cada nodo y cada arco llevan un nuemero de soluci?n. Se supone
|
428 |
// que si lo del nodo y el arco no coincide con
|
429 |
// este numero, todav?a no ha sido inicializado y hay que hacerlo.
|
430 |
// Para evitar coincidencias cuando de la vuelta el contador, cada
|
431 |
// 65000 peticiones (por ejemplo), repasamos toda
|
432 |
// la red y ponemos numSolucGlobal a -1
|
433 |
if (GlobalCounter.increment())
|
434 |
{ |
435 |
for (nodeNum = 0; nodeNum < graph.numVertices(); nodeNum++) { |
436 |
node = graph.getNodeByID(nodeNum); |
437 |
node.initialize(); |
438 |
} // for nodeNum */
|
439 |
} |
440 |
|
441 |
candidatos.clear(); |
442 |
// A?adimos el Start Node a la lista de candidatosSTL
|
443 |
// Nodo final
|
444 |
finalNode = graph.getNodeByID(idStop); |
445 |
finalNode.initialize(); |
446 |
|
447 |
node = graph.getNodeByID(idStart); |
448 |
node.initialize(); |
449 |
bestNode = node; |
450 |
|
451 |
candidatos.add(node); |
452 |
node.setBestCost(0);
|
453 |
node.setStatus(GvNode.statNowInList); |
454 |
node.calculateStimation(finalNode, 0);
|
455 |
|
456 |
// Mientras que la lista de candidatosSTL no est? vac?a, procesamos
|
457 |
// Nodos
|
458 |
double bestStimation;
|
459 |
|
460 |
while ((!bExit) && (candidatos.size() > 0)) { |
461 |
// Buscamos el nodo con m?nimo coste
|
462 |
node = (GvNode) candidatos.get(0);
|
463 |
bestNode = node; |
464 |
bestStimation = node.getStimation(); |
465 |
for (nodeNum = 1; nodeNum < candidatos.size(); nodeNum++) { |
466 |
node = (GvNode) candidatos.get(nodeNum); |
467 |
if (node.getStimation() < bestStimation) {
|
468 |
bestStimation = node.getStimation(); |
469 |
bestNode = node; |
470 |
} |
471 |
} // for nodeNum candidatosSTL
|
472 |
|
473 |
node = bestNode; |
474 |
// Borramos el mejor nodo de la lista de candidatosSTL
|
475 |
node.setStatus(GvNode.statWasInList); |
476 |
// TODO: BORRAR POR INDEX, NO AS?. ES M?S LENTO QUE SI BORRAMOS EL
|
477 |
// i-?simo.
|
478 |
candidatos.remove(node); |
479 |
// System.out.println("LINK " + link.getIdArc() + " from ");
|
480 |
// System.out.println("from " + idStart + " to " +
|
481 |
// finalNode.getIdNode() + ". node=" + node.getIdNode());
|
482 |
// Miramos si hemos llegado donde quer?amos
|
483 |
if (bestNode.getIdNode() == idStop) {
|
484 |
bExit = true;
|
485 |
break;
|
486 |
} |
487 |
|
488 |
// sprintf(Mensaje,"Enlaces en el nodo %ld:
|
489 |
// %ld.",pNodo->idNodo,pNodo->Enlaces.GetSize());
|
490 |
// AfxMessageBox(Mensaje);
|
491 |
|
492 |
// A?adimos a la lista de candidatosSTL los vecinos del nodo que
|
493 |
// acabamos de borrar
|
494 |
// HAY Arcos QUE SALEN Y Arcos QUE LLEGAN. SOLO MIRAMOS LOS QUE
|
495 |
// SALEN.
|
496 |
for (linkNum = 0; linkNum < node.getEnlaces().size(); linkNum++) { |
497 |
// Pillamos el nodo vecino
|
498 |
link = (GvEdge) node.getEnlaces().get(linkNum); |
499 |
idSiguienteNodo = link.getIdNodeEnd(); |
500 |
|
501 |
toNode = graph.getNodeByID(idSiguienteNodo); |
502 |
|
503 |
// 27_5_2004
|
504 |
// Si un arco tiene coste negativo, lo ignoramos
|
505 |
if (link.getWeight() < 0) |
506 |
continue;
|
507 |
|
508 |
// Fin arco con coste negativo
|
509 |
|
510 |
// NUEVO: 26-7-2003: Comprobamos si est? inicializado
|
511 |
if (toNode.getNumSoluc() != GlobalCounter.getGlobalSolutionNumber()) {
|
512 |
toNode.initialize(); |
513 |
} else {
|
514 |
// System.out.println("Nodo ya inicializado");
|
515 |
} |
516 |
|
517 |
// Miramos a ver si podemos mejorar su best_cost
|
518 |
newCost = node.getBestCost() + link.getWeight(); |
519 |
|
520 |
if (newCost < toNode.getBestCost()) {
|
521 |
// Es una mejora, as? que actualizamos el vecino y
|
522 |
// lo a?adimos a los candidatosSTL
|
523 |
toNode.setBestCost(newCost); |
524 |
toNode.setFromLink(link.getIdEdge()); |
525 |
|
526 |
toNode.calculateStimation(finalNode, newCost); |
527 |
|
528 |
if (toNode.getStatus() != GvNode.statNowInList) {
|
529 |
toNode.setStatus(GvNode.statNowInList); |
530 |
candidatos.add(toNode); |
531 |
} |
532 |
} // Si hay mejora
|
533 |
|
534 |
} // for linkNum
|
535 |
} // while candidatosSTL
|
536 |
|
537 |
newCost = finalNode.getBestCost(); |
538 |
|
539 |
return newCost;
|
540 |
} |
541 |
|
542 |
} |