3

Given a PostGIS table with a column of linestrings, which are expected to all be joined (they represent a network), how can I query the table to determine whether or not they are all joined (i.e. it should be possible to reach any linestring from any other, by traversing the network)?

I was thinking of creating some kind of aggregate geometry and comparing some measurement of that aggregate geometry (e.g. total "length") with the sum of all lengths, but haven't been able to get anywhere.

  • 1
    that might be no simple task...are they all supposed to be connected at their vertices only (instead of also in between, intersecting on the line) and if so, is there a pre-defined number of end points (linestrings with one unconnected end)? and how many lines are there? – ThingumaBob Oct 3 '17 at 20:28
  • 1
    also, would you be willing to dive into something like pg_routing? – ThingumaBob Oct 3 '17 at 20:40
  • Yes pg_routing would be an option. No predefined number of endpoints. – Ronnie Oct 3 '17 at 20:51
4

Assuming your dataset is small enough to fit in memory, you can cluster all of your geometries and then examine the number of clusters and the number of lines in each cluster.

If you want to use intersection as the basis of testing, you can use ST_ClusterIntersecting.

If you want to use use a distance tolerance instead, you can use ST_CusterWithin or ST_ClusterDBSCAN (which has a better interface).

Here's an example using ST_ClusterDBSCAN:

SELECT
  cluster_id,
  count(*) AS num_lines,
  array_agg(feature_id) AS features
FROM 
  (SELECT
    feature_id,
    ST_ClusterDBSCAN(geom, eps := 1e-8) OVER() AS cluster_id
  FROM lines) sq
ORDER BY num_lines DESC
OFFSET 1

In this case, we're linking our line geometries with a tolerance of 1e-8, and then assigning them to a cluster_id. If our network is entirely connected, then we'll only have one cluster ID. Assuming this is not the case, we count the number of features in each cluster, and then list out the feature IDs of every feature in each non-dominant cluster. For each non-dominant cluster, one linkage needs to be established to the dominant cluster in order to build a fully connected network.

One last thing: if you wanted to verify that your network was entirely connected by noded intersections (that is, lines that cross without a node would not be considered to intersect), you could do this by running your cluster function on ST_Points(geom) instead of geom.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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