Changes between Initial Version and Version 1 of UsersWikiNearest


Ignore:
Timestamp:
Apr 14, 2009, 1:55:45 PM (14 years ago)
Author:
pierre
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • UsersWikiNearest

    v1 v1  
     1= Nearest Neighbor Search =
     2
     3
     4Describe [http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE188.HTM Nearest Neighbor Search] here.  These are helper functions for finding nearest neighbors to a given geometry.
     5
     6Examples of how to use these and more detailed description can be found here
     7http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor_generic
     8
     9
     10{{{
     11CREATE OR REPLACE FUNCTION expandoverlap_metric(a geometry, b geometry, maxe double precision, maxslice double precision)
     12  RETURNS integer AS
     13$BODY$
     14BEGIN
     15    FOR i IN 0..maxslice LOOP
     16        IF expand(a,maxe*i/maxslice) && b THEN
     17            RETURN i;
     18        END IF;
     19    END LOOP;
     20    RETURN 99999999;
     21END;
     22$BODY$
     23LANGUAGE 'plpgsql' IMMUTABLE;
     24
     25CREATE TYPE pgis_nn AS
     26   (nn_gid integer, nn_dist numeric(16,5));
     27
     28CREATE OR REPLACE FUNCTION _pgis_fn_nn(geom1 geometry, distguess double precision, numnn integer, maxslices integer, lookupset varchar(150), swhere varchar(5000), sgid2field varchar(100), sgeom2field varchar(100))
     29  RETURNS SETOF pgis_nn AS
     30$BODY$
     31DECLARE
     32    strsql text;
     33    rec pgis_nn;
     34    ncollected integer;
     35    it integer;
     36--NOTE: it: the iteration we are currently at
     37--start at the bounding box of the object (expand 0) and move up until it has collected more objects than we need or it = maxslices whichever event happens first
     38BEGIN
     39    ncollected := 0; it := 0;
     40    WHILE ncollected < numnn AND it <= maxslices LOOP
     41        strsql := 'SELECT currentit.' || sgid2field || ', distance(ref.geom, currentit.' || sgeom2field || ') as dist FROM ' || lookupset || '  as currentit, (SELECT geometry(''' || CAST(geom1 As text) || ''') As geom) As ref WHERE ' || swhere || ' AND distance(ref.geom, currentit.' || sgeom2field || ') <= ' || CAST(distguess As varchar(200)) || ' AND expand(ref.geom, ' || CAST(distguess*it/maxslices As varchar(100)) ||  ') && currentit.' || sgeom2field || ' AND expandoverlap_metric(ref.geom, currentit.' || sgeom2field || ', ' || CAST(distguess As varchar(200)) || ', ' || CAST(maxslices As varchar(200)) || ') = ' || CAST(it As varchar(100)) || ' ORDER BY distance(ref.geom, currentit.' || sgeom2field || ') LIMIT ' ||
     42        CAST((numnn - ncollected) As varchar(200));
     43        --RAISE NOTICE 'sql: %', strsql;
     44        FOR rec in EXECUTE (strsql) LOOP
     45            IF ncollected < numnn THEN
     46                ncollected := ncollected + 1;
     47                RETURN NEXT rec;
     48            ELSE
     49                EXIT;
     50            END IF;
     51        END LOOP;
     52        it := it + 1;
     53    END LOOP;
     54END
     55$BODY$
     56LANGUAGE 'plpgsql' STABLE;
     57
     58CREATE OR REPLACE FUNCTION pgis_fn_nn(geom1 geometry, distguess double precision, numnn integer, maxslices integer, lookupset varchar(150), swhere varchar(5000), sgid2field varchar(100), sgeom2field varchar(100))
     59  RETURNS SETOF pgis_nn AS
     60$BODY$
     61    SELECT * FROM _pgis_fn_nn($1,$2, $3, $4, $5, $6, $7, $8);
     62$BODY$
     63  LANGUAGE 'sql' STABLE;
     64
     65}}}
     66
     67== Notes ==
     68
     69Though fairly fast, this method is somewhat approximate, since it uses a bounding box to determine near features, so not all features in the box can be the same distance away. A more accurate, but slower method would be to ament the expandoverlap_metric function to use ST_DWithin() instead of expand(), so replacing
     70
     71       
     72{{{
     73IF expand(a,maxe*i/maxslice) && b THEN
     74
     75}}}
     76
     77with
     78       
     79{{{
     80IF ST_DWithin(a,b,maxe*i/maxslice) THEN
     81
     82}}}