# Postgis: aggregate function for intersection

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:

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:

id integer
);
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 ) );
• 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? Mar 27, 2013 at 14:36
• 1.: I want to get all independent roadnets. 2: ST_Intersection is syntactically wrong in a GROUP statement. Mar 28, 2013 at 10:28

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
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;
• @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. Mar 28, 2013 at 16:08
• I would like to add that you have to run "CREATE EXTENSION intarray;" before using this code. Sep 5, 2015 at 10:15

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
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.

• any suggestion on how to speed up this? 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. Apr 15, 2016 at 13:14