# postgis: cluster/group points based on distance

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)

• ST_UNION is the function. Postgres/Postgis can do anything -- SQL with recursive queries is Turing complete :D 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. 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. Commented Feb 12, 2015 at 17:38
• Looks like a perfect fit for DBSCAN to me. 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"? Commented Aug 21, 2018 at 13:55

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.

• ST_ClusterWithin, great, still scheduled for Postgres 9.5/Postgis 2.2? Commented Feb 13, 2015 at 7:28

You now can use ST_ClusterDBSCAN:

``````SELECT *, ST_ClusterDBSCAN(geom, eps := 100, minpoints := 2) over () AS cid
FROM yourschema.yourtable
``````

This finishes in 7 s for 200 000 rows.