Postgis: aggregate function for intersection

Question

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 ) );

Answer 1

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;

Answer 2

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.