others (#15) - traveling a certain distance along a network (#382) - Message List

traveling a certain distance along a network

hello, i am trying to start at a node and travel every possible path along a network for a certain distance. does anyone know of anything out there that does this using pgrouting? if not, what do you suppose the best approach would be to start creating something that does that, (dijkstra, A*...)? I am using qgis and python scripting to do some other goeprocessing and viewing data and wanted to ask here before i started so i might not have to reinvent the wheel. thanks!

iant1212
09/21/10 01:30:00 (2 months ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #1621

    I think the function that suits best is the "Driving Distance" function. It travels along a network along every possible path and collects the nodes that have been passed.
    This is probably what you're looking for. But the function goes one step further and calculates and returns a polygon containing the area that can be reached for a certain distance.

    This polygon calculation is kind of a headache already since it exists, because it introduced a not very convenient dependency to CGAL.
    I think it would be also interesting to have a function that only returns the points. If you have a time and skills to look into this and modify the source code and send us a patch, we might add this functionality to pgRouting.

    Unfortunately we have no time at the moment to implement this from our side without a sponsor, but it shouldn't be too difficult, if you like to try. If you have questions, feel free to ask (Also asking on the mailing list is a good idea. Maybe someone did this already, but doesn't check the forum.)

    daniel
    09/21/10 06:06:41 (2 months ago)
    • Message #1623

      thanks,

      i looked into the driving_distance function and it looks great but i do have one question about it. the documentation says that it is supposed to return edge_id for each edge crossed, but i'm not getting that to happen.

      i used this sql: 

      DROP TABLE path1;
CREATE OR REPLACE VIEW view1 AS
SELECT * FROM driving_distance('SELECT gid AS id,source,target,
         length::double precision AS cost
         FROM lancroadsfeet', 684, 290, false, false);
SELECT gid, the_geom, source, target INTO path1
FROM lancroadsfeet lr, view1
WHERE lr.gid = view1.edge_id;


      there are 5 rows of results but the edge_id is duplicated twice..

      vertex_id-----edge_id---------cost

      87----------137------286.245514070368
      90----------228------55.2102527332564

      92----------228 ------288.291891327063

      611---------151------52.0779428964578

      684---------151-------0

      so when i render the table path1 i get

      [ http://www.imageurlhost.com/images/u8e426jxvbfx5vln1j.png]

      black text = length in feet (my cost value)

      pink text = node id

      call out text = edge_id

      green lines = render of table named path1 created from sql


      does driving distance return only nodes or am i missing something? i am expecting to get edge_ids 1720, 151, 1319, 288

      iant1212
      09/22/10 02:46:58 (2 months ago)
      • Message #1624

        Yes, it returns only nodes and a cost of going from start point to the node. Edge ids are completely arbitrary, this column is kept for the type compatibility (confusing, I know).

        Anton.

        anton
        09/22/10 07:45:51 (2 months ago)
        • Message #1627

          Hey Anton, why if the edge column is arbitrary not leave the edge column completely empty?

          daniel
          09/22/10 18:41:18 (2 months ago)
        • Message #1628

          thanks very much for the clarification.

          to get the edges i want i'm going to write some sql that will pair all the combinations of nodes that driving_distance returns.

          so if driving_distance returns nodes 1,2,3,4 i'll end up with:
          1-2, 1-3, 1-4, 2-1 ... 4-2, 4-3

          then i'll look for those combinations in the source and target fields of my network table and return the_geom for those records that match.

          iant1212
          09/22/10 23:26:27 (2 months ago)
Tree View Flat View (newer first) Flat View (older first)