[postgis-users] Help with pgdijkstra

[Darren Houston]

Hello Marc, 

Your explanation makes perfect sense. Now I understand how pgdijkstra works. 
Long story short; my current dataset will not work with pgdijkstra. I have 
written some routines that automatically clean up my dataset and apply the 
pgdijkstra functions. It's hit and miss, but I am getting some expected 
results.

Thanks for the help Marc,

Darren H.

On Wednesday 07 February 2007 01:39, Marc Compte wrote:
> Hi Darren,
>
> Actually, I think in both of your examples the algorithm works good,
> doesn't it?
>
> In reality there are always cases where two linear objects (say roads)
> will be represented as crossing, but will have no real connection
> between them. For instance, a road crossing another road over a bridge
> will be represented on a flat map as crossing each other, but in reality
> a car in one road can't take the other one as they are at different Zs.
> Or two pipelines that cross each other but are not connected (a.k.a.
> they share the same x and y but have different z).
>
> And that's what dijkstra does. To let the algorithm know that two lines
> are "connectable" you need them to have a shared node (start or end),
> but shared vertexes will not be a "point of contact" (and they probably
> should never be). The problem would not be so much on the algorithm side
> but on the layer you try to use it on. So you need to give a close look
> to your layer before using dijkstra on it and fix all those things.
>
> Does it make sense?
>
> Marc
>
> En/na Darren Houston ha escrit:
> > Oops, sent this to postgis-devel instead of postgis-users...
> >
> >
> >
> >
> > Hello everyone,
> >
> > I am trying out the pgdijkstra library and am having difficulties getting
> > it to work with my test dataset. Included is the sql to load the test
> > dataset, and a SVG and PNG output of what the dataset looks like.
> >
> > Running this sql works (finding the path from the start of the green line
> > to the end of the yellow line)
> >
> > SELECT gid,astext(the_geom) FROM shortest_path_as_geometry('line_test',
> > (select v.id from line_test_vertices v join line_test g on v.geom_id =
> > g.source_id where g.ident=1),
> > (select v.id from line_test_vertices v join line_test g on v.geom_id =
> > g.target_id where g.ident=3));
> >
> >
> > outputs
> >
> >
> > 5|"MULTILINESTRING((665249.377865961 5662895.69047619,670545.577160494
> > 5659332.79276896,668812.275573192 5654999.53880071,670449.282627866
> > 5649607.04497354,674589.947530864 5645658.9691358))"
> >
> > 6|"MULTILINESTRING((674589.947530864 5645658.9691358,671701.111552028
> > 5635259.15961199,663419.781746032 5641325.71516755,652634.794091711
> > 5639688.70811287))"
> >
> > 7|"MULTILINESTRING((652634.794091711 5639688.70811287,650708.903439153
> > 5631022.20017637,656486.575396825 5624859.35008818,663227.192680776
> > 5629096.30952381,667560.44664903 5623222.34303351,671315.933421517
> > 5623126.04850088,677767.667107584 5629481.48765432))"
> >
> >
> > Running this sql does not work (finding the path from the start of the
> > green line to the end of the red line)
> >
> > SELECT gid,astext(the_geom) FROM shortest_path_as_geometry('line_test',
> > (select v.id from line_test_vertices v join line_test g on v.geom_id =
> > g.source_id where g.ident=1),
> > (select v.id from line_test_vertices v join line_test g on v.geom_id =
> > g.target_id where g.ident=4));
> >
> >
> > outputs
> >
> >
> > ERROR:  Error computing path: No path found
> > CONTEXT:  PL/pgSQL function "shortest_path_as_geometry_internal_id" line
> > 9 at for over execute statement
> > PL/pgSQL function "shortest_path_as_geometry" line 24 at for over select
> > rows
> >
> >
> > Looking at the tables and columns  pgdijkstra creates / fills, it seems
> > that only the start and end vertices of a line are taken into
> > consideration, hence pgdijkstra thinks that the red line is not connected
> > to the network. Is this true? If so, any way to get pgdijkstra to work in
> > this situation? Any help / ideas form seasoned pgdijkstra users is
> > greatly appreciated.
> >
> > Thank you,
> >
> > Darren H.
> >
> > -------------------------------------------------------
> >
> >
> >
> >
> > ------------------------------------------------------------------------
> >
> > ------------------------------------------------------------------------
> >
> > BEGIN;
> > CREATE TABLE "line_test" (gid serial PRIMARY KEY, "ident" int4);
> > SELECT
> > AddGeometryColumn('','line_test','the_geom','-1','MULTILINESTRING',2);
> > INSERT INTO "line_test" ("ident",the_geom) VALUES
> > ('1','010500000001000000010200000005000000B3A577C1424D24410CC330EC2B9A554
> >18B948127A376244105BABC32B1965541F0ED178D18692441F4B57BE2759255418299B490E
> >2752441B8D8E0C2318D5541F3C322E53B9624412C5206BE56895541'); INSERT INTO
> > "line_test" ("ident",the_geom) VALUES
> > ('2','010500000001000000010200000004000000F3C322E53B9624412C5206BE5689554
> >1F2581D39AA7F2441381537CA2E7F554110044190F73E24411C4EC56D1B8555414F309396B
> >5EA2341AAB8512D82835541'); INSERT INTO "line_test" ("ident",the_geom)
> > VALUES
> > ('3','0105000000010000000102000000070000004F309396B5EA2341AAB8512D8283554
> >1A4938FCEA9DB234189B0CF8C0B7B5541A6699A26CD08244145D867D606755541FF0DA7627
> >63D2441F43CCF132A795541812EAFE4505F2441D242F4956D735541CF6CE9DDA77C244171A
> >31A83557355410E208F550FAF244178BA355F8A795541'); INSERT INTO "line_test"
> > ("ident",the_geom) VALUES
> > ('4','010500000001000000010200000003000000F2581D39AA7F2441381537CA2E7F554
> >1BB2798C9ACD4244165E0E9767D7D5541C42265606DD5244156CE010488765541'); END;
> >
> > ------------------------------------------------------------------------
> >
> > _______________________________________________
> > postgis-users mailing list
> > postgis-users at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-users
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users