[postgis-devel] KNN and 9.5
Stephen Mather
stephen at smathermather.com
Wed Jan 6 02:30:15 PST 2016
:) Thanks Regina. You made my morning.
On Wed, Jan 6, 2016 at 12:11 AM, Paragon Corporation <lr at pcorp.us> wrote:
> Steve,
>
> Nevermind. I was able to recreate your error with my test data. I had to
> reduce the table set so my patience wasn't exhausted.
>
> I'll ticket this one and see if I can trigger the same error with the
> built-in geometry types so I can complain upstream. So final test data and
> test to trigger:
>
> CREATE OR REPLACE FUNCTION zz_2nn_angle(geometry) RETURNS float AS $$
>
> -- Here are my wonderful points to KNN search:
> WITH index_query AS (
>
> SELECT edge.geom AS geom
> FROM (SELECT * FROM knn_recheck_geom) AS edge
> -- This is my query point
> ORDER BY $1
> <->
> edge.geom LIMIT 2
> ),
> templine AS (
> SELECT ST_MakeLine(geom) AS geom FROM index_query
> ),
> angle1 AS (
> SELECT ST_Azimuth(ST_StartPoint(geom), $1) angle FROM templine
> ),
> angle2 AS (
> SELECT ST_Azimuth(ST_EndPoint(geom), $1) angle FROM templine
> )
> SELECT a1.angle - a2.angle FROM angle1 a1, angle2 a2
>
> $$ LANGUAGE SQL;
>
> CREATE OR REPLACE FUNCTION zz_1nn_d(geometry) RETURNS float AS $$
>
> -- Here are my wonderful points to KNN search:
> WITH index_query AS (
>
> SELECT edge.geom AS geom
> FROM (SELECT * FROM knn_recheck_geom WHERE gid = 881) AS edge
> -- This is my query point
> ORDER BY $1
> <->
> edge.geom LIMIT 1
> )
> SELECT ST_Distance($1,geom) FROM index_query
>
> $$ LANGUAGE SQL;
>
> CREATE TABLE knn_recheck_geom(gid serial primary key, geom geometry);
> INSERT INTO knn_recheck_geom(gid,geom)
> SELECT ROW_NUMBER() OVER(ORDER BY x,y) AS gid, ST_Point(x*0.777,y*0.887)
> As geom
> FROM generate_series(-100,1000, 9) AS x CROSS JOIN
> generate_series(-300,1000,9) As y;
>
> ---
> DROP TABLE IF EXISTS test_angle_subset CASCADE;
> CREATE TABLE test_angle_subset AS
> WITH returnline AS (
> SELECT gid, geom,
> zz_1nn_d(geom) AS distance,
> abs(degrees(zz_2nn_angle(geom))) AS angle FROM
> (SELECT * FROM knn_recheck_geom) subset
> )
> SELECT * FROM returnline;
>
> Yields error:
>
> ERROR: index returned tuples in wrong order
> CONTEXT: SQL function "zz_2nn_angle" statement 1
> ********** Error **********
>
>
> Though I can't trigger the error with the 1nn function
>
> e.g this works fine:
>
> SELECT zz_1nn_d(geom)
> FROM knn_recheck_geom;
>
> Retuns 17835 rows in 300 ms.
>
> But this:
>
>
> SELECT zz_2nn_angle(geom)
> FROM knn_recheck_geom;
>
>
> --- triggers same error
> ERROR: index returned tuples in wrong order
> CONTEXT: SQL function "zz_2nn_angle" statement 1
>
> You are a cruel bastard Steve. You make me proud,
>
> Regina
>
>
>
>
>
>
> -----Original Message-----
> From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On
> Behalf Of Paragon Corporation
> Sent: Tuesday, January 05, 2016 11:56 PM
> To: 'PostGIS Development Discussion' <postgis-devel at lists.osgeo.org>
> Subject: Re: [postgis-devel] KNN and 9.5
>
> Steve,
>
> I tested with my junk dataset and I can't trigger the issue.
>
> Are you able to with this?
>
> CREATE TABLE knn_recheck_geom(gid serial primary key, geom geometry);
> INSERT INTO knn_recheck_geom(gid,geom) SELECT ROW_NUMBER() OVER(ORDER BY
> x,y) AS gid, ST_Point(x*0.777,y*0.887) As geom FROM
> generate_series(-100,1000, 1) AS x CROSS JOIN generate_series(-300,1000,1)
> As y;
>
> CREATE INDEX idx_knn_recheck_geom on knn_recheck_geom using gist(geom);
>
>
> CREATE OR REPLACE FUNCTION zz_2nn_angle(geometry) RETURNS float AS $$
>
> -- Here are my wonderful points to KNN search:
> WITH index_query AS (
>
> SELECT edge.geom AS geom
> FROM (SELECT * FROM knn_recheck_geom) AS edge
> -- This is my query point
> ORDER BY $1
> <->
> edge.geom LIMIT 2
> ),
> templine AS (
> SELECT ST_MakeLine(geom) AS geom FROM index_query ),
> angle1 AS (
> SELECT ST_Azimuth(ST_StartPoint(geom), $1) angle FROM templine ),
> angle2 AS (
> SELECT ST_Azimuth(ST_EndPoint(geom), $1) angle FROM templine
> )
> SELECT a1.angle - a2.angle FROM angle1 a1, angle2 a2
>
> $$ LANGUAGE SQL;
>
> vacuum analyze knn_recheck_geom;
>
> Then I ran with this query:
>
> SELECT zz_2nn_angle(ST_Point(10,2)); --returns 2.56969144546978 in 11ms
>
> This is testing on PostGIS 2.2.1, PostgreSQL 9.5.0rc1 under windows 7
> 64-bit
>
> I'm gonna try next on a real dataset. Maybe I don't have enough test data
> or distribution is too predictable.
>
> Does the above test crash for you?
>
>
> Thanks,
> Regina
>
>
>
>
>
>
> From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On
> Behalf Of Stephen Mather
> Sent: Tuesday, January 05, 2016 10:31 PM
> To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
> Subject: Re: [postgis-devel] KNN and 9.5
>
> Hi Regina,
>
> The dataset is from Natural Earth:
> http://www.naturalearthdata.com/http//www.naturalearthdata.com/download/10m/physical/ne_10m_geography_regions_polys.zip
>
> I imported that dataset and transformed to 3857 just to get it in planar
> coordinates. I affectionately called it regions_polys_subset.
>
> https://gist.github.com/smathermather/320273309124bf8b80a7
>
> But honestly, as long as you throw the knn in a function, any point
> dataset will do it, I think.
>
> Hope this helps (and helps in time!)!
> Cheers,
> Best,
> Steve
>
>
>
>
>
>
>
> On Sun, Jan 3, 2016 at 9:24 PM, Paragon Corporation <lr at pcorp.us> wrote:
> Steve,
>
> Well that sucks. Can I borrow your dataset to test with?
>
> Thanks,
> Regina
>
> From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On
> Behalf Of Stephen Mather
> Sent: Sunday, January 03, 2016 10:41 AM
> To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
> Subject: Re: [postgis-devel] KNN and 9.5
>
> Hi Regina,
>
> On a lark, I also tested with 2.3.0dev r14538 (9.5rc1)
>
> "POSTGIS="2.3.0dev r14538" GEOS="3.5.0-CAPI-1.9.0 r4084" SFCGAL="1.2.2"
> PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.1, released 2013/08/26"
> LIBXML="2.9.1" LIBJSON="0.11.99" RASTER"
>
> Same result.
>
> Cheers,
> Best,
> Steve
>
>
>
>
> On Sun, Jan 3, 2016 at 9:34 AM, Stephen Mather <stephen at smathermather.com>
> wrote:
> 2.2.0 and RC1. Should I be trying 2.2 branch?
>
>
> SELECT version();
>
> "PostgreSQL 9.5rc1 on x86_64-pc-linux-gnu, compiled by gcc (Debian
> 4.7.2-5) 4.7.2, 64-bit"
>
>
> SELECT postgis_full_version();
>
> "POSTGIS="2.2.0 r14208" GEOS="3.5.0-CAPI-1.9.0 r4084" SFCGAL="1.2.2"
> PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.1, released 2013/08/26"
> LIBXML="2.9.1" LIBJSON="0.11.99" RASTER"
>
>
>
> On Sun, Jan 3, 2016 at 2:18 AM, Paragon Corporation <lr at pcorp.us> wrote:
> Steve,
>
> Haven't had a chance to look thru what you have here and test it out
> myself.
>
> The issue I flagged in the ticket was fixed in PostgreSQL 9.5 code base
> upstream:
>
> http://www.postgresql.org/message-id/55630D9D.3090508@iki.fi
>
> It's my understanding that you should never get that notice again. So I'm
> a bit concerned you are. It's possible you found another area where this
> issue arises and is not handled.
>
> Are you running PostgreSQL 9.5RC1 and latest PostGIS 2.2 branch (or
> 2.2.0?).
>
> Thanks,
> Regina
>
> From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On
> Behalf Of Stephen Mather
> Sent: Sunday, January 03, 2016 1:56 AM
> To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
> Subject: [postgis-devel] KNN and 9.5
>
> Hi All,
>
> Short version:
> Does Regina's comment on http://trac.osgeo.org/postgis/ticket/2703
> regarding ERROR: index returned tuples in wrong order apply to any uses of
> indices in conjunction with KNN?
>
> Long version:
> Digging many of the 2.2 / 9.5 updates. Having fun on break playing with
> skeleton simplification and using KNN in the process. Yes. For those of you
> who know me, this is an obsession that won't die quietly.
>
>
> https://smathermather.files.wordpress.com/2016/01/screen-shot-2016-01-03-at-1-19-26-am.png
>
> I've got a function that does my KNN in the usual style, finds the nearest
> 2 points, and makes a line from them:
>
> CREATE OR REPLACE FUNCTION zz_knn_wonderful_points (geometry) RETURNS
> geometry AS $$
>
> -- Here are my wonderful points to KNN search:
> WITH index_query AS (
>
> SELECT edge.geom AS geom
> FROM (SELECT * FROM regions_dpoints WHERE gid = 882) AS edge
> -- This is my query point
> ORDER BY $1
> <->
> edge.geom LIMIT 2
> )
> SELECT ST_MakeLine(geom) FROM index_query
>
> $$ LANGUAGE SQL;
>
> The intent is to implement angle values as an importance criterion for
> simplifying the skeleton as described at minute 2:20 in Balint Miklos video
> on the scale axis transform:
> http://balintmiklos.com/scale-axis/The_Scale_Axis_Picture_Show.mp4
>
> Actually, in the final function, I will likely directly calculate the
> angle and return that instead of the geometry, but I digress.
>
> Regardless, when I use this function as is, it works great in drawing
> lines connecting the two nearest points to the vertex in the medial axis:
>
> DROP TABLE IF EXISTS test CASCADE;
> CREATE TABLE test AS
> WITH returnline AS (
> SELECT oid, gid,
> ST_Union(
> ST_MakeLine(
> ST_StartPoint(zz_knn_wonderful_points(subset.geom)), subset.geom),
> ST_MakeLine(
> ST_EndPoint(zz_knn_wonderful_points(subset.geom)), subset.geom)
> )
> AS geom FROM
> (SELECT * FROM regions_points WHERE oid = 882)
> subset
> )
> SELECT * FROM returnline
> ;
>
> However, as implemented, this will not work in the case of overlapping
> geometries, such as Natural Earth's label polygon dataset
> "ne_10m_geography_regions_polys":
>
>
> https://smathermather.files.wordpress.com/2016/01/screen-shot-2016-01-03-at-1-33-01-am.png
>
> And so I add a constraint using an integer ID:
>
> CREATE OR REPLACE FUNCTION zz_knn(integer,geometry) RETURNS geometry AS $$
>
> -- Here are my wonderful points to KNN search:
> WITH index_query AS (
>
> SELECT edge.geom AS geom
> FROM (SELECT * FROM regions_dpoints WHERE gid = $1) AS edge
> -- This is my query point
> ORDER BY $2
> <->
> edge.geom LIMIT 2
> )
> SELECT ST_MakeLine(geom) FROM index_query
>
> $$ LANGUAGE SQL;
>
> And now it takes much longer and fails with
>
> "
> ERROR: index returned tuples in wrong order
> CONTEXT: SQL function "zz_knn" statement 1
> ********** Error **********
>
> ERROR: index returned tuples in wrong order SQL state: XX000
> Context: SQL function "zz_knn" statement 1 "
>
> Thanks!
> Cheers,
> Best,
> Steve Mather
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/postgis-devel
>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/postgis-devel
>
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/postgis-devel
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/postgis-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20160106/f14f9d08/attachment.html>
More information about the postgis-devel
mailing list