4

I have a PostGIS Table with LINESTRINGS.

I look for a query that returns all Roads that are connected. So I get a set of unconnected trees (in german 'Wald (Graphentheorie)')

pseudo code:

select array_to_string(array_agg(id),', ') from roads
  group by ST_Intersection;

e.g.:

in table:

 id |           way
----+-------------------------
  1 | LINESTRING(1 3,2 4)
  2 | LINESTRING(1 3,1 0)
  3 | LINESTRING(11 13,12 14)
  4 | LINESTRING(2 4,0 1)
  5 | LINESTRING(11 13,11 10)
  6 | LINESTRING(6 12,8 7)

result:

  id 
-------
1, 2, 4
3, 5

For Testing in DB:

  SELECT DropGeometryTable ( 'roads' );
  CREATE TABLE roads (
    id integer
  ); 
  SELECT AddGeometryColumn('public','roads','way','900913','LINESTRING',2);
  INSERT INTO roads (id ,way) VALUES (1,GeometryFromText ( 'LINESTRING (1 3, 2 4)', 900913 ) );
  INSERT INTO roads (id ,way) VALUES (2,GeometryFromText ( 'LINESTRING (1 3,1 0)', 900913 ) );
  INSERT INTO roads (id ,way) VALUES (3,GeometryFromText ( 'LINESTRING (11 13,12 14)', 900913 ) );
  INSERT INTO roads (id ,way) VALUES (4,GeometryFromText ( 'LINESTRING (2 4,0 1)', 900913 ) );
  INSERT INTO roads (id ,way) VALUES (5,GeometryFromText ( 'LINESTRING (11 13,11 10)', 900913) );
  INSERT INTO roads (id ,way) VALUES (6,GeometryFromText ( 'LINESTRING (6 12,8 7)', 900913 ) );
2
  • Hi, I'm having difficulty understanding what your question is. Could you explain better what you expect to happen with your query and how your result differs from your expectation? Commented Mar 27, 2013 at 14:36
  • 1.: I want to get all independent roadnets. 2: ST_Intersection is syntactically wrong in a GROUP statement.
    – youseeus
    Commented Mar 28, 2013 at 10:28

2 Answers 2

8

Your example may not be the best since it only contains two groups so I added line(point(6 12) point(8 7)) which intersects with 5. This should be possible with a recursive CTE. This works on the test data:

WITH RECURSIVE 
inter_agg AS
(
 SELECT r.id,array[r.id]||array_agg(r2.id) as arr FROM
 roads AS r
 JOIN roads AS r2
   ON r.id<>r2.id
 WHERE ST_Intersects(r.way,r2.way)
 GROUP BY r.id

),
final AS
(
    SELECT i.id,arr as inter, array[i.id] as ex FROM inter_agg AS i
  UNION ALL
    SELECT f.id,f.inter&i.arr,ex||array[i.id] 
    FROM final AS f 
    JOIN inter_agg AS i 
      ON f.id<i.id AND f.inter@>ARRAY[i.id] AND (f.ex@>ARRAY[i.id]) IS FALSE
  )
 SELECT inter FROM final WHERE inter=ex;
2
  • @youseeus I hope it does. I looked up graph theory and it turns out I did a query to find clique and you wanted unconnected trees. If you want to find that other thing after all I'll see what I can do. Commented Mar 28, 2013 at 16:08
  • 2
    I would like to add that you have to run "CREATE EXTENSION intarray;" before using this code.
    – marcodena
    Commented Sep 5, 2015 at 10:15
4

I've slightly modified Jakub's code. Now it lists unconnected trees.

It is better to add one more line to see the difference in results:

INSERT INTO roads (id , way) VALUES (7,ST_GeomFromText ( 'LINESTRING (0 0, 2 0)', 900913 ) );

WITH RECURSIVE 
inter_agg AS
(
 SELECT r.id,array[r.id]||array_agg(r2.id) as arr FROM
 roads AS r
 JOIN roads AS r2
   ON r.id<>r2.id
 WHERE ST_Intersects(r.way,r2.way)
 GROUP BY r.id

),
final AS
(
    SELECT distinct i.id,arr as inter, array[i.id] as ex FROM inter_agg AS i
  UNION ALL
    SELECT f.id,uniq(sort(f.inter||i.arr)),uniq(sort(ex||array[i.id])) 
    FROM final AS f 
    JOIN inter_agg AS i 
      ON f.id<i.id AND f.inter@>ARRAY[i.id] AND (f.ex@>ARRAY[i.id]) IS FALSE
  )
 SELECT distinct inter FROM final WHERE inter=ex;

One should take into account, that this query tends to be extremly slow when input consists large trees.

My task was to find intersected polygons. I had about 60 polygons in experemental input (up to 13 connected polygons in each tree, 8 trees overall). Execution time was about 500ms. Addition of the one big polygon, which united 21 polygons, led to 8s execution time.

2
  • any suggestion on how to speed up this?
    – marcodena
    Commented Sep 5, 2015 at 11:01
  • As far as I understood at that moment, the problem was specific to the implementation of WITH RECURSIVE statement. So, to solve the speed issue I would consider writing a function in PL/pgSQL or any other supported language (C for the fastest code) which performs this search not as a query, but as a program. Commented Apr 15, 2016 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.