[postgis-devel] KNN Centroid Example

Paragon Corporation lr at pcorp.us
Mon Sep 26 22:03:30 PDT 2011


This is really weird.  Have geometries always been able to autocast to
PostgreSQL boxes.  I was running this function on my 1.5
install and it worked but I was scratching my head why it wasn't giving me
squared answers and then I released I was testing on the wrong server and
the geometries were being cast to boxes.

WITH 
cte(geom,type) AS (VALUES ('POINT(1 2)'::geometry, 'pt1'),
            ('POINT(3 2)'::geometry, 'pt2'),
            ('LINESTRING(-1 20, 3 4, 6 8)'::geometry, 'line'),
            (ST_Buffer(ST_Point(-9,-10),1000), 'poly')
           )
SELECT a.geom <-> b.geom AS knn, 
ST_Distance(ST_Centroid(a.geom),
ST_Centroid(b.geom)) As cdist, sqrt(a.geom <-> b.geom),
 a.type As atype, b.type as btype
FROM cte AS a CROSS JOIN cte AS b
WHERE b.type != a.type;

Is this just something quirky about my 1.5 install?
1.5 install 
       knn        |       cdist       |       sqrt       | atype | btype
------------------+------------------+------------------+-------+-------
                2 |                2 |  1.4142135623731 | pt1   | pt2
 10.1118742080783 | 8.64260049075301 | 3.17991732723955 | pt1   | line
 15.6204993518133 | 15.6204993518134 | 3.95227774224096 | pt1   | poly
                2 |                2 |  1.4142135623731 | pt2   | pt1
 10.0124921972504 | 8.68548106900008 | 3.16425223350642 | pt2   | line
 16.9705627484771 | 16.9705627484772 | 4.11953428781424 | pt2   | poly
 10.1118742080783 | 8.64260049075301 | 3.17991732723955 | line  | pt1
 10.0124921972504 | 8.68548106900008 | 3.16425223350642 | line  | pt2
 24.8243831746128 | 23.2697050583419 | 4.98240736738906 | line  | poly
 15.6204993518133 | 15.6204993518134 | 3.95227774224096 | poly  | pt1
 16.9705627484771 | 16.9705627484772 | 4.11953428781424 | poly  | pt2
 24.8243831746128 | 23.2697050583419 | 4.98240736738906 | poly  | line


2.0 install

  knn   |      cdist       |       sqrt       | atype | btype
--------+------------------+------------------+-------+-------
      4 |                2 |                2 | pt1   | pt2
 102.25 | 8.64260049075301 | 10.1118742080783 | pt1   | line
    244 | 15.6204993518134 | 15.6204993518133 | pt1   | poly
      4 |                2 |                2 | pt2   | pt1
 100.25 | 8.68548106900008 | 10.0124921972504 | pt2   | line
    288 | 16.9705627484772 | 16.9705627484771 | pt2   | poly
 102.25 | 8.64260049075301 | 10.1118742080783 | line  | pt1
 100.25 | 8.68548106900008 | 10.0124921972504 | line  | pt2
 616.25 | 23.2697050583419 | 24.8243831746128 | line  | poly
    244 | 15.6204993518134 | 15.6204993518133 | poly  | pt1
    288 | 16.9705627484772 | 16.9705627484771 | poly  | pt2
 616.25 | 23.2697050583419 | 24.8243831746128 | poly  | line

 
I ask cause I think it may leave some people scratching their heads thinking
they have knn gist when they don't.

