From 28b8cbebd58625cd253b75f19ccffabe75f5334a Mon Sep 17 00:00:00 2001 From: Sandro Santilli Date: Fri, 20 Feb 2015 17:27:56 +0000 Subject: [PATCH] Fix dimensionality confusion in &&& operator (#3045) Also enforce the concept that missing dimensions are infinite, thus always intersecting present dimensions. See http://lists.osgeo.org/pipermail/postgis-devel/2015-February/024759.html git-svn-id: http://svn.osgeo.org/postgis/trunk@13250 b70326c6-7e19-0410-871a-916f4a2858ee --- libpgcommon/gserialized_gist.c | 162 ++++++++++++++++++--------------- libpgcommon/gserialized_gist.h | 4 - postgis/gserialized_gist_nd.c | 22 +++-- regress/operators.sql | 29 +++++- regress/operators_expected | 2 + 5 files changed, 129 insertions(+), 90 deletions(-) diff --git a/libpgcommon/gserialized_gist.c b/libpgcommon/gserialized_gist.c index 3bfb1c0e1..71ccebece 100644 --- a/libpgcommon/gserialized_gist.c +++ b/libpgcommon/gserialized_gist.c @@ -17,10 +17,16 @@ #include "../postgis_config.h" +/*#define POSTGIS_DEBUG_LEVEL 4*/ + #include "liblwgeom.h" /* For standard geometry types. */ #include "lwgeom_pg.h" /* For debugging macros. */ #include "gserialized_gist.h" +#define FLAGS_NDIMS_GIDX(f) ( FLAGS_GET_GEODETIC(f) ? 3 : \ + FLAGS_GET_M(f) ? 4 : \ + FLAGS_GET_Z(f) ? 3 : 2 ) + /* Generate human readable form for GIDX. */ #if POSTGIS_DEBUG_LEVEL > 0 @@ -59,6 +65,73 @@ gserialized_datum_get_flags(Datum gsdatum) return gpart->flags; } +/* Convert a double-based GBOX into a float-based GIDX, + ensuring the float box is larger than the double box */ +static int gidx_from_gbox_p(GBOX box, GIDX *a) +{ + int ndims; + + ndims = FLAGS_NDIMS_GIDX(box.flags); + SET_VARSIZE(a, VARHDRSZ + ndims * 2 * sizeof(float)); + + GIDX_SET_MIN(a,0,next_float_down(box.xmin)); + GIDX_SET_MAX(a,0,next_float_up(box.xmax)); + GIDX_SET_MIN(a,1,next_float_down(box.ymin)); + GIDX_SET_MAX(a,1,next_float_up(box.ymax)); + + /* Geodetic indexes are always 3d, geocentric x/y/z */ + if ( FLAGS_GET_GEODETIC(box.flags) ) + { + GIDX_SET_MIN(a,2,next_float_down(box.zmin)); + GIDX_SET_MAX(a,2,next_float_up(box.zmax)); + } + else + { + /* Cartesian with Z implies Z is third dimension */ + if ( FLAGS_GET_Z(box.flags) ) + { + GIDX_SET_MIN(a,2,next_float_down(box.zmin)); + GIDX_SET_MAX(a,2,next_float_up(box.zmax)); + } + /* M is always fourth dimension, we pad if needed */ + if ( FLAGS_GET_M(box.flags) ) + { + if ( ! FLAGS_GET_Z(box.flags) ) + { + GIDX_SET_MIN(a,2,-1*FLT_MAX); + GIDX_SET_MAX(a,2,FLT_MAX); + } + GIDX_SET_MIN(a,3,next_float_down(box.mmin)); + GIDX_SET_MAX(a,3,next_float_up(box.mmax)); + } + } + + POSTGIS_DEBUGF(5, "converted %s to %s", gbox_to_string(&box), gidx_to_string(a)); + + return LW_SUCCESS; +} + +/* Convert a gidx to a gbox */ +static void gbox_from_gidx(GIDX *a, GBOX *gbox, int flags) +{ + gbox->xmin = (double)GIDX_GET_MIN(a,0); + gbox->xmax = (double)GIDX_GET_MAX(a,0); + + gbox->ymin = (double)GIDX_GET_MIN(a,1); + gbox->ymax = (double)GIDX_GET_MAX(a,1); + + if ( FLAGS_GET_Z(flags) ) { + gbox->zmin = (double)GIDX_GET_MIN(a,2); + gbox->zmax = (double)GIDX_GET_MAX(a,2); + } + + if ( FLAGS_GET_M(flags) ) { + gbox->mmin = (double)GIDX_GET_MIN(a,3); + gbox->mmax = (double)GIDX_GET_MAX(a,3); + } +} + + /** * Given a #GSERIALIZED datum, as quickly as possible (peaking into the top * of the memory) return the gbox extents. Does not deserialize the geometry, @@ -75,8 +148,8 @@ gserialized_datum_get_gbox_p(Datum gsdatum, GBOX *gbox) if( LW_FAILURE == gserialized_datum_get_gidx_p(gsdatum, gidx) ) return LW_FAILURE; - gbox_from_gidx(gidx, gbox); gbox->flags = gserialized_datum_get_flags(gsdatum); + gbox_from_gidx(gidx, gbox, gbox->flags); return LW_SUCCESS; } @@ -92,7 +165,7 @@ gserialized_datum_get_gbox_p(Datum gsdatum, GBOX *gbox) */ GSERIALIZED* gserialized_set_gidx(GSERIALIZED *g, GIDX *gidx) { - int g_ndims = (FLAGS_GET_GEODETIC(g->flags) ? 3 : FLAGS_NDIMS(g->flags)); + int g_ndims = FLAGS_NDIMS_BOX(g->flags); int box_ndims = GIDX_NDIMS(gidx); GSERIALIZED *g_out = NULL; size_t box_size = 2 * g_ndims * sizeof(float); @@ -140,7 +213,7 @@ GSERIALIZED* gserialized_set_gidx(GSERIALIZED *g, GIDX *gidx) */ GSERIALIZED* gserialized_drop_gidx(GSERIALIZED *g) { - int g_ndims = (FLAGS_GET_GEODETIC(g->flags) ? 3 : FLAGS_NDIMS(g->flags)); + int g_ndims = FLAGS_NDIMS_BOX(g->flags); size_t box_size = 2 * g_ndims * sizeof(float); size_t g_out_size = VARSIZE(g) - box_size; GSERIALIZED *g_out = palloc(g_out_size); @@ -168,76 +241,6 @@ GSERIALIZED* gserialized_drop_gidx(GSERIALIZED *g) return g_out; } - -/* Convert a double-based GBOX into a float-based GIDX, - ensuring the float box is larger than the double box */ -static int gidx_from_gbox_p(GBOX box, GIDX *a) -{ - int ndims; - - ndims = (FLAGS_GET_GEODETIC(box.flags) ? 3 : FLAGS_NDIMS(box.flags)); - SET_VARSIZE(a, VARHDRSZ + ndims * 2 * sizeof(float)); - - GIDX_SET_MIN(a,0,next_float_down(box.xmin)); - GIDX_SET_MAX(a,0,next_float_up(box.xmax)); - GIDX_SET_MIN(a,1,next_float_down(box.ymin)); - GIDX_SET_MAX(a,1,next_float_up(box.ymax)); - - /* Geodetic indexes are always 3d, geocentric x/y/z */ - if ( FLAGS_GET_GEODETIC(box.flags) ) - { - GIDX_SET_MIN(a,2,next_float_down(box.zmin)); - GIDX_SET_MAX(a,2,next_float_up(box.zmax)); - } - else - { - /* Cartesian with Z implies Z is third dimension */ - if ( FLAGS_GET_Z(box.flags) ) - { - GIDX_SET_MIN(a,2,next_float_down(box.zmin)); - GIDX_SET_MAX(a,2,next_float_up(box.zmax)); - if ( FLAGS_GET_M(box.flags) ) - { - GIDX_SET_MIN(a,3,next_float_down(box.mmin)); - GIDX_SET_MAX(a,3,next_float_up(box.mmax)); - } - } - /* Unless there's no Z, in which case M is third dimension */ - else if ( FLAGS_GET_M(box.flags) ) - { - GIDX_SET_MIN(a,2,next_float_down(box.mmin)); - GIDX_SET_MAX(a,2,next_float_up(box.mmax)); - } - } - - POSTGIS_DEBUGF(5, "converted %s to %s", gbox_to_string(&box), gidx_to_string(a)); - - return LW_SUCCESS; -} - - -GIDX* gidx_from_gbox(GBOX box) -{ - int ndims; - GIDX *a; - - ndims = (FLAGS_GET_GEODETIC(box.flags) ? 3 : FLAGS_NDIMS(box.flags)); - a = gidx_new(ndims); - gidx_from_gbox_p(box, a); - return a; -} - - -void gbox_from_gidx(GIDX *a, GBOX *gbox) -{ - gbox->xmin = (double)GIDX_GET_MIN(a,0); - gbox->ymin = (double)GIDX_GET_MIN(a,1); - gbox->zmin = (double)GIDX_GET_MIN(a,2); - gbox->xmax = (double)GIDX_GET_MAX(a,0); - gbox->ymax = (double)GIDX_GET_MAX(a,1); - gbox->zmax = (double)GIDX_GET_MAX(a,2); -} - /** * Peak into a #GSERIALIZED datum to find the bounding box. If the * box is there, copy it out and return it. If not, calculate the box from the @@ -265,9 +268,18 @@ gserialized_datum_get_gidx_p(Datum gsdatum, GIDX *gidx) if ( FLAGS_GET_BBOX(gpart->flags) ) { /* Yes! Copy it out into the GIDX! */ - const size_t size = gbox_serialized_size(gpart->flags); + size_t size = gbox_serialized_size(gpart->flags); POSTGIS_DEBUG(4, "copying box out of serialization"); memcpy(gidx->c, gpart->data, size); + /* if M is present but Z is not, pad Z and shift M */ + if ( FLAGS_GET_M(gpart->flags) && ! FLAGS_GET_Z(gpart->flags) ) + { + size += 2 * sizeof(float); + GIDX_SET_MIN(gidx,3,GIDX_GET_MIN(gidx,2)); + GIDX_SET_MAX(gidx,3,GIDX_GET_MAX(gidx,2)); + GIDX_SET_MIN(gidx,2,-1*FLT_MAX); + GIDX_SET_MAX(gidx,2,FLT_MAX); + } SET_VARSIZE(gidx, VARHDRSZ + size); result = LW_SUCCESS; } @@ -312,7 +324,7 @@ int gserialized_get_gidx_p(GSERIALIZED *g, GIDX *gidx) if ( FLAGS_GET_BBOX(g->flags) ) { - int ndims = FLAGS_NDIMS_BOX(g->flags); + int ndims = FLAGS_NDIMS_GIDX(g->flags); const size_t size = 2 * ndims * sizeof(float); POSTGIS_DEBUG(4, "copying box out of serialization"); memcpy(gidx->c, g->data, size); diff --git a/libpgcommon/gserialized_gist.h b/libpgcommon/gserialized_gist.h index c8e2215b7..bd26f4b43 100644 --- a/libpgcommon/gserialized_gist.h +++ b/libpgcommon/gserialized_gist.h @@ -51,10 +51,6 @@ typedef struct /* allocate a new gidx object on the heap */ GIDX* gidx_new(int ndims) ; -/* Convert a gidx to a gbox */ -void gbox_from_gidx(GIDX *gidx, GBOX *gbox); -/* Convert a gbox to a new gidx */ -GIDX* gidx_from_gbox(GBOX box); /* Increase the size of a GIDX */ void gidx_expand(GIDX *a, float d); diff --git a/postgis/gserialized_gist_nd.c b/postgis/gserialized_gist_nd.c index 641c94bf5..e264cf374 100644 --- a/postgis/gserialized_gist_nd.c +++ b/postgis/gserialized_gist_nd.c @@ -29,6 +29,8 @@ #include "../postgis_config.h" +/*#define POSTGIS_DEBUG_LEVEL 4*/ + #include "liblwgeom.h" /* For standard geometry types. */ #include "lwgeom_pg.h" /* For debugging macros. */ #include "gserialized_gist.h" /* For utility functions. */ @@ -301,7 +303,15 @@ static float gidx_inter_volume(GIDX *a, GIDX *b) /* ** Overlapping GIDX box test. ** -** Box(A) Overlap Box(B) IFF (pt(a)LL < pt(B)UR) && (pt(b)LL < pt(a)UR) +** Box(A) Overlaps Box(B) IFF for every dimension d: +** min(A,d) <= max(B,d) && max(A,d) => min(B,d) +** +** Any missing dimension is assumed by convention to +** overlap whatever finite range available on the +** other operand. See +** http://lists.osgeo.org/pipermail/postgis-devel/2015-February/024757.html +** +** Empty boxes never overlap. */ static bool gidx_overlaps(GIDX *a, GIDX *b) { @@ -319,7 +329,7 @@ static bool gidx_overlaps(GIDX *a, GIDX *b) ndims_b = GIDX_NDIMS(b); - /* compare within the dimensions of (b) */ + /* compare only up to dimensions of (b), missing dimensions always overlap */ for ( i = 0; i < ndims_b; i++ ) { if ( GIDX_GET_MIN(a,i) > GIDX_GET_MAX(b,i) ) @@ -328,14 +338,6 @@ static bool gidx_overlaps(GIDX *a, GIDX *b) return FALSE; } - /* compare to zero those dimensions in (a) absent in (b) */ - for ( i = ndims_b; i < GIDX_NDIMS(a); i++ ) - { - if ( GIDX_GET_MIN(a,i) > 0.0 ) - return FALSE; - if ( GIDX_GET_MAX(a,i) < 0.0 ) - return FALSE; - } return TRUE; } diff --git a/regress/operators.sql b/regress/operators.sql index eef3afe9a..121ffc776 100644 --- a/regress/operators.sql +++ b/regress/operators.sql @@ -113,4 +113,31 @@ select 'ndov6', 'LINESTRING(2 2 2 2, 4 4 4 4)'::geometry &&& 'POINT(2 4 2 4)'::geometry; -- t select 'ndov7', 'LINESTRING(2 2 2 2, 4 4 4 4)'::geometry &&& 'POINT(4 2 4 2)'::geometry; -- t --- TODO: mixed-dimension &&& overlap + +-- &&& with mixed dimensions + +WITH v(i,g) AS ( VALUES + (1,'POINT(0 0)'::geometry), -- true, infinite M range + (2,'POINTZ(0 0 1)'), -- true, infinite M range + (3,'POINTZ(0 0 0)'), -- true, infinite M range + (4,'POINTM(0 0 1)'), -- true, fully defined overlap + (5,'POINTZM(0 0 0 1)'), -- true, fully defined overlap + (6,'POINTZM(0 0 1 0)'), -- false, M out of range + (7,'LINESTRINGM(-1 0 2,1 0 3)'), -- false, M out of range + (8,'LINESTRINGZ(-1 0 2,1 0 3)') -- true, infinite M range + ) +SELECT 'ndovm1', array_agg(i) FROM v WHERE g &&& 'POINTM(0 0 1)'::geometry +ORDER BY 1; + +WITH v(i,g) AS ( VALUES + (1,'POINT(0 0)'::geometry), -- true, infinite Z range + (2,'POINTZ(0 0 1)'), -- true, fully defined overlap + (3,'POINTZ(0 0 0)'), -- false, Z out of range + (4,'POINTM(0 0 0)'), -- true, infinite Z range + (5,'POINTZM(0 0 0 1)'), -- false, Z out of range + (6,'POINTZM(0 0 1 0)'), -- true, fully defined overlap + (7,'LINESTRINGM(-1 0 2,1 0 3)'), -- true, infinite Z range + (8,'LINESTRINGZ(-1 0 2,1 0 3)') -- false, Z out of range + ) +SELECT 'ndovm2', array_agg(i) FROM v WHERE g &&& 'POINTZ(0 0 1)'::geometry +ORDER BY 1; diff --git a/regress/operators_expected b/regress/operators_expected index 4b318d247..f8b1dc8bf 100644 --- a/regress/operators_expected +++ b/regress/operators_expected @@ -55,3 +55,5 @@ ndov4|f ndov5|t ndov6|t ndov7|t +ndovm1|{1,2,3,4,5,8} +ndovm2|{1,2,4,6,7} -- 2.40.0