1

I have a set of points in a table, each has a value between 1 and 100.

How could I reduce this to the point with the highest value within a radius distance X. So that no point is ever closer than X to another.

As an example. If the table contained 4 points

Point 1 - value 10 
Point 2 - value 15
Point 3 - value 20
Point 4 - value 5
Point 5 - value 3

If Point's 1 - 3 were within 100 metres of each other then Point 3 would be selected. If points 4 -5 were within 100 meters of each other but > 100 metres from the others then point 4 would be selected. The resultant data set would be:-

Point 3 - value 15
Point 4 - value 5
  • If I understand your question correctly, there would be multiple potential solutions, depending on where you start from and what the radius is. Perhaps you could outline the expected solution a bit more. – John Powell Jun 9 '16 at 12:27
  • Edited to add an example – CF-GISRAW Jun 9 '16 at 13:00
4

One possible solution is to use St_ClusterWithin. This creates geometry collections of all the geometries that are within a distince, d, of each other, and takes the form ST_ClusterWithin(geom, d).

  • Start by using ST_ClusterWithin. Wrap this function in unnest and ST_CollectionExtract which takes a GeometryCollection and a number, in this case 1, points, which will return you MultiPoints representing each cluster based on the distance d.

  • Then use ST_Dump in conjunction with row_number() over() which will return the original points, but now with an associated clusterid.

  • Use ST_Intersects to get the original values associated with each geometry by joining the original points with the dumped points from each cluster.

  • Finally, use Distinct on (clusterid), where id is the cluster id, in conjunction with order by val desc, which will get you the highest value for each cluster along with the associated geometry. Distinct on takes the first of any combination, in this case clusterid, and because you sort on val DESC, this will give you the highest value for each cluster. You need clusterid in the order by or else the query planner will complain (you have to have the same order as in the distinct on), but this has no effect, as the hightest value, the 2nd order term, is what will be used.

Assuming you table is called test,

WITH 
   clusters(geom) AS 
      (SELECT 
          ST_CollectionExtract(unnest(ST_ClusterWithin(geom, 100)),1) 
        FROM test), 
   cl1 (clusterid, geom) AS 
      (SELECT 
          row_number() over(), 
          (ST_Dump(geom)).geom 
        FROM clusters),
   parts(val, clusterid, geom) AS 
      (SELECT val, id, test.geom 
         FROM test, cl1 
        WHERE ST_Intersects(test.geom, cl1.geom))
   SELECT DISTINCT ON (clusterid) val, geom 
     FROM parts 
    ORDER BY clusterid, val DESC;

It is more than conceivable that there are more elegant/shorter solutions, but this works.

With test geometies and cluster distance of 100:

WITH 
 test (val, geom) AS 
    (values(1, ST_MakePoint(0,0)),
           (2, ST_MakePoint(1,1)),
           (3, ST_MakePoint(200,200)), 
           (4, ST_MakePoint(201,201)), 
           (5, ST_MakePoint(200,200))),
 clusters(geom) AS 
   (SELECT 
      ST_CollectionExtract(unnest(ST_ClusterWithin(geom, 100)),1) 
    FROM test), 
 cl1 (clusterid, geom) AS 
   (SELECT 
      row_number() over(), 
      (ST_Dump(geom)).geom FROM clusters),
parts(val, clusterid, geom) AS 
   (SELECT val, clusterid, test.geom 
     FROM test, cl1 
    WHERE ST_Intersects(test.geom, cl1.geom))
SELECT DISTINCT ON (clusterid) val, geom 
 FROM parts 
ORDER BY clusterid, val DESC;

which returns:

2 | POINT(1 1)

5 | POINT(200 200)

as you would expect.

  • A great solution that has introduced me to a new set of POSTGIS functions – CF-GISRAW Jun 9 '16 at 20:05
  • You are welcome. ST_ClusterWithin is a recent addition and very useful, but a bit fiddly, as you have to break up the results and rejoin on the original geometries in order to get attributes back in order to use group by type functionality, etc. As I said, it might be possible to do this slightly more efficiently and elegantly :D. The expert on this is @dbaston, who might have something to add. – John Powell Jun 9 '16 at 20:11
  • 2
    Nothing to add, @JohnBarça 's solution is as good as it gets. It should be better in 2.3: WITH clusters(val, clusterid, geom) AS (SELECT val, ST_ClusterDBSCAN(geom, minpoints := 1, eps := 100) OVER(), geom FROM test) SELECT DISTINCT ON (clusterid) val, geom FROM clusters ORDER BY clusterid, val DESC; – dbaston Jun 9 '16 at 20:49
  • @dbaston. Yes, the windowing of cluster functions is going to be a fantastically useful addition. – John Powell Jun 10 '16 at 11:03

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.