[postgis-users] Group intersecting lines

Stephen Woodbridge woodbri at swoodbridge.com
Sun Jul 13 18:54:56 PDT 2008


Shane Butler wrote:
> Dear all,
> 
> Can anyone offer some advice on how to group lines together that
> intersect?  What I would like to achieve is a grouping where all
> connected lines are added to the one group and a disconnected set of
> connecting lines would be added to another group (and so on).  Can I
> do this using a GROUP BY clause?

If you are trying to identify say all roads the are networked on an 
island as one group and all lines that are networked on the mainland as 
a separate group? Then no you can not. I believe you will need to look 
at some algorithms in "graph theory" to do that.

You can use DFS (Depth First Search) to generate graphs of your nodes 
and from that identify the separate "forests" in your data.

I would recommend getting this book:

http://www.google.com/search?hl=en&q=%22graph+algorithms%22+sedgewick&btnG=Google+Search


-Steve



More information about the postgis-users mailing list