First I would like to mention that I am not an expert with PostGreSQL so my question may seem dumb, but here it goes:

I have a database with over 800 000 points associated to a geometry (EPSG 2950) and I would like to cluster those in convex hulls based on this:

"Group every point that has (at least) 3 other points at a distance of maximum 100 meters."

The resulting laye would show polygons delimiting points that respect that condition.

I am guessing I would use the ST_ConvexHull fonction for this particular request but I am struggeling to see how i add my constraints.

  • Not sure if this is possible as you have problems with the clusters (that you need to find first). There will be solutions where for example you group 4 points and your criteria only applies for one point in the middle. How are you going to group this as it will be correct for one point but false for the others. – Matte Jun 14 '16 at 19:17
  • @Matte I see your point. Even if the end result would be different, would it be easier to separate the constraint in 2, meaning: 1) Create a Cluster where every point within is at max 100m from another 2) Every cluster has to have a minimum of 4 points ? Even if the end result is different, this would still be acceptable. – Alex Girard Jun 14 '16 at 21:44

The clustering approach you're describing is referred to as DBSCAN*. (Yes, with an asterisk in the name). There's currently no functionality to do this in PostGIS, though an enhancement request could be made to add it, since it's only a small modification of the DBSCAN algorithm that's already implemented (unreleased).

Barring that, DBSCAN* implementations are available in R, for example through the "dbscan" package. You could export your data to R do this processing, or possibly wire something up with PL/R (see this answer for some ideas).

If you want to stay within PostGIS and don't exactly need DBSCAN*, you could try ST_ClusterWithin and doing some postprocessing on the results. That might look a bit like this:

  (SELECT ST_ConvexHull(unnest(ST_ClusterWithin(geom, 100))) AS geom FROM points) sq 
WHERE ST_NPoints(geom) >= 3
| improve this answer | |
  • Seems like I will be fine with the ST_ClusterWithin fonction! Thanks! – Alex Girard Jun 16 '16 at 14:35
  • After trying the said fonction it works fine. However I am thinking of using a ConcaveHull instead of a ConvexHull for more precise clusters. How would that translate? Is it possible to use the clusterwitin fonction but use ConcaveHull instead of ConvexHull? – Alex Girard Jun 16 '16 at 17:18
  • QGIS 3.4 offers a DBSCAN-tool which works fine. Anyway, +1 for pointing me in the right direction. – Erik Mar 14 '19 at 14:51

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.