[GIS] nearest neighbor within table using PostGIS

postgis-2.0

using PostGIS 2.0 and PostgreSQL 9.1 I have a table of photographic observations, sco_photos. The location column contains a PostGIS geometry point specifying where the observation was made. The table is not enormous (about 7,000 rows).

I am trying to write a query that will return, for each observation, the nearest other observation in the same table, along with the distance between the two observations. I can easily do this for a fixed point, e.g., how far is each observation from some central point, but the trick is locating the nearest other point in the table and measuring the distance to it.

This is the closest I've come thus far:

SELECT a.photo_id, b.photo_id, st_distance(a.location, b.location) 
FROM sco_photos a, sco_photos b 
WHERE st_distance(a.location, b.location) =
      (select min(st_distance(a.location, c.location)) 
       from sco_photos c where c.photo_id <> a.photo_id);

…but this seems just to hang. Performance for this application is not terribly important, as I need this for analysis not for real-time querying.

Thanks for any advice.

Best Answer

There are various methods for determining nearest neighbor - I provide several examples in this blogpost (pre-2.0, however).

Here is an example using a postgres window function to rank the distances between points. Grab the highest - and thus closest - rank and recalculate the distance. If you have a general sense of how clustered your points are, you can throw a ST_DWithin() in your query to limit the initial distance calculations.

  SELECT
     i.gid
    ,i.b_gid
    ,ST_Distance(i.geom, i.b_geom) AS dist
FROM(
SELECT
     a.gid
    ,b.gid AS b_gid
    ,a.geom
    ,b.geom AS b_geom
    ,rank() OVER (PARTITION BY a.gid ORDER BY ST_Distance(a.centroid_geom, b.the_geom)) AS pos
FROM points a, points b 
WHERE a.gid <> b.gid) i
WHERE pos = 1
Related Question