1

I have a task which looks pretty nontrivial yet pretty standard.

Let's say, I have a set of points, unevenly distributed on the map (i.e. in some regions there are a lot of points, while in the other regions points are sparse). The points can be sorted by some criterion K. I want to limit selection of point based on criterion K so that those points would be distributed relatively evenly. I.e. in the dense regions only really high on K points are shown, while in sparse regions whatever points there are are shown.

It seems to be a pretty standard task: e.g. showing cafes by their ranking or the most attractive tourists points of interest. So, I wonder, if there is a standard algorithm for this task (or maybe even a function in PostGIS) that I just not aware of?

Roman Bekkiev
  • 131
  • 1
  • 2
    In order to better help you and better understand your request, can you edit your post and illustrate the context and the expected result? – Vincent Bré Jan 03 '20 at 09:17
  • @VincentBré, as I said in question: e.g. in town all the cafes are in historical center. E.g. 90 on two streets. And another 30 cafes over the rest of the town. I want to show on map (when zoom over the whole town) only 10 top voted cafes in the center and all 30 over the rest of the town, so that cafes look "evenly distributed" over the town, when it reality in the center the worst cafes just filtered out. – Roman Bekkiev Jan 03 '20 at 09:34
  • one solution can be creating a grid of squares and then do join between the points and grid. Then, group the points based on grid id. Now, you know which points are in one grid together. Now, you can order the points by K and select the top N points – milad Jan 03 '20 at 14:13
  • I think you are looking for spatial clustering methods. Something like https://gis.stackexchange.com/questions/11567/spatial-clustering-with-postgis may be? I remember performing hierarchical clustering with postgis, using recursive with. I think that would fit your needs. Search the Internet for "spatial hierarchical clustering". Maybe later i can look for the code i've used that time. – Javier JC Jun 13 '20 at 05:20

2 Answers2

1

You can try to compute the kernel density of your points with this function: https://gist.github.com/AbelVM/dc86f01fbda7ba24b5091a7f9b48d2ee

And after you can use this density to mitigate the K, so you would need a higher K to be displayed in a region with a lot of points.

Be aware that if you do that, multiple points can be shown even if they are close with each other if they have a high K.

Another way to answer the general question of displaying only a few cafe on a map (for example) could be to define the maximum number N of cafe to be displayed, and use ST_ClusterKMeans. You will have your points (cafe) grouped in N groups, and you can select the highest K in each group to display only this one. The downpoint would be that if all your cafe are grouped in a same location, you will have all your N points displayed possibly close to each other. You can also try with ST_ClusterDBSCAN, but you're not garanteed to have a fixed amount of cluster so it's more difficult to parametrize, but it can resolve the problem if all the points are very close to each other.

Finally, you also can divide in a grid and display only one point by cell but it's less representative to me, you can still have very close points (in 2 different cells) and it would be weird to have a "grid" of cafe displayed.

robin loche
  • 2,465
  • 5
  • 9
1

This put me in mind of Poisson Disc Sampling (demo and resources here).

This can be emulated easily (but slowly) by creating an aggregate function which builds a list of points which are all further than a given distance from each other. When this is called on the dataset sorted by decreasing K value, this will produce a set of points with the desired property (I think).

Here's the code:

CREATE OR REPLACE FUNCTION sparse_pts_accum(pts geometry, pt geometry, r numeric)
RETURNS geometry AS
$$
        SELECT CASE WHEN ST_IsEmpty(pts) THEN pt
          WHEN ST_DWithin(pts, pt, r) THEN pts
          ELSE ST_Union(pts, pt)
          END;
$$ LANGUAGE 'sql' STRICT;

CREATE AGGREGATE sparse_pts (geometry, numeric)
(
    sfunc = sparse_pts_accum,
    stype = geometry,
    initcond = 'POINT EMPTY'
);

And here's an example of using it:

WITH data(geom, k) AS (VALUES
 ( 'POINT ( 1 1 )'::geometry, 1 )
,( 'POINT ( 2 2 )'::geometry, 9 )
,( 'POINT ( 3 3 )'::geometry, 1 )
,( 'POINT ( 3 3 )'::geometry, 2 )
,( 'POINT ( 4 4 )'::geometry, 9 )
)
SELECT ST_AsText( sparse_pts(geom, 2 ORDER By k DESC ) ) AS pts
FROM data;

-- output is MULTIPOINT(2 2,4 4)

Some notes:

  • To get the actual records in the output set, ST_Dump the MultiPoint and JOIN it back to the original data
  • This is pretty inefficient, so might only work on small datasets
  • It would be more efficient if it used a faster way of adding accepted points to the list than ST_Union. There is probably a better way of doing this, or if not there should be!
dr_jts
  • 5,038
  • 18
  • 15