2

I have millions of rows of geometry data. Some of them are close to each other (tens of meters apart), and some of them can be very far from each other. You can think of gas stations in real world where some gas stations are close to each other across the street, but some are not. The next closest one can be few hundreds meters or tens of kilometers apart.

I was curious if it is possible to write a query that can select one record per area. (either square area or in circle is fine)

For instance, a query that can do something like

"I want to select all gas stations in Germany but only interested in seeing at most one per 500m radius area. If there are multiple stations that are close to each other (fewer than 500m apart), only one of them must be selected."

=> In the result set of the query, I can safely assume that most of Germany's gas stations will be shown and none of them will be fewer than 500 meters apart.

One way that I thought of doing this is to calculate geohash for each geometry, and select one per certain geohash prefix. However, this approach is not very flexible because the query will be limited to geohash characters. I cannot supply arbitrary distance threshold in meters.

Would this be possible as PostGIS query? (e.g. using clustering approach perhaps?)

Edit 1

Below is an example incomplete query that I have tried using geohash. Results are sorted by geohash, so it is just matter of selecting one from each set with the same geohash value. However, I can only use area box determined by geohash prefix, and cannot provide custom radius (e.g. 5km, 2km, 1km, etc) value, which makes this query not so flexible.

select id, ST_GeoHash(way, 5), st_y(way) as lat, st_x(way) as lng 
from points order by st_geohash(way, 5) limit 1000;


id          geohash lat         lng
115319221   "4uusx" -41.5740949 -74.0718146
679361789   "4uusx" -41.5759059 -74.0728299
591844292   "4uusz" -41.5711773 -74.0703186
796302025   "4uutp" -41.5086211 -74.1087041
672159089   "4uuu8" -41.5721128 -74.0665036
687629681   "4uuub" -41.57108   -74.069856
591843790   "4uuub" -41.5696367 -74.064995
596950189   "4uuub" -41.5700602 -74.0660787
  • What have you tried? Editing the Question to include your code makes it easier to generate a solution that will work for you. – Vince Mar 2 at 3:19
  • How about using ST_Buffer on each gas station's geometry and then a ST_Intersects on each of these buffers with the gas stations and a LIMIT 1 to only return one gas station – JoeBe Mar 2 at 3:30
  • If you can construct the query to select ALL X, then add a LIMIT 1 to your query, with your rows optionally sorted if you don't want an apparently-random output. However, if you mean to construct a query where you seek to find an area where at most only one entity meets your condition, that's a different kind of problem. Your two sample queries are illustrating both of these problems. – alphabetasoup Mar 2 at 3:40
  • @Vince Thanks for feedback. I added a sample per suggestion. – user482594 Mar 2 at 4:49
  • @JoeBe, I did not think about that. That seems interesting. Though, if multiple gas stations's buffer zones are intersected, like a long chain in a line, the query may end up selling unnecessarily select only 1, while more than 1 could be selected. Still, I will think more about your approach. – user482594 Mar 2 at 4:51
3

A simple way to cluster with ST_SnapToGrid is to use DISTINCT ON:

SELECT id, way FROM (
SELECT DISTINCT ON (snap) 
  id, way,
  ST_SnapToGrid(way, 1) AS snap 
FROM points
) AS t;

The precision value in ST_SnapToGrid is chosen based on required point density. This picks an essentially random point as the representative point for the cell.

For a limited extent make this faster by adding a WHERE clause:

SELECT id, way FROM (
SELECT DISTINCT ON (snap) 
  id, way,
  ST_SnapToGrid(way, 1) AS snap 
FROM points
WHERE way && ST_MakeEnvelope(xmin, ymin, xmax, ymax, 4326);
) AS t;

Alternatively, to add a count of the number of points in each cell you can use an aggregation approach. (Note that the aggregated id value will only match the chosen point when the count = 1)

SELECT COUNT(1), MIN(id) AS name, 
  MIN(way)::geometry(point,4326) AS way,
  ST_X(snap) AS snapx, ST_Y(snap) AS snapy
FROM ( 
  SELECT id, way, ST_SnapToGrid(way, 1) AS snap
  FROM points
  --  WHERE way && ST_MakeEnvelope(-128.7275, 45.8855, -115.9615, 49.3854, 4326)
) AS t
GROUP BY snapx, snapy;
| improve this answer | |
  • These queries are concise & beautiful. Thank you. – user482594 Mar 4 at 11:45
2

You can use the function ST_SnapToGrid to gather the points in "cells", of the size that depends on the parameters you give. Then you just have to use a group by st_geohash(geom, 8) limit 1 (with geom the result of ST_SnapToGrid) to get the first by "cell" (the geohash size doesn't really matters, it is just to group more easily than using geometry, it just needs to be more precise than the snaptogrid). You could also add some randomness by adding a field random() and order your result by this field.

This would look like something like that:

WITH data_snapped AS 
(
    SELECT 
            id,
            random() as rng,
            ST_SnapToGrid(way::geometry, 10) as geom, -- Your precision here. Casted in geometry to have meters.
            ST_Y(way) as lat,
            ST_X(way) as lng 
        FROM 
            points
)
SELECT 
        DISTINCT ON (ST_geohash(geom)) 
        id,
        lat,
        lng
    FROM
        data_snapped
    ORDER BY
        ST_geohash(geom), rng;

I usually prefer to use geohash than geom to group or order, I think it's shorter (I'm not sure), but you should be able to use either.

| improve this answer | |
  • ST_SnapToGrid might work for me. 1. Why do you have to group by geohash? Can't you group by geom itself since it has already been snapped previously? 2. Once you use group by, it won't be possible to select one particular station's id, lat, lng, will it? – user482594 Mar 3 at 6:28
  • I edited my answer to respond your question and because effectively it did not worked. A distinct on, like @dr_jts is better. – robin loche Mar 3 at 10:22

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.