[postgis-users] Help with pgdijkstra

[Marc Compte]

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','010500000001000000010200000005000000B3A577C1424D24410CC330EC2B9A55418B948127A376244105BABC32B1965541F0ED178D18692441F4B57BE2759255418299B490E2752441B8D8E0C2318D5541F3C322E53B9624412C5206BE56895541');
> INSERT INTO "line_test" ("ident",the_geom) VALUES ('2','010500000001000000010200000004000000F3C322E53B9624412C5206BE56895541F2581D39AA7F2441381537CA2E7F554110044190F73E24411C4EC56D1B8555414F309396B5EA2341AAB8512D82835541');
> INSERT INTO "line_test" ("ident",the_geom) VALUES ('3','0105000000010000000102000000070000004F309396B5EA2341AAB8512D82835541A4938FCEA9DB234189B0CF8C0B7B5541A6699A26CD08244145D867D606755541FF0DA762763D2441F43CCF132A795541812EAFE4505F2441D242F4956D735541CF6CE9DDA77C244171A31A83557355410E208F550FAF244178BA355F8A795541');
> INSERT INTO "line_test" ("ident",the_geom) VALUES ('4','010500000001000000010200000003000000F2581D39AA7F2441381537CA2E7F5541BB2798C9ACD4244165E0E9767D7D5541C42265606DD5244156CE010488765541');
> END;
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-users
>