1

I have created a topology from OSM data and would like to simulate a car driving every possible route along the map. The purpose is to "survey" the osm data as if in a car. My ultimate objective is to find every unique journey segment of five miles, I am aware that there will be a LOT of them.

I am using pgrouting/postgis and have created a topology from roads. I've also written an algorithm that given any osm_id will find all connected osm_id's to a depth of N. This works by finding all connected osm_ids and then recursing through these until the depth is reached.

I could modify this to change N to a distance of five miles.

But is there a better way of traversing every possible path in a network?

For information, here is my current algorithm which is sub-optimal as it does not deal well with junctions that have more than one connection

** Find connections **

CREATE OR REPLACE FUNCTION ng_research.get_connections(id bigint, table_param character varying)
RETURNS bigint[] AS
$BODY$
DECLARE
  ret_vals integer [];
BEGIN
--quite simply given a source node for a line string returns all of the connected nodes including its own target

WITH CTE AS (
 SELECT source from ng_research.all_roads WHERE osm_id=id
) 

SELECT array_agg(osm_id)  into ret_vals FROM ng_research.all_roads AR,CTE  WHERE  AR.target=CTE.source or AR.source=CTE.source;
RETURN ret_vals;
END;
$BODY$
 LANGUAGE plpgsql VOLATILE

** Build linestring arrays **

CREATE OR REPLACE FUNCTION ng_research.road_string_finder(node bigint, table_param character varying, depth integer default 0, max_depth integer default 2, previous_nodes bigint[] DEFAULT NULL::integer[]) RETURNS bigint[] AS
$BODY$
DECLARE
 connected_nodes bigint[];
 node_var integer;
BEGIN


IF depth = 0 THEN
 DROP TABLE IF EXISTS ng_research.nodes_visited;
 CREATE TABLE ng_research.nodes_visited (id bigint);
END IF;

previous_nodes := array_append(previous_nodes, node);

SELECT ng_research.get_connections(node, table_param) INTO connected_nodes;

IF connected_nodes IS NOT NULL THEN
 FOREACH node_var IN ARRAY connected_nodes LOOP

  IF NOT (node_var = ANY(previous_nodes)) THEN 
   RAISE NOTICE '% :  %', node_var, previous_nodes;
   IF depth < max_depth THEN

    IF (SELECT node_var from ng_research.nodes_visited WHERE id=node) IS NULL THEN
    SELECT ng_research.road_string_finder(node_var, table_param, depth + 1, max_depth, previous_nodes) INTO previous_nodes;
    INSERT  INTO ng_research.nodes_visited (id) VALUES (node_var);
   END IF;
  END IF;
 ELSE
 RAISE NOTICE 'SEEN YOU';
END IF;
END LOOP;

END IF;

IF array_length(previous_nodes,1) > 1 THEN

 previous_nodes := array_remove(previous_nodes, node);
 END IF;
 return previous_nodes;
 END;
$BODY$
LANGUAGE PLPGSQL;

** find connections for a single linestring **

SELECT ng_research.road_string_finder(204359430, 'ng_research.all_roads',0,5);
  • It can help to refine your definition of "path" beforehand. For instance, would it count to have a car just zig-zag back and forth along one segment until its odometer reads five miles? If so, you have an impossible task, but if not, you need to stipulate what constitutes a valid "path" or what would make two of them essentially the same for your purposes. – whuber Feb 6 '14 at 23:02
  • Once you have reached your "ultimate objective" what is next step? I'm asking since these "find all possible routes" keep coming up and they never seem to have any real-life relevance and they are not defined very well. – Uffe Kousgaard Feb 7 '14 at 8:01
  • The objective is simple. Find all hills in a given area. This is done by looking at the linestrings and mapping them to height data, but a hill can traverse multiple linestrings (ie. junctions) hence the need for coverage of all routes. This hopefully answers the path question as well. – user1331131 Feb 7 '14 at 9:15
  • Do you have height data at junctions only or also for each node along the linestrings (segments)? In other words, how detailed should the result be? – Uffe Kousgaard Feb 7 '14 at 9:51
  • I have height data from any point on any linestring (derived from the free NASA datasets) – user1331131 Feb 7 '14 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.