5

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

Improve this question
5
  • 2
    ST_UNION is the function. Postgres/Postgis can do anything -- SQL with recursive queries is Turing complete :D
    – John Powell
    Commented Feb 12, 2015 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
    Commented Feb 12, 2015 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
    Commented Feb 12, 2015 at 17:38
  • 1
    Looks like a perfect fit for DBSCAN to me.
    – Has QUIT--Anony-Mousse
    Commented Jun 13, 2015 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
    Commented Aug 21, 2018 at 13:55

1 Answer 1

Reset to default
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.

Improve this answer
1
  • 1
    ST_ClusterWithin, great, still scheduled for Postgres 9.5/Postgis 2.2?
    – John Powell
    Commented Feb 13, 2015 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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