Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a PostGIS Table with LINESTRINGS.

I like to 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 ) );
share|improve this question
    
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? –  Jay Guarneri Mar 27 '13 at 14:36
    
1.: I want to get all independent roadnets. 2: ST_Intersection is syntactically wrong in a GROUP statement. –  youseeus Mar 28 '13 at 10:28

2 Answers 2

up vote 5 down vote accepted

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;
share|improve this answer
    
Wow it works... –  youseeus Mar 28 '13 at 10:53
    
@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. –  Jakub Kania Mar 28 '13 at 16:08

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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