> -----Original Message-----
> From: postgis-devel-bounces at postgis.refractions.net 
> [mailto:postgis-devel-bounces at postgis.refractions.net] On 
> Behalf Of Paragon Corporation
> Sent: Tuesday, September 27, 2011 12:24 AM
> To: 'PostGIS Development Discussion'
> Subject: Re: [postgis-devel] KNN Centroid Example
> 
> No that's fine - just wanted to document it correctly. 
> 
> > -----Original Message-----
> > From: postgis-devel-bounces at postgis.refractions.net
> > [mailto:postgis-devel-bounces at postgis.refractions.net] On Behalf Of 
> > Paul Ramsey
> > Sent: Monday, September 26, 2011 11:57 PM
> > To: PostGIS Development Discussion
> > Cc: PostGIS Development Discussion
> > Subject: Re: [postgis-devel] KNN Centroid Example
> > 
> > I am using the square of the centroid distance, since it saves me a 
> > call into sqrt during the index traversals. If you think it 
> should be 
> > a simple distance that can be arranged, but to the extent that it's 
> > just a number being used for sorting, the square suffices fine.
> > 
> > P.
> > 
> > On 2011-09-26, at 7:51 PM, "Paragon Corporation" 
> <lr at pcorp.us> wrote:
> > 
> > > What algorithm does it use for non-points.  Thought you
> > went with centroid.
> > > IF so how come these don't match or is it centroid of the box?
> > > 
> > > 
> > > SELECT ST_Distance(line,pt) as dist, line <-> pt as knn_dist,
> > >    ST_Distance(ST_Centroid(line),pt) As dist_cent
> > >    FROM (SELECT 'SRID=3005;LINESTRING(1011102 450541, 1011103 
> > > 450641)'::geometry As line,
> > >         'SRID=3005;POINT(1011102 450541)'::geometry As pt) As foo;
> > > 
> > > 
> > > Gives me:
> > > 
> > > dist | knn_dist |    dist_cent
> > > ------+----------+------------------
> > >    0 |  2500.25 | 50.0024999375613
> > > 
> > > 
> > > 
> > >> -----Original Message-----
> > >> From: postgis-devel-bounces at postgis.refractions.net
> > >> [mailto:postgis-devel-bounces at postgis.refractions.net] On
> > Behalf Of
> > >> Paul Ramsey
> > >> Sent: Monday, September 26, 2011 6:59 PM
> > >> To: PostGIS Development Discussion
> > >> Subject: [postgis-devel] KNN Centroid Example
> > >> 
> > >> So, I did a few KNN queries on my wee voting areas table
> > (8000 polys).
> > >> 
> > >> First the correct answer:
> > >> 
> > >> select st_distance(geom, 'SRID=3005;POINT(1011102 450541)') as 
> > >> d,edabbr, vaabbr from va2005 order by d limit 10;
> > >> 
> > >>        d         | edabbr | vaabbr
> > >> ------------------+--------+--------
> > >>                0 | ALQ    | 128
> > >> 5541.57712511724 | ALQ    | 129A
> > >> 5579.67450712005 | ALQ    | 001
> > >>  6083.4207708641 | ALQ    | 131
> > >>  7691.2205404848 | ALQ    | 003
> > >> 7900.75451037313 | ALQ    | 122
> > >> 8694.20710669982 | ALQ    | 129B
> > >> 9564.24289057111 | ALQ    | 130
> > >>  12089.665931705 | ALQ    | 127
> > >> 18472.5531479404 | ALQ    | 002
> > >> (10 rows)
> > >> 
> > >> Then the KNN raw answer:
> > >> 
> > >> select st_distance(geom, 'SRID=3005;POINT(1011102 450541)') as 
> > >> d,edabbr, vaabbr from va2005 order by geom <->
> > >> 'SRID=3005;POINT(1011102 450541)' limit 10;
> > >> 
> > >>        d         | edabbr | vaabbr
> > >> ------------------+--------+--------
> > >>                0 | ALQ    | 128
> > >> 5579.67450712005 | ALQ    | 001
> > >> 5541.57712511724 | ALQ    | 129A
> > >> 8694.20710669982 | ALQ    | 129B
> > >> 9564.24289057111 | ALQ    | 130
> > >>  6083.4207708641 | ALQ    | 131
> > >>  12089.665931705 | ALQ    | 127
> > >>  24795.264503022 | ALQ    | 124
> > >> 24587.6584922302 | ALQ    | 123
> > >> 26764.2555463114 | ALQ    | 125
> > >> (10 rows)
> > >> 
> > >> Note the misordering in the actual distances and the different 
> > >> entries that actually show up in the top 10.
> > >> 
> > >> Finally the hybrid:
> > >> 
> > >> with index_query as (
> > >>  select st_distance(geom, 'SRID=3005;POINT(1011102 450541)') as 
> > >> d,edabbr, vaabbr  from va2005  order by geom <->
> > >> 'SRID=3005;POINT(1011102 450541)' limit
> > >> 100) select * from index_query order by d limit 10;
> > >> 
> > >>        d         | edabbr | vaabbr
> > >> ------------------+--------+--------
> > >>                0 | ALQ    | 128
> > >> 5541.57712511724 | ALQ    | 129A
> > >> 5579.67450712005 | ALQ    | 001
> > >>  6083.4207708641 | ALQ    | 131
> > >>  7691.2205404848 | ALQ    | 003
> > >> 7900.75451037313 | ALQ    | 122
> > >> 8694.20710669982 | ALQ    | 129B
> > >> 9564.24289057111 | ALQ    | 130
> > >>  12089.665931705 | ALQ    | 127
> > >> 18472.5531479404 | ALQ    | 002
> > >> (10 rows)
> > >> 
> > >> And again we have the right entries and the right ordering. 
> > >> The trouble is the magic number (100) in the subquery. 
> Still, it's 
> > >> fast and it uses the index, so, what the hey!
> > >> 
> > >> P.
> > >> _______________________________________________
> > >> postgis-devel mailing list
> > >> postgis-devel at postgis.refractions.net
> > >> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> > >> 
> > > 
> > > 
> > > _______________________________________________
> > > postgis-devel mailing list
> > > postgis-devel at postgis.refractions.net
> > > http://postgis.refractions.net/mailman/listinfo/postgis-devel
> > _______________________________________________
> > postgis-devel mailing list
> > postgis-devel at postgis.refractions.net
> > http://postgis.refractions.net/mailman/listinfo/postgis-devel
> > 
> 
> 
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> 





More information about the postgis-devel mailing list