Apr

29

pgDIJKSTRA 2-way

Filed Under PostGIS | 3 Comments

Dari milis mapserver-id seputar fungsi pgDijkstra untuk routing 2-arah. Udah agak lama juga sih tapi sebenarnya pengen dicoba dulu sebelum diposting di sini. Cuma karena kesibukan yang sangat saat ini, ditumpahkan apa adanya dulu deh ;)

Sekedar mau menambahkan. pgdijkstra sebenarnya bisa dipakai untuk perhitungan jalan searah.
Caranya field cost dan reverse_cost keduanya diisi.
Untuk arah yang tidak bisa dilalui diberi nilai yang besar, mis. ditambahkan 1000000.
Untuk jelasnya bisa baca di sini

Tutorial dalam link di atas menggunakan pgRouting, tapi cara yang sama bisa diterapkan pada pgdijkstra. Saya sendiri sudah mencoba cara ini pada pgdijkstra. Cuma untuk display pathnya, fungsi shortest_path_as_geometry yang ada pada pgdijkstra perlu sedikit dimodifikasi karena fungsi yang diberikan tidak memperhitungkan reverse_cost untuk menghasilkan pathnya.
Satu hal yg perlu diperhatikan arah arc mengikuti arah digitize. Ini yang agak repot krn adakalanya data jalan tidak di-digitize mengikuti arah jalan sebenarnya. Saya sendiri waktu mau menerapkan jalan 1-arah dg cara di atas, terpaksa mencek arah digitize dari shapefile yang ada. Cukup repot, lebih mudah kalo digitize sendiri datanya mengikuti arah jalan yg benar.
Menyambung posting saya sebelumnya, berikut saya kirimkan fungsi PL/pgSQL untuk menampilkan shortest path dg memperhitungkan reverse_cost. Fungsi-fungsi ini dimodifikasi dari modul pgDijkstra dari Sylvain Pasche. Untuk menampilkan shortest path dg memperhitungkan reverse_cost digunakan fungsi shortest_path_as_geometry_dir(). Penggunaannya sama persis dengan fungsi shortest_path_as_geometry() yang asli (lihat README_dijkstra_pgsq.txt dari paket modul pgDijkstra). Fungsi shortest_path_as_geometry_dir() memanggil fungsi shortest_path_as_geometry_internal_id_dir(), yg merupakan modifikasi dari shortest_path_as_geometry_internal_id(). Di fungsi inilah letak perbedaannya. Dalam fungsi shortest_path_as_geometry_internal_id_dir() fungsi shortest_path(sql text, source_id integer, target_id integer, directed boolean, has_reverse_cost boolean) dipanggil dg argumen directed = true dan has_reverse_cost = true.
Saya rasa cukup penjelasannya. Selanjutnya bisa lihat langsung kedua fungsi di bawah.

Selamat mencoba.

Thanks,
Ardi

-- Function: shortest_path_as_geometry_dir(geom_table “varchar”, geom_source anyelement, geom_target anyelement)
CREATE OR REPLACE FUNCTION shortest_path_as_geometry_dir(geom_table “VARCHAR”, geom_source anyelement, geom_target anyelement)
RETURNS SETOF geoms AS
$BODY$
DECLARE
r RECORD;
source int4;
target int4;
path_result RECORD;
v_id INTEGER;
e_id INTEGER;
geom geoms;
BEGIN
FOR r IN EXECUTE ‘SELECT id FROM ‘ || quote_ident(geom_table) || ‘_vertices WHERE geom_id = ‘ || quote_literal(geom_source) LOOP
source = r.id;
END LOOP;
IF source IS NULL THEN
RAISE EXCEPTION ‘Can”t find source edge’;
END IF;
FOR r IN EXECUTE ‘SELECT id FROM ‘ || quote_ident(geom_table) || ‘_vertices WHERE geom_id = ‘ || quote_literal(geom_target) LOOP
target = r.id;
END LOOP;
IF target IS NULL THEN
RAISE EXCEPTION ‘Can”t find target edge’;
END IF;
 
FOR geom IN SELECT * FROM shortest_path_as_geometry_internal_id_dir(geom_table, source, target) LOOP
RETURN NEXT geom;
END LOOP;
RETURN;
END;
$BODY$
LANGUAGE ‘plpgsql’ VOLATILE STRICT;
ALTER FUNCTION shortest_path_as_geometry_dir(geom_table “VARCHAR”, geom_source anyelement, geom_target anyelement) OWNER TO postgres;
-- Function: shortest_path_as_geometry_internal_id_dir(geom_table “varchar”, source int4, target int4)
CREATE OR REPLACE FUNCTION shortest_path_as_geometry_internal_id_dir(geom_table “VARCHAR”, source int4, target int4)
RETURNS SETOF geoms AS
$BODY$
DECLARE
r RECORD;
path_result RECORD;
v_id INTEGER;
e_id INTEGER;
geom geoms;
BEGIN
FOR path_result IN EXECUTE ‘SELECT vertex_id, edge_id FROM shortest_path(”SELECT id, source, target, cost, reverse_cost FROM ‘ ||
quote_ident(geom_table) || ‘_edges ”, ‘ || quote_literal(source) || ‘ , ‘ || quote_literal(target) || ‘ , TRUE, TRUE) ‘ LOOP
v_id = path_result.vertex_id;
e_id = path_result.edge_id;
FOR r IN EXECUTE ‘SELECT gid, the_geom FROM ‘ || quote_ident(geom_table) || ‘ WHERE edge_id = ‘ || quote_literal(e_id) LOOP
geom.gid := r.gid;
geom.the_geom := r.the_geom;
RETURN NEXT geom;
END LOOP;
END LOOP;
RETURN;
END;
$BODY$
LANGUAGE ‘plpgsql’ VOLATILE STRICT;
ALTER FUNCTION shortest_path_as_geometry_internal_id_dir(geom_table “VARCHAR”, source int4, target int4) OWNER TO postgres;