samedi 31 mars 2007
PgRouting - autres tests avec plus de rond-points - fonction A* - 2/3
Par david techer, samedi 31 mars 2007 à 19:56 :: PostGIS et PostgreSQL
Bon je me suis amusé à reprendre le réseau que j'avais pris dans mon précédent billet - billet concernant l'installation de PgRouting sous Ubuntu - pour lui ajouter de nouveaux tronçons en utilisant OpenJump. Pour se faire, j'ai importé ma table postgis de mon graphe précédent. En utilisant depuis le menu de OpenJump - dans les menu - "Ajout de nouvelles", j'ai complété le dessin. J'ai ensuite tout exporté en shapefile que j'ai nommé troncon_route.shp - toujours grâce à OpenJump -. Il est cool cet outil 
.
shp2pgsql -dDI troncon_route.shp troncon_route| psql -h 192.168.0.5 -U postgres geocodingN.B: Le shapefile en question peut être téléchargé à http://www.davidgis.fr/download/troncon_route.zip.> Il ne contient rien d'extraordinaire pour le moment:
SELECT gid,sens,astext(the_geom) FROM troncon_route ORDER BY gid "
gid | sens | astext
-----+-------------+--------------------------------------
1 | double sens | MULTILINESTRING((1 0,5 0))
2 | double sens | MULTILINESTRING((5 0,5 6))
3 | double sens | MULTILINESTRING((0 7.5,3 7.5))
4 | sens direct | MULTILINESTRING((3 7.5,3 7,4 6,5 6))
5 | sens direct | MULTILINESTRING((5 6,6 6,7 7,7 7.5))
6 | sens direct | MULTILINESTRING((7 7.5,7 8,6 9,5 9))
7 | sens direct | MULTILINESTRING((5 9,4 9,3 8,3 7.5))
8 | double sens | MULTILINESTRING((7 7.5,11 7.5))
9 | double sens | MULTILINESTRING((11 7.5,11 11))
10 | double sens | MULTILINESTRING((11 7.5,14 7.5))
11 | double sens | MULTILINESTRING((14 7.5,21 7.5))
... | double sens | MULTILINESTRING((..................))
Bon je suis pas un grand spéclialiste du dessin - ça on s'en doute 
- mais au final celà ressemble à ça:
Fig 1. Mon graphe simulant un réseau routier avec rond-points.
Fig 2. Noeuds de mon graphe qui serviront de sources et de targets .
troncon_route_edges, je l'ai créé en faisant, les requêtes SQL suivantes. Par rapport à mon précédent billet, j'ai quand même réussi à améliorer les requêtes.
BEGIN TRANSACTION;
--SELECT dropgeometrytable('troncon_route');
SELECT drop_graph_tables('troncon_route');
/*
Ajouter les colonnes adéquates
*/
ALTER TABLE troncon_route ADD column source_id int4;
ALTER TABLE troncon_route ADD column target_id int4;
ALTER TABLE troncon_route ADD column edge_id int4;
/*
Mettre à jour le srid=1 sinon pgdijkstra gueule 8-(
*/
SELECT UPDATEgeometrysrid('troncon_route','the_geom',-1);
SELECT assign_vertex_id('troncon_route',0.00001);
/*
Ok...Je crée mon graphe
*/
SELECT create_graph_tables('troncon_route', 'int4');
--SELECT UPDATE_cost_FROM_distance('troncon_route');
ALTER TABLE troncon_route_edges ADD column sens text;
ALTER TABLE troncon_route_edges ADD column x1 double precision;
ALTER TABLE troncon_route_edges ADD column y1 double precision;
ALTER TABLE troncon_route_edges ADD column x2 double precision;
ALTER TABLE troncon_route_edges ADD column y2 double precision;
ALTER TABLE troncon_route_edges ADD column edge_id int4;
/*
Mise à jour des colonnes x1,y1,x2,y2 originaux par rapport aux données géométriques de la table troncon_route
et mise à jour des colonnes sens et edge_id
*/
UPDATE troncon_route_edges SET cost=(select length(the_geom) FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.the_geom);
UPDATE troncon_route_edges SET x1=(select x(startpoint(the_geom)) FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.the_geom);
UPDATE troncon_route_edges SET y1=(select y(startpoint(the_geom)) FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.the_geom);
UPDATE troncon_route_edges SET x2=(select x(endpoint(the_geom)) FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.the_geom);
UPDATE troncon_route_edges SET y2=(select y(endpoint(the_geom)) FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.the_geom);
UPDATE troncon_route_edges SET edge_id=(select edge_id FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.edge_id);
UPDATE troncon_route_edges SET sens=(select sens::text FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.sens);
SELECT AddGeometryColumn( 'troncon_route_edges', 'the_geom', -1, 'MULTILINESTRING', 2 );
UPDATE troncon_route_edges SET the_geom=(select the_geom FROM troncon_route g WHERE g.edge_id=id GROUP BY id,g.the_geom);
/*
Tout ce qui est à double sens je le garde
*/
UPDATE troncon_route_edges SET reverse_cost=cost;
/*
Paramétrer le coût des tronçons à sens unique
*/
UPDATE troncon_route_edges SET reverse_cost=-1 WHERE sens='sens direct';
END TRANSACTION;
VACUUM FULL ANALYZE ;
Maintenant, ma table troncon_route_edges est parfaitement complète car la requête
SELECT id,sens,astext(the_geom),x1,y1,x2,y2,source,target,edge_id,cost,reverse_cost FROM troncon_route_edges ORDER BY id LIMIT 10me renvoit
id | sens | astext | x1 | y1 | x2 | y2 | source | target | edge_id | cost | reverse_cost ----+-------------+--------------------------------------+----+-----+----+-----+--------+--------+---------+------------------+-------------- 1 | double sens | MULTILINESTRING((1 0,5 0)) | 1 | 0 | 5 | 0 | 1 | 2 | 1 | 4 | 4 2 | double sens | MULTILINESTRING((5 0,5 6)) | 5 | 0 | 5 | 6 | 2 | 3 | 2 | 6 | 6 3 | double sens | MULTILINESTRING((0 7.5,3 7.5)) | 0 | 7.5 | 3 | 7.5 | 4 | 5 | 3 | 3 | 3 4 | sens direct | MULTILINESTRING((3 7.5,3 7,4 6,5 6)) | 3 | 7.5 | 5 | 6 | 5 | 3 | 4 | 2.91421356237309 | -1 5 | sens direct | MULTILINESTRING((5 6,6 6,7 7,7 7.5)) | 5 | 6 | 7 | 7.5 | 3 | 6 | 5 | 2.91421356237309 | -1 6 | sens direct | MULTILINESTRING((7 7.5,7 8,6 9,5 9)) | 7 | 7.5 | 5 | 9 | 6 | 7 | 6 | 2.91421356237309 | -1 7 | sens direct | MULTILINESTRING((5 9,4 9,3 8,3 7.5)) | 5 | 9 | 3 | 7.5 | 7 | 5 | 7 | 2.91421356237309 | -1 8 | double sens | MULTILINESTRING((7 7.5,11 7.5)) | 7 | 7.5 | 11 | 7.5 | 6 | 8 | 8 | 4 | 4 9 | double sens | MULTILINESTRING((11 7.5,11 11)) | 11 | 7.5 | 11 | 11 | 8 | 9 | 9 | 3.5 | 3.5 10 | double sens | MULTILINESTRING((11 7.5,14 7.5)) | 11 | 7.5 | 14 | 7.5 | 8 | 10 | 10 | 3 | 3 (10 lignes)
J'obtiens des résultats très intéressants:
Fig 3. Parcours à l'aller.
Fig 4. Parcours au retour.
shortest_path_asta(SQL,source,target,true/false,true/false) pour avoir aller et le retour. Selon l'ordre celà me fait donc 8 possibilités: 4 ordres possibles pour l'aller et 4 pour le retour. Pour le retour, il suffit donc d'intervertir la place du source et du target. J'ai créé 8 tables associées chacune à un des ordre possibles. Par exemple ma première table sera associée à l'ordre source,target,,false,false, la seconde table sera associée à l'ordre source,target,false,true et ainsi de suite.... Je me suis fait un petit script shell - nommé test.sh - dont le contenu est le suivant
echo "begin transaction;
drop table if exists test1,test2,test3,test4,test5,test6,test7,test8;
create table test1(gid int4) with oids;SELECT AddGeometryColumn( 'test1', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test2(gid int4) with oids;SELECT AddGeometryColumn( 'test2', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test3(gid int4) with oids;SELECT AddGeometryColumn( 'test3', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test4(gid int4) with oids;SELECT AddGeometryColumn( 'test4', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test5(gid int4) with oids;SELECT AddGeometryColumn( 'test5', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test6(gid int4) with oids;SELECT AddGeometryColumn( 'test6', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test7(gid int4) with oids;SELECT AddGeometryColumn( 'test7', 'the_geom', -1, 'MULTILINESTRING', 2 );
create table test8(gid int4) with oids;SELECT AddGeometryColumn( 'test8', 'the_geom', -1, 'MULTILINESTRING', 2 );
insert into test1(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$1,$2,false,false)));
insert into test2(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$1,$2,false,true)));
insert into test3(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$1,$2,true,true)));
insert into test4(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$1,$2,true,false)));
insert into test5(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$2,$1,false,false)));
insert into test6(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$2,$1,false,true)));
insert into test7(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$2,$1,true,true)));
insert into test8(the_geom) (select the_geom from troncon_route_edges where edge_id in
(select edge_id from shortest_path_astar('select id,source::int4,target::int4,cost::double precision,
reverse_cost::double precision as reverse_cost, x1::double precision,y1::double precision,
x2::double precision,y2::double precision from troncon_route_edges',$2,$1,true,false)));
end transaction;"|psql -h 192.168.0.5 -U postgres geocoding
Pour l'exécuter, il me suffit de lui passer les paramètre suivants où source et target sont les noeuds de la figure 2.
./test.shPour l'exemple ici entre le noeud 38 et 48, j'ai simplement faitsourcetarget
./test4.sh 38 48L'affichage a ensuite eu lieu tout simplement sous QGIS
. 
...
...Il est bien reconnu sous Dapper mais quand j'insère un CD ou un DVD, rien ne se produit 
!...
. Bon pas de panique, direction le chan IRC de Ubuntu au cas où il y aurait un topic pour ce genre de graveur ou d'essayer de bidouiller quoique ce soit. Et là je tombe sur The_Marauder - ze master of ze master 
- qui veut bien me donner un coup de main! A 00h30, faut le faire quand même! Il est cool ce mec 
