From 8606a3164111e75754ce59c095a05e193cdae636 Mon Sep 17 00:00:00 2001 From: Paul Ramsey Date: Tue, 12 Sep 2017 19:44:32 +0000 Subject: [PATCH] #3844, new btree behavior for = and < > git-svn-id: http://svn.osgeo.org/postgis/trunk@15700 b70326c6-7e19-0410-871a-916f4a2858ee --- liblwgeom/g_serialized.c | 190 +++++++++++++ liblwgeom/liblwgeom.h.in | 22 ++ postgis/geography_btree.c | 120 +------- postgis/lwgeom_btree.c | 360 +++--------------------- regress/concave_hull.sql | 8 +- regress/operators.sql | 39 +-- regress/operators_expected | 8 +- topology/test/regress/topojson_expected | 26 +- 8 files changed, 298 insertions(+), 475 deletions(-) diff --git a/liblwgeom/g_serialized.c b/liblwgeom/g_serialized.c index 4c7677a31..84d16b78c 100644 --- a/liblwgeom/g_serialized.c +++ b/liblwgeom/g_serialized.c @@ -25,6 +25,7 @@ #include "liblwgeom_internal.h" #include "lwgeom_log.h" +#include "lwgeodetic.h" /*********************************************************************** * GSERIALIZED metadata utility functions. @@ -66,6 +67,16 @@ uint32_t gserialized_max_header_size(void) return sizeof(GSERIALIZED) + 8 * sizeof(float) + sizeof(int); } +uint32_t gserialized_header_size(const GSERIALIZED *gser) +{ + uint32_t sz = 8; /* varsize (4) + srid(3) + flags (1) */ + + if (gserialized_has_bbox(gser)) + sz += gbox_serialized_size(gser->flags); + + return sz; +} + uint32_t gserialized_get_type(const GSERIALIZED *s) { uint32_t *ptr; @@ -169,6 +180,185 @@ char* gserialized_to_string(const GSERIALIZED *g) return lwgeom_to_wkt(lwgeom_from_gserialized(g), WKT_ISO, 12, 0); } +/* Unfortunately including advanced instructions is something that +only helps a small sliver of users who can build their own +knowing the target system they will be running on. Packagers +have to aim for the lowest common demoninator. So this is +dead code for the forseeable future. */ +#define HAVE_PDEP 0 +#if HAVE_PDEP +/* http://www.joshbarczak.com/blog/?p=454 */ +static uint64_t uint32_interleave_2(uint32_t u1, uint32_t u2) +{ + uint64_t x = u1; + uint64_t y = u2; + uint64_t x_mask = 0x5555555555555555; + uint64_t y_mask = 0xAAAAAAAAAAAAAAAA; + return _pdep_u64(x, x_mask) | _pdep_u64(y, y_mask); +} + +static uint64_t uint32_interleave_3(uint32_t u1, uint32_t u2, uint32_t u3) +{ + /* only look at the first 21 bits */ + uint64_t x = u1 & 0x1FFFFF; + uint64_t y = u2 & 0x1FFFFF; + uint64_t z = u3 & 0x1FFFFF; + uint64_t x_mask = 0x9249249249249249; + uint64_t y_mask = 0x2492492492492492; + uint64_t z_mask = 0x4924924924924924; + return _pdep_u64(x, x_mask) | _pdep_u64(y, y_mask) | _pdep_u64(z, z_mask); +} + +#else +static uint64_t uint32_interleave_2(uint32_t u1, uint32_t u2) +{ + uint64_t x = u1; + uint64_t y = u2; + int i; + + static uint64_t B[5] = + { + 0x5555555555555555, + 0x3333333333333333, + 0x0F0F0F0F0F0F0F0F, + 0x00FF00FF00FF00FF, + 0x0000FFFF0000FFFF + }; + static uint64_t S[5] = { 1, 2, 4, 8, 16 }; + + for ( i = 4; i >= 0; i-- ) + { + x = (x | (x << S[i])) & B[i]; + y = (y | (y << S[i])) & B[i]; + } + + return x | (y << 1); +} +#endif + + +uint64_t gbox_get_sortable_hash(const GBOX *g) +{ + uint32_t ux, uy; + float fx, fy; + + /* + * Since in theory the bitwise representation of an IEEE + * float is sortable (exponents come before mantissa, etc) + * we just copy the bits directly into an int and then + * interleave those ints. + */ + if ( FLAGS_GET_GEODETIC(g->flags) ) + { + GEOGRAPHIC_POINT gpt; + POINT3D p; + p.x = (g->xmax + g->xmin) / 2.0; + p.y = (g->ymax + g->ymin) / 2.0; + p.z = (g->zmax + g->zmin) / 2.0; + normalize(&p); + cart2geog(&p, &gpt); + fx = gpt.lon; + fy = gpt.lat; + memcpy(&ux, &fx, sizeof(uint32_t)); + memcpy(&uy, &fy, sizeof(uint32_t)); + } + else + { + fx = (g->xmax + g->xmin) / 2.0; + fy = (g->ymax + g->ymin) / 2.0; + memcpy(&ux, &fx, sizeof(uint32_t)); + memcpy(&uy, &fy, sizeof(uint32_t)); + } + return uint32_interleave_2(ux, uy); +} + +int gserialized_cmp(const GSERIALIZED *g1, const GSERIALIZED *g2) +{ + int g1_is_empty, g2_is_empty, cmp; + GBOX box1, box2; + size_t sz1 = SIZE_GET(g1->size); + size_t sz2 = SIZE_GET(g2->size); + size_t hsz1 = gserialized_header_size(g1); + size_t hsz2 = gserialized_header_size(g2); + + uint8_t *b1 = (uint8_t*)g1 + hsz1; + uint8_t *b2 = (uint8_t*)g2 + hsz2; + size_t bsz1 = sz1 - hsz1; + size_t bsz2 = sz2 - hsz2; + size_t bsz = bsz1 < bsz2 ? bsz1 : bsz2; + + uint64_t hash1, hash2; + int32_t srid1 = gserialized_get_srid(g1); + int32_t srid2 = gserialized_get_srid(g2); + + g1_is_empty = (gserialized_get_gbox_p(g1, &box1) == LW_FAILURE); + g2_is_empty = (gserialized_get_gbox_p(g2, &box2) == LW_FAILURE); + + /* Empty == Empty */ + if (g1_is_empty && g2_is_empty) + { + /* POINT EMPTY == POINT EMPTY */ + /* POINT EMPTY < LINESTRING EMPTY */ + uint32_t t1 = gserialized_get_type(g1); + uint32_t t2 = gserialized_get_type(g2); + return t1 == t2 ? 0 : (t1 < t2 ? -1 : 1); + } + + /* Empty < Non-empty */ + if (g1_is_empty) + return -1; + + /* Non-empty > Empty */ + if (g2_is_empty) + return 1; + + /* Return equality for perfect equality only */ + cmp = memcmp(b1, b2, bsz); + if ( bsz1 == bsz2 && srid1 == srid2 && cmp == 0 ) + return 0; + + /* using the centroids, and preferring the X axis */ + hash1 = gbox_get_sortable_hash(&box1); + hash2 = gbox_get_sortable_hash(&box2); + + if ( hash1 > hash2 ) + return 1; + else if ( hash1 < hash2 ) + return -1; + + /* What, the hashes are equal? OK... sort on the */ + /* box minima */ + if (box1.xmin < box2.xmin) + return -1; + else if (box1.xmin > box2.xmin) + return 1; + + if (box1.ymin < box2.ymin) + return -1; + else if (box1.ymin > box2.ymin) + return 1; + + /* Still equal? OK... sort on the box maxima */ + if (box1.xmax < box2.xmax) + return -1; + else if (box1.xmax > box2.xmax) + return 1; + + if (box1.ymax < box2.ymax) + return -1; + else if (box1.ymax > box2.ymax) + return 1; + + /* How about object size? Sort on that... */ + if (hsz1 < hsz2) + return -1; + else if (hsz1 > hsz2) + return 1; + + /* Well, they aren't memcmp equal, so we'll sort on the memcmp */ + return cmp == 0 ? 0 : (cmp > 0 ? 1 : -1); +} + int gserialized_read_gbox_p(const GSERIALIZED *g, GBOX *gbox) { diff --git a/liblwgeom/liblwgeom.h.in b/liblwgeom/liblwgeom.h.in index 32c04b6f3..1207d6e5a 100644 --- a/liblwgeom/liblwgeom.h.in +++ b/liblwgeom/liblwgeom.h.in @@ -650,6 +650,12 @@ extern uint32_t gserialized_get_type(const GSERIALIZED *g); */ extern uint32_t gserialized_max_header_size(void); +/** +* Returns the size in bytes of the header, from the start of the +* object up to the type number. +*/ +extern uint32_t gserialized_header_size(const GSERIALIZED *gser); + /** * Extract the SRID from the serialized form (it is packed into * three bytes so this is a handy function). @@ -701,6 +707,16 @@ extern int gserialized_get_zm(const GSERIALIZED *gser); */ extern int gserialized_ndims(const GSERIALIZED *gser); +/** +* Return -1 if g1 is "less than" g2, 1 if g1 is "greater than" +* g2 and 0 if g1 and g2 are the "same". Equality is evaluated +* with a memcmp and size check. So it is possible that two +* identical objects where one lacks a bounding box could be +* evaluated as non-equal initially. Greater and less than +* are evaluated by calculating a sortable key from the center +* point of the object bounds. +*/ +extern int gserialized_cmp(const GSERIALIZED *g1, const GSERIALIZED *g2); /** * Call this function to drop BBOX and SRID @@ -1941,6 +1957,12 @@ extern void gbox_float_round(GBOX *gbox); */ extern int gbox_is_valid(const GBOX *gbox); +/** +* Return a sortable key based on the center point of the +* GBOX. +*/ +extern uint64_t gbox_get_sortable_hash(const GBOX *g); + /** * Utility function to get type number from string. For example, a string 'POINTZ' * would return type of 1 and z of 1 and m of 0. Valid diff --git a/postgis/geography_btree.c b/postgis/geography_btree.c index d3c3a2f68..2a4ec103d 100644 --- a/postgis/geography_btree.c +++ b/postgis/geography_btree.c @@ -54,78 +54,6 @@ static void geography_gidx_center(const GIDX *gidx, POINT3D *p) p->z = GIDX_GET_MIN(gidx, 2) + GIDX_GET_MAX(gidx, 2); } -static int geography_cmp_internal(const GSERIALIZED *g1, const GSERIALIZED *g2) -{ - int cmp, have_box1, have_box2; - int g1_is_empty = gserialized_is_empty(g1); - int g2_is_empty = gserialized_is_empty(g2); - size_t sz1 = SIZE_GET(g1->size); - size_t sz2 = SIZE_GET(g2->size); - size_t sz = sz1 < sz2 ? sz1 : sz2; - - /* Put aside some stack memory and use it for GIDX pointers. */ - char gboxmem1[GIDX_MAX_SIZE]; - char gboxmem2[GIDX_MAX_SIZE]; - GIDX *gbox1 = (GIDX*)gboxmem1; - GIDX *gbox2 = (GIDX*)gboxmem2; - POINT3D p1, p2; - - /* Empty == Empty */ - if (g1_is_empty && g2_is_empty) - { - /* POINT EMPTY == POINT EMPTY */ - /* POINT EMPTY < LINESTRING EMPTY */ - uint32_t t1 = gserialized_get_type(g1); - uint32_t t2 = gserialized_get_type(g2); - return t1 == t2 ? 0 : (t1 < t2 ? -1 : 1); - } - - /* Empty < Non-empty */ - if (g1_is_empty) - return -1; - - /* Non-empty > Empty */ - if (g2_is_empty) - return 1; - - /* Return equality for perfect equality only */ - cmp = memcmp(g1, g2, sz); - if ( sz1 == sz2 && cmp == 0 ) - return 0; - - /* Must be able to build box for each argument */ - /* (ie, not empty geometry) */ - have_box1 = gserialized_get_gidx_p(g1, gbox1); - have_box2 = gserialized_get_gidx_p(g2, gbox2); - if ( ! (have_box1 && have_box2) ) - { - lwerror("%s [%d] unable to calculate boxes of geographies", __FILE__, __LINE__); - } - - /* Order geographies more or less left-to-right */ - /* using the centroids, and preferring the X axis */ - geography_gidx_center(gbox1, &p1); - geography_gidx_center(gbox2, &p2); - - if ( ! FP_EQUALS(p1.x, p2.x) ) - return p1.x < p2.x ? -1 : 1; - - if ( ! FP_EQUALS(p1.y, p2.y) ) - return p1.y < p2.y ? -1 : 1; - - if ( ! FP_EQUALS(p1.z, p2.z) ) - return p1.z < p2.z ? -1 : 1; - - /* Geographies that are the "same in centroid" */ - /* but didn't pass the exact equality test */ - /* First order smallest-first */ - if (sz1 != sz2) - return sz1 < sz2 ? -1 : 1; - /* Then just order on the memcmp return */ - else - return cmp; -} - /* ** BTree support function. Based on two geographies return true if ** they are "less than" and false otherwise. @@ -135,7 +63,7 @@ Datum geography_lt(PG_FUNCTION_ARGS) { GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - int cmp = geography_cmp_internal(g1, g2); + int cmp = gserialized_cmp(g1, g2); if (cmp < 0) PG_RETURN_BOOL(TRUE); else @@ -151,7 +79,7 @@ Datum geography_le(PG_FUNCTION_ARGS) { GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - int cmp = geography_cmp_internal(g1, g2); + int cmp = gserialized_cmp(g1, g2); if (cmp <= 0) PG_RETURN_BOOL(TRUE); else @@ -167,7 +95,7 @@ Datum geography_gt(PG_FUNCTION_ARGS) { GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - int cmp = geography_cmp_internal(g1, g2); + int cmp = gserialized_cmp(g1, g2); if (cmp > 0) PG_RETURN_BOOL(TRUE); else @@ -183,7 +111,7 @@ Datum geography_ge(PG_FUNCTION_ARGS) { GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - int cmp = geography_cmp_internal(g1, g2); + int cmp = gserialized_cmp(g1, g2); if (cmp >= 0) PG_RETURN_BOOL(TRUE); else @@ -199,7 +127,7 @@ Datum geography_eq(PG_FUNCTION_ARGS) { GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - int cmp = geography_cmp_internal(g1, g2); + int cmp = gserialized_cmp(g1, g2); if (cmp == 0) PG_RETURN_BOOL(TRUE); else @@ -215,41 +143,5 @@ Datum geography_cmp(PG_FUNCTION_ARGS) { GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - PG_RETURN_INT32(geography_cmp_internal(g1, g2)); -} - - -#if 0 -/* -** Calculate a hash code based on the geometry data alone -*/ -static uint32 geography_hash(GSERIALIZED *g) -{ - return DatumGetUInt32(hash_any((void*)g, VARSIZE(g))); -} -/* -** BTree support function. Based on two geographies return true if -** they are "equal" and false otherwise. This version uses a hash -** function to try and shoot for a more exact equality test. -*/ -PG_FUNCTION_INFO_V1(geography_eq); -Datum geography_eq(PG_FUNCTION_ARGS) -{ - /* Perfect equals test based on hash */ - GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); - - uint32 h1 = geography_hash(g1); - uint32 h2 = geography_hash(g2); - - PG_FREE_IF_COPY(g1,0); - PG_FREE_IF_COPY(g2,0); - - if ( h1 == h2 ) - PG_RETURN_BOOL(TRUE); - - PG_RETURN_BOOL(FALSE); + PG_RETURN_INT32(gserialized_cmp(g1, g2)); } -#endif - - diff --git a/postgis/lwgeom_btree.c b/postgis/lwgeom_btree.c index 2ee935cdd..cd6c996a7 100644 --- a/postgis/lwgeom_btree.c +++ b/postgis/lwgeom_btree.c @@ -49,354 +49,68 @@ Datum lwgeom_cmp(PG_FUNCTION_ARGS); PG_FUNCTION_INFO_V1(lwgeom_lt); Datum lwgeom_lt(PG_FUNCTION_ARGS) { - GSERIALIZED *geom1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *geom2 = PG_GETARG_GSERIALIZED_P(1); - GBOX box1; - GBOX box2; - bool empty1, empty2; - - POSTGIS_DEBUG(2, "lwgeom_lt called"); - - error_if_srid_mismatch(gserialized_get_srid(geom1), gserialized_get_srid(geom2)); - - POSTGIS_DEBUG(3, "lwgeom_lt passed getSRID test"); - - empty1 = ( gserialized_get_gbox_p(geom1, &box1) == LW_FAILURE ); - empty2 = ( gserialized_get_gbox_p(geom2, &box2) == LW_FAILURE ); - - PG_FREE_IF_COPY(geom1, 0); - PG_FREE_IF_COPY(geom2, 1); - - POSTGIS_DEBUG(3, "lwgeom_lt getbox2d_p passed"); - - if ( empty1 != empty2 ) - { - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.xmin , box2.xmin) ) - { - if (box1.xmin < box2.xmin) - PG_RETURN_BOOL(TRUE); - } - - if ( ! FPeq(box1.ymin , box2.ymin) ) - { - if (box1.ymin < box2.ymin) - PG_RETURN_BOOL(TRUE); - } - - if ( ! FPeq(box1.xmax , box2.xmax) ) - { - if (box1.xmax < box2.xmax) - PG_RETURN_BOOL(TRUE); - } - - if ( ! FPeq(box1.ymax , box2.ymax) ) - { - if (box1.ymax < box2.ymax) - PG_RETURN_BOOL(TRUE); - } - - PG_RETURN_BOOL(FALSE); + GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); + GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); + int cmp = gserialized_cmp(g1, g2); + if (cmp < 0) + PG_RETURN_BOOL(TRUE); + else + PG_RETURN_BOOL(FALSE); } PG_FUNCTION_INFO_V1(lwgeom_le); Datum lwgeom_le(PG_FUNCTION_ARGS) { - GSERIALIZED *geom1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *geom2 = PG_GETARG_GSERIALIZED_P(1); - GBOX box1; - GBOX box2; - bool empty1, empty2; - - POSTGIS_DEBUG(2, "lwgeom_le called"); - - error_if_srid_mismatch(gserialized_get_srid(geom1), gserialized_get_srid(geom2)); - - empty1 = ( gserialized_get_gbox_p(geom1, &box1) == LW_FAILURE ); - empty2 = ( gserialized_get_gbox_p(geom2, &box2) == LW_FAILURE ); - - PG_FREE_IF_COPY(geom1, 0); - PG_FREE_IF_COPY(geom2, 1); - - if ( empty1 != empty2 ) - { - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.xmin , box2.xmin) ) - { - if (box1.xmin < box2.xmin) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.ymin , box2.ymin) ) - { - if (box1.ymin < box2.ymin) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.xmax , box2.xmax) ) - { - if (box1.xmax < box2.xmax) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.ymax , box2.ymax) ) - { - if (box1.ymax < box2.ymax) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - PG_RETURN_BOOL(TRUE); + GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); + GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); + int cmp = gserialized_cmp(g1, g2); + if (cmp == 0) + PG_RETURN_BOOL(TRUE); + else + PG_RETURN_BOOL(FALSE); } PG_FUNCTION_INFO_V1(lwgeom_eq); Datum lwgeom_eq(PG_FUNCTION_ARGS) { - GSERIALIZED *geom1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *geom2 = PG_GETARG_GSERIALIZED_P(1); - GBOX box1; - GBOX box2; - bool empty1, empty2; - bool result; - - POSTGIS_DEBUG(2, "lwgeom_eq called"); - - error_if_srid_mismatch(gserialized_get_srid(geom1), gserialized_get_srid(geom2)); - - gbox_init(&box1); - gbox_init(&box2); - - empty1 = ( gserialized_get_gbox_p(geom1, &box1) == LW_FAILURE ); - empty2 = ( gserialized_get_gbox_p(geom2, &box2) == LW_FAILURE ); - - PG_FREE_IF_COPY(geom1, 0); - PG_FREE_IF_COPY(geom2, 1); - - if ( empty1 != empty2 ) - { - result = FALSE; - } - else if ( ! (FPeq(box1.xmin, box2.xmin) && FPeq(box1.ymin, box2.ymin) && - FPeq(box1.xmax, box2.xmax) && FPeq(box1.ymax, box2.ymax)) ) - { - result = FALSE; - } + GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); + GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); + int cmp = gserialized_cmp(g1, g2); + if (cmp == 0) + PG_RETURN_BOOL(TRUE); else - { - result = TRUE; - } - - PG_RETURN_BOOL(result); + PG_RETURN_BOOL(FALSE); } PG_FUNCTION_INFO_V1(lwgeom_ge); Datum lwgeom_ge(PG_FUNCTION_ARGS) { - GSERIALIZED *geom1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *geom2 = PG_GETARG_GSERIALIZED_P(1); - GBOX box1; - GBOX box2; - bool empty1, empty2; - - POSTGIS_DEBUG(2, "lwgeom_ge called"); - - error_if_srid_mismatch(gserialized_get_srid(geom1), gserialized_get_srid(geom2)); - - empty1 = ( gserialized_get_gbox_p(geom1, &box1) == LW_FAILURE ); - empty2 = ( gserialized_get_gbox_p(geom2, &box2) == LW_FAILURE ); - - PG_FREE_IF_COPY(geom1, 0); - PG_FREE_IF_COPY(geom2, 1); - - if ( empty1 != empty2 ) - { - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.xmin , box2.xmin) ) - { - if (box1.xmin > box2.xmin) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.ymin , box2.ymin) ) - { - if (box1.ymin > box2.ymin) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.xmax , box2.xmax) ) - { - if (box1.xmax > box2.xmax) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.ymax , box2.ymax) ) - { - if (box1.ymax > box2.ymax) - { - PG_RETURN_BOOL(TRUE); - } - PG_RETURN_BOOL(FALSE); - } - - PG_RETURN_BOOL(TRUE); + GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); + GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); + int cmp = gserialized_cmp(g1, g2); + if (cmp >= 0) + PG_RETURN_BOOL(TRUE); + else + PG_RETURN_BOOL(FALSE); } PG_FUNCTION_INFO_V1(lwgeom_gt); Datum lwgeom_gt(PG_FUNCTION_ARGS) { - GSERIALIZED *geom1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *geom2 = PG_GETARG_GSERIALIZED_P(1); - GBOX box1; - GBOX box2; - bool empty1, empty2; - - POSTGIS_DEBUG(2, "lwgeom_gt called"); - - error_if_srid_mismatch(gserialized_get_srid(geom1), gserialized_get_srid(geom2)); - - empty1 = ( gserialized_get_gbox_p(geom1, &box1) == LW_FAILURE ); - empty2 = ( gserialized_get_gbox_p(geom2, &box2) == LW_FAILURE ); - - PG_FREE_IF_COPY(geom1, 0); - PG_FREE_IF_COPY(geom2, 1); - - if ( empty1 != empty2 ) - { - PG_RETURN_BOOL(FALSE); - } - - if ( ! FPeq(box1.xmin , box2.xmin) ) - { - if (box1.xmin > box2.xmin) - { - PG_RETURN_BOOL(TRUE); - } - } - - if ( ! FPeq(box1.ymin , box2.ymin) ) - { - if (box1.ymin > box2.ymin) - { - PG_RETURN_BOOL(TRUE); - } - } - - if ( ! FPeq(box1.xmax , box2.xmax) ) - { - if (box1.xmax > box2.xmax) - { - PG_RETURN_BOOL(TRUE); - } - } - - if ( ! FPeq(box1.ymax , box2.ymax) ) - { - if (box1.ymax > box2.ymax) - { - PG_RETURN_BOOL(TRUE); - } - } - - PG_RETURN_BOOL(FALSE); + GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); + GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); + int cmp = gserialized_cmp(g1, g2); + if (cmp > 0) + PG_RETURN_BOOL(TRUE); + else + PG_RETURN_BOOL(FALSE); } PG_FUNCTION_INFO_V1(lwgeom_cmp); Datum lwgeom_cmp(PG_FUNCTION_ARGS) { - GSERIALIZED *geom1 = PG_GETARG_GSERIALIZED_P(0); - GSERIALIZED *geom2 = PG_GETARG_GSERIALIZED_P(1); - GBOX box1; - GBOX box2; - bool empty1, empty2; - - POSTGIS_DEBUG(2, "lwgeom_cmp called"); - - error_if_srid_mismatch(gserialized_get_srid(geom1), gserialized_get_srid(geom2)); - - empty1 = ( gserialized_get_gbox_p(geom1, &box1) == LW_FAILURE ); - empty2 = ( gserialized_get_gbox_p(geom2, &box2) == LW_FAILURE ); - - PG_FREE_IF_COPY(geom1, 0); - PG_FREE_IF_COPY(geom2, 1); - - if ( empty1 || empty2 ) - { - if ( empty1 && empty2 ) - { - PG_RETURN_INT32(1); - } - else if ( empty1 ) - { - PG_RETURN_INT32(-1); - } - else - { - PG_RETURN_INT32(1); - } - } - - if ( ! FPeq(box1.xmin , box2.xmin) ) - { - if (box1.xmin < box2.xmin) - { - PG_RETURN_INT32(-1); - } - PG_RETURN_INT32(1); - } - - if ( ! FPeq(box1.ymin , box2.ymin) ) - { - if (box1.ymin < box2.ymin) - { - PG_RETURN_INT32(-1); - } - PG_RETURN_INT32(1); - } - - if ( ! FPeq(box1.xmax , box2.xmax) ) - { - if (box1.xmax < box2.xmax) - { - PG_RETURN_INT32(-1); - } - PG_RETURN_INT32(1); - } - - if ( ! FPeq(box1.ymax , box2.ymax) ) - { - if (box1.ymax < box2.ymax) - { - PG_RETURN_INT32(-1); - } - PG_RETURN_INT32(1); - } - - PG_RETURN_INT32(0); + GSERIALIZED *g1 = PG_GETARG_GSERIALIZED_P(0); + GSERIALIZED *g2 = PG_GETARG_GSERIALIZED_P(1); + PG_RETURN_INT32(gserialized_cmp(g1, g2)); } diff --git a/regress/concave_hull.sql b/regress/concave_hull.sql index a06fe2032..70b9f585b 100644 --- a/regress/concave_hull.sql +++ b/regress/concave_hull.sql @@ -11,8 +11,8 @@ FROM ST_Union(ST_GeomFromText('POLYGON((175 150, 20 40, ) As geom; SELECT - 'ST_ConcaveHull Lines 0.80', ST_Intersection(geom,ST_ConcaveHull( - geom, 0.80) ) = geom As encloses_geom, + 'ST_ConcaveHull Lines 0.80', ST_Within(geom,ST_ConcaveHull( + geom, 0.80) ) As encloses_geom, (ST_Area(ST_ConvexHull(geom)) - ST_Area(ST_ConcaveHull(geom, 0.80))) < (0.80 * ST_Area(ST_ConvexHull(geom) ) ) As reached_target @@ -27,8 +27,8 @@ FROM ST_GeomFromText('MULTILINESTRING((106 164,30 112,74 70,82 112,130 94, -- test holes vs. no holes - holes should still enclose but have smaller area than no holes -- SELECT - 'ST_ConcaveHull Lines 0.80 holes', ST_Intersection(geom,ST_ConcaveHull( - geom, 0.80, true) ) = geom As encloses_geom, + 'ST_ConcaveHull Lines 0.80 holes', ST_Within(geom,ST_ConcaveHull( + geom, 0.80, true) ) As encloses_geom, ST_Area(ST_ConcaveHull(geom, 0.80, true)) < ST_Area(ST_ConcaveHull(geom, 0.80)) As reached_target FROM ST_GeomFromText('MULTILINESTRING((106 164,30 112,74 70,82 112,130 94, diff --git a/regress/operators.sql b/regress/operators.sql index 21cc153d5..1d92bcb09 100644 --- a/regress/operators.sql +++ b/regress/operators.sql @@ -141,23 +141,26 @@ SELECT 'ndovm2', array_agg(i) FROM v WHERE g &&& 'POINTZ(0 0 1)'::geometry ORDER BY 1; -- GROUP BY on empty -SELECT '#3777', ST_AsText(geom), count(*) FROM ( -SELECT 'POINT(0 0)'::geometry geom UNION ALL -SELECT 'POINT(0 0)'::geometry UNION ALL -SELECT 'POINT(0 0)'::geometry UNION ALL -SELECT 'POINT(0 1)'::geometry UNION ALL -SELECT 'LINESTRING(0 0,0 1)'::geometry UNION ALL -SELECT 'GEOMETRYCOLLECTION EMPTY'::geometry UNION ALL -SELECT 'POINT EMPTY'::geometry -) foo +SELECT '#3777', ST_AsText(geom), count(*) +FROM (VALUES + ('POINT(0 0)'::geometry), + ('POINT(0 0)'::geometry), + ('POINT(0 0)'::geometry), + ('POINT(0 1)'::geometry), + ('LINESTRING(0 0,0 1)'::geometry), + ('GEOMETRYCOLLECTION EMPTY'::geometry), + ('POINT EMPTY'::geometry) +) AS f(geom) GROUP BY geom ORDER BY 2; -SELECT '#3777.1', ST_AsText(geom), count(*) FROM ( -SELECT 'POINT(0 0)'::geometry geom UNION ALL -SELECT 'POINT(0 0)'::geometry UNION ALL -SELECT 'POINT EMPTY'::geometry UNION ALL -SELECT 'POINT(0 0)'::geometry UNION ALL -SELECT 'POINT(0 1)'::geometry UNION ALL -SELECT 'LINESTRING(0 0,0 1)'::geometry UNION ALL -SELECT 'GEOMETRYCOLLECTION EMPTY'::geometry geom -) foo + +SELECT '#3777.1', ST_AsText(geom), count(*) +FROM (VALUES + ('POINT(0 0)'::geometry), + ('POINT(0 0)'::geometry), + ('POINT EMPTY'::geometry), + ('POINT(0 0)'::geometry), + ('POINT(0 1)'::geometry), + ('LINESTRING(0 0,0 1)'::geometry), + ('GEOMETRYCOLLECTION EMPTY'::geometry) +) AS f(geom) GROUP BY geom ORDER BY 2; diff --git a/regress/operators_expected b/regress/operators_expected index 1dfd63475..b5018c509 100644 --- a/regress/operators_expected +++ b/regress/operators_expected @@ -42,7 +42,7 @@ ab1|f ab2|f ab3|t eq1|t -eq2|t +eq2|f eq3|f cd1|4 bd1|0 @@ -56,11 +56,13 @@ ndov6|t ndov7|t ndovm1|{1,2,3,4,5,8} ndovm2|{1,2,4,6,7} -#3777|GEOMETRYCOLLECTION EMPTY|2 +#3777|GEOMETRYCOLLECTION EMPTY|1 #3777|LINESTRING(0 0,0 1)|1 +#3777|POINT EMPTY|1 #3777|POINT(0 0)|3 #3777|POINT(0 1)|1 -#3777.1|GEOMETRYCOLLECTION EMPTY|2 +#3777.1|GEOMETRYCOLLECTION EMPTY|1 #3777.1|LINESTRING(0 0,0 1)|1 +#3777.1|POINT EMPTY|1 #3777.1|POINT(0 0)|3 #3777.1|POINT(0 1)|1 diff --git a/topology/test/regress/topojson_expected b/topology/test/regress/topojson_expected index 0b1901193..3cff7db21 100644 --- a/topology/test/regress/topojson_expected +++ b/topology/test/regress/topojson_expected @@ -24,30 +24,30 @@ L1-vanilla|R3|{ "type": "MultiLineString", "arcs": [[25]]} L1-vanilla|R4|{ "type": "MultiLineString", "arcs": [[3]]} L2-vanilla|R1R2|{ "type": "MultiLineString", "arcs": [[9,-11],[4,-6]]} L2-vanilla|R4|{ "type": "MultiLineString", "arcs": [[3]]} -A1-vanilla|P1|{ "type": "MultiPolygon", "arcs": [[[20,5,-19,-20,-12,21]]]} -A1-vanilla|P2|{ "type": "MultiPolygon", "arcs": [[[18,6,-17,-18,-13,19]]]} -A1-vanilla|P3|{ "type": "MultiPolygon", "arcs": [[[16,7,-15,-16,-14,17]]]} +A1-vanilla|P1|{ "type": "MultiPolygon", "arcs": [[[21,20,5,-19,-20,-12]]]} +A1-vanilla|P2|{ "type": "MultiPolygon", "arcs": [[[19,18,6,-17,-18,-13]]]} +A1-vanilla|P3|{ "type": "MultiPolygon", "arcs": [[[17,16,7,-15,-16,-14]]]} A1-vanilla|P4|{ "type": "MultiPolygon", "arcs": [[[-2]]]} -A1-vanilla|P5|{ "type": "MultiPolygon", "arcs": [[[-1],[25]]]} -A2-vanilla|P1P2|{ "type": "MultiPolygon", "arcs": [[[20,5,6,-17,-18,-13,-12,21]]]} -A2-vanilla|P3P4|{ "type": "MultiPolygon", "arcs": [[[-2]],[[16,7,-15,-16,-14,17]]]} +A1-vanilla|P5|{ "type": "MultiPolygon", "arcs": [[[25],[-1]]]} +A2-vanilla|P1P2|{ "type": "MultiPolygon", "arcs": [[[21,20,5,6,-17,-18,-13,-12]]]} +A2-vanilla|P3P4|{ "type": "MultiPolygon", "arcs": [[[17,16,7,-15,-16,-14]],[[-2]]]} L1-edgemap|R1|{ "type": "MultiLineString", "arcs": [[0,-2]]} L1-edgemap|R2|{ "type": "MultiLineString", "arcs": [[2,-4]]} L1-edgemap|R3|{ "type": "MultiLineString", "arcs": [[4]]} L1-edgemap|R4|{ "type": "MultiLineString", "arcs": [[5]]} L2-edgemap|R1R2|{ "type": "MultiLineString", "arcs": [[0,-2],[2,-4]]} L2-edgemap|R4|{ "type": "MultiLineString", "arcs": [[4]]} -A1-edgemap|P1|{ "type": "MultiPolygon", "arcs": [[[5,4,-4,-3,-2,0]]]} -A1-edgemap|P2|{ "type": "MultiPolygon", "arcs": [[[3,9,-9,-8,-7,2]]]} -A1-edgemap|P3|{ "type": "MultiPolygon", "arcs": [[[8,13,-13,-12,-11,7]]]} +A1-edgemap|P1|{ "type": "MultiPolygon", "arcs": [[[5,4,3,-3,-2,-1]]]} +A1-edgemap|P2|{ "type": "MultiPolygon", "arcs": [[[1,2,9,-9,-8,-7]]]} +A1-edgemap|P3|{ "type": "MultiPolygon", "arcs": [[[7,8,13,-13,-12,-11]]]} A1-edgemap|P4|{ "type": "MultiPolygon", "arcs": [[[-15]]]} -A1-edgemap|P5|{ "type": "MultiPolygon", "arcs": [[[-16],[16]]]} -A2-edgemap|P1P2|{ "type": "MultiPolygon", "arcs": [[[7,6,5,-5,-4,-3,-2,0]]]} -A2-edgemap|P3P4|{ "type": "MultiPolygon", "arcs": [[[-9]],[[4,12,-12,-11,-10,3]]]} +A1-edgemap|P5|{ "type": "MultiPolygon", "arcs": [[[15],[-17]]]} +A2-edgemap|P1P2|{ "type": "MultiPolygon", "arcs": [[[7,6,5,4,-4,-3,-2,-1]]]} +A2-edgemap|P3P4|{ "type": "MultiPolygon", "arcs": [[[2,3,11,-11,-10,-9]],[[-13]]]} E32 E33 E34 E35 -A3-vanilla|P6|{ "type": "MultiPolygon", "arcs": [[[-33],[30,25],[1]],[[-34],[34]]]} +A3-vanilla|P6|{ "type": "MultiPolygon", "arcs": [[[30,25],[-33],[1]],[[34],[-34]]]} P1-vanilla|S2|{"type":"MultiPoint","coordinates":[[35,14]]} Topology 'city_data' dropped -- 2.40.0