4

We have a set of thousands of points and want to group all of those which are within 100m distance from each other (to get the centroid from each group). A first idea was to build 100m buffers around each point and to union/group all intersecting/overlapping polygons to one (but there can also be non-overlapping polygons within one cluster, see screenshot) - after that, we could simply calculate the centroid from the merged polygons. But I do not know how to do that in Postgis (in QGIS there is a simple tool called 'dissolve' that merges overlapping polygons, but we want to automatize the process)

enter image description here

  • 1
    ST_UNION is the function. Postgres/Postgis can do anything -- SQL with recursive queries is Turing complete :D – John Powell Feb 12 '15 at 13:57
  • Could you explain what you mean by non-overlapping polygons within each cluster? Are you able to pre-calculate a 100m buffer and use this as an indexed columm. It will be a lot quicker than buffering on the fly, as the index will no longer get used. – John Powell Feb 12 '15 at 17:33
  • Are you saying if polygon A is 75m from polygon B and polygon C is a further 75m away, that A and C will not end up in the same cluster? If so, you need not worry, they will all end up in one unioned polygon, as ST_Union works piecewise. – John Powell Feb 12 '15 at 17:38
  • 1
    Looks like a perfect fit for DBSCAN to me. – Anony-Mousse Jun 13 '15 at 22:31
  • You want to group points "which are within 100m distance from each other". But how you want to "group"? For example, 3 points: A, B, C. Distance from A to B < 100 m, from B to C < 100 m, but from A to C > 100 m. Which result do you want? Two groups {A, B}, {B, C} (A & B are not linked)? Or one group {A, B, C} (A & C are linked via B)? In terms of algebra, relation "to be within 100 m" is not transitive. It can't divide points onto groups. Maybe, you mean "Group is a chain of points" instead of "within 100 m from each other"? – Evgeny Nozdrev Aug 21 '18 at 13:55
6

You can group points using either the recursive query or PL/PLGSQL procedure described in the answers to this question. Just substitute ST_DWithin for ST_Intersects/ST_Touches, as appropriate.

If you're comfortable trying something experimental, you could build PostGIS with purpose-built functions to solve this problem: see the ticket on trac (code available on github)

Update January 2016: The "experimental" functions described above are no longer experimental; ST_ClusterWithin and ST_ClusterIntersecting are available in PostGIS 2.2. I highly recommend PostGIS 2.2.1, which includes a very important performance fix for these functions.

  • 1
    ST_ClusterWithin, great, still scheduled for Postgres 9.5/Postgis 2.2? – John Powell Feb 13 '15 at 7:28

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.