Select kNN nearest point not already joined in table

Question

Think of this as a low-sophistication routing strategy.

Is there a way to select the nearest point from a table that has not already been processed through a kNN query?

What I have is this:

SELECT *
FROM sites s1
CROSS JOIN LATERAL (
    SELECT *
    FROM sites s2
    WHERE s1.id <> s2.id
    ORDER BY s1.geom <-> s2.geom
    LIMIT 1 ) AS s3;

... which correctly finds the nearest neighbor for each point, but what I'd like to do is to find the nearest neighbor that has not already been processed in the join. In other words:

point | Available for kNN
------+------------------
  A   | B C D
  B   | C D
  C   | D
  D   | (none)

Am I missing some basic SQL here?

(pgr_tsp(), from pgRouting, is too slow for the use case, and I don't need the globally shortest route.) I'm on PostgreSQL 14.1/PostGIS 3.2. The geom is 8191 (NAD83(HARN)/WISCRS Dane (m)).

user_18634266 · Answer

SELECT fst_id
     , array_agg(snd_id) arr_id
  FROM
     ( SELECT s1.id fst_id
            , s2.id snd_id
            , ROW_NUMBER() OVER ( PARTITION BY s1.id
                                      ORDER BY s1.geom <-> s2.geom
                                               asc
                                ) pos  
         FROM cites s1
         JOIN cites s2
           ON ST_DWITHIN(s1.geom,s2.geom, *MAX_SEARCH_DISTANCE*) -- max search distance in meters 
          and s1.id < s2.id
     ) sq
 WHERE pos <= *K* -- K-value (max numbers of nearest points)
 GROUP 
    BY fst_id

Notes

for geometry type must be SRS in meters (not 'default' EPSG:4326 and not popular 'Web Mercator').
for good performance, create a spatial index on geom column

Select kNN nearest point not already joined in table

1 Answers