[SCM] PostGIS branch master updated. 3.5.0alpha2-45-gbb0f19dab
git at osgeo.org
git at osgeo.org
Fri Aug 30 00:52:22 PDT 2024
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "PostGIS".
The branch, master has been updated
via bb0f19dab776e79804f44c3ab449b6924efa6886 (commit)
from 15a9061171a643553c3ce2a5c85c7657ec2dd54c (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit bb0f19dab776e79804f44c3ab449b6924efa6886
Author: gluser1357 <gluser1357 at gmx.de>
Date: Thu Aug 29 18:27:13 2024 +0200
Make optimization based on cartesian math optional (#5744)
diff --git a/doc/reference_editor.xml b/doc/reference_editor.xml
index ac5923016..83d7e94d5 100644
--- a/doc/reference_editor.xml
+++ b/doc/reference_editor.xml
@@ -1757,6 +1757,7 @@ SELECT ST_AsText( ST_RemoveRepeatedPoints( 'LINESTRING (0 0, 0 0, 1 1, 5 5, 1 1,
<funcdef>geometry <function>ST_RemoveIrrelevantPointsForView</function></funcdef>
<paramdef><type>geometry </type> <parameter>geom</parameter></paramdef>
<paramdef><type>box2d </type> <parameter>bounds</parameter></paramdef>
+ <paramdef choice="opt"><type>boolean </type><parameter>cartesian_hint = false</parameter></paramdef>
</funcprototype>
</funcsynopsis>
</refsynopsisdiv>
@@ -1775,6 +1776,14 @@ SELECT ST_AsText( ST_RemoveRepeatedPoints( 'LINESTRING (0 0, 0 0, 1 1, 5 5, 1 1,
<listitem><para>may introduce self-intersections which would make the resulting geometry invalid (see example below).</para></listitem>
</itemizedlist>
</para>
+
+ <para>If <code>cartesian_hint</code> is set to <code>true</code>,
+ the algorithm applies additional optimizations involving cartesian math
+ to further reduce the resulting point number.
+ Please note that using this option might introduce rendering artifacts
+ if the resulting coordinates are projected into another (non-cartesian)
+ coordinate system before rendering.
+ </para>
<warning><para>For polygons, this function does currently not ensure that the result is valid.
This situation can be checked with <xref linkend="ST_IsValid"/> and repaired with <xref linkend="ST_MakeValid"/>.
@@ -1818,7 +1827,7 @@ SELECT ST_AsText( ST_RemoveRepeatedPoints( 'LINESTRING (0 0, 0 0, 1 1, 5 5, 1 1,
SELECT ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('MULTIPOLYGON(((10 10, 20 10, 30 10, 40 10, 20 20, 10 20, 10 10)),((10 10, 20 10, 20 20, 10 20, 10 10)))'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
st_astext
---------
@@ -1829,7 +1838,7 @@ SELECT ST_AsText( ST_RemoveRepeatedPoints( 'LINESTRING (0 0, 0 0, 1 1, 5 5, 1 1,
SELECT ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('MULTILINESTRING((0 0, 10 0,20 0,30 0), (0 15, 5 15, 10 15, 15 15, 20 15, 25 15, 30 15, 40 15), (13 13,15 15,17 17))'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
st_astext
---------
@@ -1840,13 +1849,35 @@ SELECT ST_AsText( ST_RemoveRepeatedPoints( 'LINESTRING (0 0, 0 0, 1 1, 5 5, 1 1,
SELECT ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('LINESTRING(0 0, 10 0,20 0,30 0)'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
st_astext
---------
LINESTRING EMPTY
</programlisting>
+ <programlisting>
+ SELECT ST_AsText(
+ ST_RemoveIrrelevantPointsForView(
+ ST_GeomFromText('POLYGON((0 30, 15 30, 30 30, 30 0, 0 0, 0 30))'),
+ ST_MakeEnvelope(12,12,18,18), true));
+
+ st_astext
+ ---------
+ POLYGON((15 30,30 0,0 0,15 30))
+ </programlisting>
+
+ <programlisting>
+ SELECT ST_AsText(
+ ST_RemoveIrrelevantPointsForView(
+ ST_GeomFromText('POLYGON((0 30, 15 30, 30 30, 30 0, 0 0, 0 30))'),
+ ST_MakeEnvelope(12,12,18,18)));
+
+ st_astext
+ ---------
+ POLYGON((0 30,30 30,30 0,0 0,0 30))
+ </programlisting>
+
</refsection>
<refsection>
diff --git a/liblwgeom/Makefile.in b/liblwgeom/Makefile.in
index 9ed2c38ca..caed0abdb 100644
--- a/liblwgeom/Makefile.in
+++ b/liblwgeom/Makefile.in
@@ -134,7 +134,8 @@ SA_OBJS = \
lwchaikins.o \
lwmval.o \
lwkmeans.o \
- varint.o
+ varint.o \
+ lwgeom_remove_irrelevant_points_for_view.o
NM_OBJS = \
lwspheroid.o
@@ -177,7 +178,8 @@ SA_HEADERS = \
measures3d.h \
measures.h \
stringbuffer.h \
- varint.h
+ varint.h \
+ lwgeom_remove_irrelevant_points_for_view.h
all: liblwgeom.la
diff --git a/liblwgeom/cunit/Makefile.in b/liblwgeom/cunit/Makefile.in
index 83fc75baf..f397414c9 100644
--- a/liblwgeom/cunit/Makefile.in
+++ b/liblwgeom/cunit/Makefile.in
@@ -79,6 +79,7 @@ OBJS= \
cu_varint.o \
cu_unionfind.o \
cu_wrapx.o \
+ cu_remove_irrelevant_points_for_view.o \
cu_tester.o
ifeq (@SFCGAL@,sfcgal)
diff --git a/liblwgeom/cunit/cu_remove_irrelevant_points_for_view.c b/liblwgeom/cunit/cu_remove_irrelevant_points_for_view.c
new file mode 100644
index 000000000..4d25f540f
--- /dev/null
+++ b/liblwgeom/cunit/cu_remove_irrelevant_points_for_view.c
@@ -0,0 +1,50 @@
+/**********************************************************************
+ *
+ * PostGIS - Spatial Types for PostgreSQL
+ * http://postgis.net
+ *
+ * Copyright (C) 2024 Sam Peters <gluser1357 at gmx.de>
+ *
+ * This is free software; you can redistribute and/or modify it under
+ * the terms of the GNU General Public Licence. See the COPYING file.
+ *
+ **********************************************************************/
+
+#include "CUnit/Basic.h"
+#include "cu_tester.h"
+
+#include "lwgeom_remove_irrelevant_points_for_view.h"
+
+// test case for lwgeom_remove_irrelevant_points_for_view()
+static void test_lwgeom_remove_irrelevant_points_for_view(void)
+{
+ LWGEOM *geom;
+ char *wkt, *in_wkt;
+ GBOX *bbox;
+
+ bbox = gbox_new(0);
+ bbox->xmin = 12;
+ bbox->xmax = 18;
+ bbox->ymin = 12;
+ bbox->ymax = 18;
+
+ geom = lwgeom_from_wkt("POLYGON((0 30, 15 30, 30 30, 30 0, 0 0, 0 30))", LW_PARSER_CHECK_NONE);
+ CU_ASSERT(geom != NULL);
+
+ lwgeom_remove_irrelevant_points_for_view(geom, bbox, true);
+ wkt = lwgeom_to_ewkt(geom);
+ in_wkt = "POLYGON((15 30,30 0,0 0,15 30))";
+ ASSERT_STRING_EQUAL(wkt, in_wkt);
+
+ lwfree(wkt);
+ lwgeom_free(geom);
+ lwfree(bbox);
+}
+
+void remove_irrelevant_points_for_view_suite_setup(void);
+void
+remove_irrelevant_points_for_view_suite_setup(void)
+{
+ CU_pSuite suite = CU_add_suite("remove_irrelevant_points_for_view", NULL, NULL);
+ PG_ADD_TEST(suite, test_lwgeom_remove_irrelevant_points_for_view);
+}
diff --git a/liblwgeom/cunit/cu_tester.c b/liblwgeom/cunit/cu_tester.c
index 2aa1f6ad9..0df215893 100644
--- a/liblwgeom/cunit/cu_tester.c
+++ b/liblwgeom/cunit/cu_tester.c
@@ -79,6 +79,7 @@ extern void surface_suite_setup(void);
extern void wkb_in_suite_setup(void);
extern void wkt_in_suite_setup(void);
extern void wrapx_suite_setup(void);
+extern void remove_irrelevant_points_for_view_suite_setup(void);
/* AND ADD YOUR SUITE SETUP FUNCTION HERE (2 of 2) */
@@ -133,6 +134,7 @@ PG_SuiteSetup setupfuncs[] = {algorithms_suite_setup,
wkt_in_suite_setup,
wkt_out_suite_setup,
wrapx_suite_setup,
+ remove_irrelevant_points_for_view_suite_setup,
NULL};
diff --git a/postgis/lwgeom_remove_irrelevant_points_for_view.c b/liblwgeom/lwgeom_remove_irrelevant_points_for_view.c
similarity index 77%
copy from postgis/lwgeom_remove_irrelevant_points_for_view.c
copy to liblwgeom/lwgeom_remove_irrelevant_points_for_view.c
index 069918be4..6b246dcdf 100644
--- a/postgis/lwgeom_remove_irrelevant_points_for_view.c
+++ b/liblwgeom/lwgeom_remove_irrelevant_points_for_view.c
@@ -22,16 +22,7 @@
*
**********************************************************************/
-#include "postgres.h"
-#include "funcapi.h"
-#include "utils/array.h"
-#include "utils/builtins.h"
-#include "utils/lsyscache.h"
-#include "utils/numeric.h"
-#include "access/htup_details.h"
-
-#include "liblwgeom.h"
-#include "liblwgeom_internal.h"
+#include "lwgeom_remove_irrelevant_points_for_view.h"
// ===============================================================================
// Encodes the location of a value related to min and max.
@@ -41,8 +32,8 @@
// - 0x2 for min <= value <= max
// - 0x4 for value > max
// ===============================================================================
-static int encodeToBits(double value, double min, double max) {
- return value < min ? 0x1 : value <= max ? 0x2 : 0x4;
+int encodeToBits(double value, double min, double max) {
+ return value < min ? 0x1 : value <= max ? 0x2 : 0x4;
}
// ===============================================================================
@@ -63,7 +54,7 @@ static int encodeToBits(double value, double min, double max) {
// - 0x4 if xs >= xmax (top or bottom), or ys >= ymax (left or right)
// - 0x0 if no cutting point can be determined (if S and L are parallel or straightPosition is not valid)
// ===============================================================================
-static int encodeToBitsStraight(double xa, double ya, double xb, double yb, double xmin, double ymin, double xmax, double ymax, int straightPosition) {
+int encodeToBitsStraight(double xa, double ya, double xb, double yb, double xmin, double ymin, double xmax, double ymax, int straightPosition) {
double x, y, dx, dy, d, c;
@@ -128,8 +119,20 @@ static int encodeToBitsStraight(double xa, double ya, double xb, double yb, doub
// outside points would be optimal to keep. Since this would introduce a lot
// more code complexity and a backing array and would likely have
// no real practical impact this step is skipped.
+//
+// Note on cartesian_hint:
+// - if false, the algorithm removes one or a sequence of points
+// lying on "the same side" (either top, bottom, left or right) of the
+// given bounds except the first and last point of that sequence.
+// - if true, the algorithm assumes that the coordinates are rendered in
+// a cartesian coordinate system and tries to remove further points
+// if the resulting connection lines do not cross the borders of
+// the rectangular view given by the bounds.
+// Please note that this option might produce rendering artifacts
+// if the coordinates are used for rendering in a non-cartesian
+// coordinate system.
// ===============================================================================
-static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
+void removePoints(POINTARRAY *points, GBOX *bounds, bool closed, bool cartesian_hint) {
int npoints, minpoints;
double xmin, ymin, xmax, ymax;
@@ -145,9 +148,6 @@ static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
bool cutting;
int crossingN;
- bool optimize;
- optimize = true;
-
// point number check
npoints = points->npoints;
minpoints = closed ? 4 : 2; // min points for each polygon ring or linestring
@@ -173,6 +173,7 @@ static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
else {
getPoint4d_p(points, 0, &p0); // for linestrings reuse start point
}
+
xx0 = p0.x;
yy0 = p0.y;
vx0 = encodeToBits(xx0, xmin, xmax);
@@ -217,7 +218,7 @@ static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
// check for irrelevant points that would introduce "diagonal"
// lines between different outside quadrants which may cross the bounds
- if (optimize && !skip && !same && !inside && (vx0 | vy0) != 0x02 && (vx1 | vy1) != 0x02) {
+ if (cartesian_hint && !skip && !same && !inside && (vx0 | vy0) != 0x02 && (vx1 | vy1) != 0x02) {
vvx = 0;
vvy = 0;
@@ -271,7 +272,8 @@ static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
clear |= vyall == 0x04; // completely bottom outside
// clear if everything is outside and not enclosing
- if (optimize && !clear && !insideAll) { // not required if points inside bbox
+ if (cartesian_hint && !clear && !insideAll) { // not required if points inside bbox
+
cutting = false;
for (int r = 0; r < w - 1; r++) {
@@ -312,77 +314,15 @@ static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
points->npoints = w;
}
-// ===============================================================================
-// remove points that are irrelevant for rendering the geometry within
-// a view specified by rectangular bounds.
-// 2D-(MULTI)POLYGONs and (MULTI)LINESTRINGs are evaluated, others keep untouched.
-// ===============================================================================
-PG_FUNCTION_INFO_V1(ST_RemoveIrrelevantPointsForView);
-Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
+
+void lwgeom_remove_irrelevant_points_for_view(LWGEOM *geom, GBOX *bbox, bool cartesian_hint) {
unsigned int i, j, iw, jw;
- // gserialized logic see for example in /postgis/lwgeom_functions_basic.c,
- // type definitions see /liblwgeom/liblwgeom.h(.in)
-
- GSERIALIZED *serialized_in;
- GSERIALIZED *serialized_out;
-
- LWGEOM *geom;
- GBOX *bbox;
-
- // geom input check
- if (PG_GETARG_POINTER(0) == NULL) {
- PG_RETURN_NULL();
- }
-
- serialized_in = (GSERIALIZED *)PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0));
-
- // box input check
- if (PG_GETARG_POINTER(1) == NULL) {
- // no BBOX given, leave untouched
- PG_RETURN_POINTER(serialized_in);
- }
-
- // type check (only polygon and line types are supported yet)
- if (gserialized_get_type(serialized_in) != POLYGONTYPE &&
- gserialized_get_type(serialized_in) != MULTIPOLYGONTYPE &&
- gserialized_get_type(serialized_in) != LINETYPE &&
- gserialized_get_type(serialized_in) != MULTILINETYPE) {
-
- // no (multi)polygon or (multi)linetype, leave untouched
- PG_RETURN_POINTER(serialized_in);
- }
-
- // deserialize geom and copy coordinates (no clone_deep)
- geom = lwgeom_from_gserialized(serialized_in);
-
- // bbox checks
- bbox = (GBOX*)PG_GETARG_DATUM(1);
- if (!geom->bbox) {
- lwgeom_add_bbox(geom);
- }
-
- if (!geom->bbox) {
- // no bbox determinable, leave untouched
- lwgeom_free(geom);
- PG_RETURN_POINTER(serialized_in);
- }
-
- if (bbox->xmin <= geom->bbox->xmin &&
- bbox->ymin <= geom->bbox->ymin &&
- bbox->xmax >= geom->bbox->xmax &&
- bbox->ymax >= geom->bbox->ymax) {
-
- // trivial case: geometry is fully covered by requested bbox
- lwgeom_free(geom);
- PG_RETURN_POINTER(serialized_in);
- }
-
if (geom->type == LINETYPE) {
LWLINE* line = (LWLINE*)geom;
- removePoints(line->points, bbox, false);
+ removePoints(line->points, bbox, false, cartesian_hint);
}
if (geom->type == MULTILINETYPE) {
@@ -391,7 +331,7 @@ Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
iw = 0;
for (i=0; i<mline->ngeoms; i++) {
LWLINE* line = mline->geoms[i];
- removePoints(line->points, bbox, false);
+ removePoints(line->points, bbox, false, cartesian_hint);
if (line->points->npoints) {
// keep (reduced) line
@@ -410,7 +350,7 @@ Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
LWPOLY* polygon = (LWPOLY*)geom;
iw = 0;
for (i=0; i<polygon->nrings; i++) {
- removePoints(polygon->rings[i], bbox, true);
+ removePoints(polygon->rings[i], bbox, true, cartesian_hint);
if (polygon->rings[i]->npoints) {
// keep (reduced) ring
@@ -443,7 +383,7 @@ Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
LWPOLY* polygon = mpolygon->geoms[j];
iw = 0;
for (i=0; i<polygon->nrings; i++) {
- removePoints(polygon->rings[i], bbox, true);
+ removePoints(polygon->rings[i], bbox, true, cartesian_hint);
if (polygon->rings[i]->npoints) {
// keep (reduced) ring
@@ -476,14 +416,4 @@ Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
}
mpolygon->ngeoms = jw;
}
-
- // recompute bbox if computed previously (may result in NULL)
- lwgeom_drop_bbox(geom);
- lwgeom_add_bbox(geom);
-
- serialized_out = gserialized_from_lwgeom(geom, 0);
- lwgeom_free(geom);
-
- PG_FREE_IF_COPY(serialized_in, 0); // see postgis/lwgeom_functions_basic.c, force_2d
- PG_RETURN_POINTER(serialized_out);
}
diff --git a/liblwgeom/lwgeom_remove_irrelevant_points_for_view.h b/liblwgeom/lwgeom_remove_irrelevant_points_for_view.h
new file mode 100644
index 000000000..a4014e51b
--- /dev/null
+++ b/liblwgeom/lwgeom_remove_irrelevant_points_for_view.h
@@ -0,0 +1,33 @@
+/**********************************************************************
+ *
+ * PostGIS - Spatial Types for PostgreSQL
+ * http://postgis.net
+ *
+ * PostGIS is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * PostGIS is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
+ *
+ **********************************************************************
+ *
+ * Copyright (C) 2024 Sam Peters <gluser1357 at gmx.de>
+ *
+ **********************************************************************/
+
+#include "liblwgeom.h"
+#include "liblwgeom_internal.h"
+
+/**
+ * remove points that are irrelevant for rendering the geometry within
+ * a view specified by rectangular bounds.
+ * 2D-(MULTI)POLYGONs and (MULTI)LINESTRINGs are evaluated, others keep untouched.
+ */
+void lwgeom_remove_irrelevant_points_for_view(LWGEOM *geom, GBOX *bbox, bool cartesian_hint);
diff --git a/postgis/lwgeom_remove_irrelevant_points_for_view.c b/postgis/lwgeom_remove_irrelevant_points_for_view.c
index 069918be4..c806f3925 100644
--- a/postgis/lwgeom_remove_irrelevant_points_for_view.c
+++ b/postgis/lwgeom_remove_irrelevant_points_for_view.c
@@ -30,287 +30,7 @@
#include "utils/numeric.h"
#include "access/htup_details.h"
-#include "liblwgeom.h"
-#include "liblwgeom_internal.h"
-
-// ===============================================================================
-// Encodes the location of a value related to min and max.
-
-// Returns
-// - 0x1 for value < min
-// - 0x2 for min <= value <= max
-// - 0x4 for value > max
-// ===============================================================================
-static int encodeToBits(double value, double min, double max) {
- return value < min ? 0x1 : value <= max ? 0x2 : 0x4;
-}
-
-// ===============================================================================
-// Encodes the location where a line segment S given by (xa, ya) and (xb, yb)
-// cuts a straight L (either xmin, ymin, xmax or ymax) of a bounding box
-// defined by (xmin, ymin) and (xmax, ymax) without actually computing
-// the cutting point (xs, ys) for performance reasons.
-//
-// Allowed values for the straightPosition are
-// - 1 for top (ymin)
-// - 2 for bottom (ymax)
-// - 3 for left (xmin)
-// - 4 for right (xmax)
-//
-// Returns
-// - 0x1 if xs < xmin (top or bottom), or ys < ymin (left or right)
-// - 0x2 if xmin <= xs < xmax (top or bottom), or ymin <= ys < ymax (left or right)
-// - 0x4 if xs >= xmax (top or bottom), or ys >= ymax (left or right)
-// - 0x0 if no cutting point can be determined (if S and L are parallel or straightPosition is not valid)
-// ===============================================================================
-static int encodeToBitsStraight(double xa, double ya, double xb, double yb, double xmin, double ymin, double xmax, double ymax, int straightPosition) {
-
- double x, y, dx, dy, d, c;
-
- if (straightPosition == 1 || straightPosition == 2) {
-
- // top and bottom
- if (ya == yb) return 0;
-
- y = straightPosition == 2 ? ymax : ymin;
- if (ya < y && yb < y) return 0;
- if (ya > y && yb > y) return 0;
-
- dx = xb - xa;
- dy = yb - ya;
- d = dy;
- c = dx * (y - ya);
- if (dy < 0) {
- d = -d;
- c = -c;
- }
- return c < d * (xmin - xa) ? 0x1 : c < d * (xmax - xa) ? 0x2 : 0x4;
- }
-
- if (straightPosition == 3 || straightPosition == 4) {
-
- // left and right
- if (xa == xb) return 0;
-
- x = straightPosition == 4 ? xmax : xmin;
- if (xa < x && xb < x) return 0;
- if (xa > x && xb > x) return 0;
-
- dx = xb - xa;
- dy = yb - ya;
- d = dx;
- c = dy * (x - xa);
- if (dx < 0) {
- d = -d;
- c = -c;
- }
- return c < d * (ymin - ya) ? 0x1 : c < d * (ymax - ya) ? 0x2 : 0x4;
- }
-
- return 0;
-}
-
-// ===============================================================================
-// Helper function for polygon and polyline POINTARRAY's.
-// Removes points being irrelevant for rendering the geometry
-// within a view specified by rectangular bounds without introducing
-// new points. The main idea is to sequentially evaluate a group of
-// three consecutive points and decide if the second point has impact
-// on the rendering result within the given bounds. If it doesn't
-// have impact it will be skipped.
-//
-// Note on the algorithm:
-// The algorithm tries to remove points outside the given bounds
-// on a best-effort basis, optimized for speed. It doesn't use allocs,
-// instead it reuses the given point array.
-// There are some known cases where a minor improvement (slightly less points
-// in the result) could be achieved by checking which point(s) of a sequence of
-// outside points would be optimal to keep. Since this would introduce a lot
-// more code complexity and a backing array and would likely have
-// no real practical impact this step is skipped.
-// ===============================================================================
-static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
-
- int npoints, minpoints;
- double xmin, ymin, xmax, ymax;
-
- int i, j, next, w;
- int vx, vy, vx0, vy0, vx1, vy1, vxall, vyall;
- double xx, yy, xx0, yy0, xx1, yy1;
- bool sameX, sameY, same, insideX, insideY, inside, insideAll, skip, clear;
- int vvx, vvy;
- POINT4D p, p0, p1; // current, previous, next;
-
- double xa, ya, xb, yb;
- bool cutting;
- int crossingN;
-
- bool optimize;
- optimize = true;
-
- // point number check
- npoints = points->npoints;
- minpoints = closed ? 4 : 2; // min points for each polygon ring or linestring
- if (npoints < minpoints) {
- // clear if not expected minimum number of points
- points->npoints = 0;
- return;
- }
-
- xmin = bounds->xmin;
- ymin = bounds->ymin;
- xmax = bounds->xmax;
- ymax = bounds->ymax;
-
- // get previous point [i-1]
- if (closed) {
- getPoint4d_p(points, 0, &p);
- getPoint4d_p(points, npoints - 1, &p0);
- if (p.x != p0.x || p.y != p0.y) return; // requirement for polygons: startpoint equals endpoint. Leave untouched of not met.
- npoints--; // remove double here, and re-add at the end
- getPoint4d_p(points, npoints - 1, &p0);
- }
- else {
- getPoint4d_p(points, 0, &p0); // for linestrings reuse start point
- }
- xx0 = p0.x;
- yy0 = p0.y;
- vx0 = encodeToBits(xx0, xmin, xmax);
- vy0 = encodeToBits(yy0, ymin, ymax);
-
- // for all points
- w = 0;
- vxall = 0;
- vyall = 0;
- insideAll = false;
- for (i = 0; i < npoints; i++) {
-
- // get current point [i]
- getPoint4d_p(points, i, &p);
- xx = p.x;
- yy = p.y;
- vx = encodeToBits(xx, xmin, xmax);
- vy = encodeToBits(yy, ymin, ymax);
-
- // get subsequent point [i+1]
- next = i + 1;
- if (next == npoints) {
- if (closed) next = 0; // for polygons, use (new) start point as end point
- else next = i; // for linestrings reuse last point as end point
- }
- getPoint4d_p(points, next, &p1);
- xx1 = p1.x;
- yy1 = p1.y;
- vx1 = encodeToBits(xx1, xmin, xmax);
- vy1 = encodeToBits(yy1, ymin, ymax);
-
- sameX = vx == vx1 && vx == vx0;
- sameY = vy == vy1 && vy == vy0;
- same = sameX && sameY;
- insideX = vx == 0x02;
- insideY = vy == 0x02;
- inside = insideX && insideY;
-
- skip = sameX && sameY && !inside; // three consecutive points in same outside quarter, leave out central one
- skip |= sameX && !insideX; // three consecutive points in same outside area (left or right), leave out central one
- skip |= sameY && !insideY; // three consecutive points in same outside area (top or bottom), leave out central one
-
- // check for irrelevant points that would introduce "diagonal"
- // lines between different outside quadrants which may cross the bounds
- if (optimize && !skip && !same && !inside && (vx0 | vy0) != 0x02 && (vx1 | vy1) != 0x02) {
-
- vvx = 0;
- vvy = 0;
- for (j = 0; j < 2; j++) {
- // left, right
- vvx |= encodeToBitsStraight(xx0, yy0, xx, yy, xmin, ymin, xmax, ymax, j + 1);
- vvx |= encodeToBitsStraight(xx, yy, xx1, yy1, xmin, ymin, xmax, ymax, j + 1);
- vvx |= encodeToBitsStraight(xx0, yy0, xx1, yy1, xmin, ymin, xmax, ymax, j + 1);
- if ((vvx & 0x2) != 0) break;
-
- // top, bottom
- vvy |= encodeToBitsStraight(xx0, yy0, xx, yy, xmin, ymin, xmax, ymax, j + 3);
- vvy |= encodeToBitsStraight(xx, yy, xx1, yy1, xmin, ymin, xmax, ymax, j + 3);
- vvy |= encodeToBitsStraight(xx0, yy0, xx1, yy1, xmin, ymin, xmax, ymax, j + 3);
- if ((vvy & 0x2) != 0) break;
- }
-
- if (((vvx | vvy) & 0x2) == 0) {
- // if no bbox bounds crossed:
- skip |= vvx == 0x1; // three cutting points are left outside
- skip |= vvx == 0x4; // three cutting points are right outside
- skip |= vvy == 0x1; // three cutting points are top outside
- skip |= vvy == 0x4; // three cutting points are bottom outside
- }
- }
-
- if (skip) continue;
-
- // save current point at [w <= i]
- ptarray_set_point4d(points, w++, &p);
- vx0 = vx;
- vy0 = vy;
- xx0 = xx;
- yy0 = yy;
- vxall |= vx;
- vyall |= vy;
- insideAll |= inside;
- }
-
- if (closed && w > 0) {
- // re-add first new point at the end if closed
- getPoint4d_p(points, 0, &p);
- ptarray_set_point4d(points, w++, &p);
- }
-
- // eval empty cases
- clear = w < minpoints; // too less points
- clear |= vxall == 0x01; // completely left outside
- clear |= vxall == 0x04; // completely right outside
- clear |= vyall == 0x01; // completely top outside
- clear |= vyall == 0x04; // completely bottom outside
-
- // clear if everything is outside and not enclosing
- if (optimize && !clear && !insideAll) { // not required if points inside bbox
- cutting = false;
- for (int r = 0; r < w - 1; r++) {
-
- getPoint4d_p(points, r, &p);
- getPoint4d_p(points, r + 1, &p1);
-
- xa = p.x;
- ya = p.y;
- xb = p1.x;
- yb = p1.y;
-
- for (j = 0; j < 4 && !cutting; j++) {
- cutting |= encodeToBitsStraight(xa, ya, xb, yb, xmin, ymin, xmax, ymax, j + 1) == 0x2;
- }
- }
-
- if (!cutting && closed) {
- // test if polygon surrounds bbox completely or is fully contained within bbox
- // using even-odd rule algorithm
- crossingN = 0;
- for (int r = 0; r < w - 1; r++) {
-
- getPoint4d_p(points, r, &p);
- getPoint4d_p(points, r + 1, &p1);
-
- xa = p.x;
- ya = p.y;
- xb = p1.x;
- yb = p1.y;
-
- if (encodeToBitsStraight(xa, ya, xb, yb, xmin, ymin, xmax, ymax, 1) == 0x1) crossingN++;
- }
- clear |= crossingN % 2 == 0; // not surrounding, we can clear
- }
- }
- if (clear) w = 0;
-
- points->npoints = w;
-}
+#include "lwgeom_remove_irrelevant_points_for_view.h"
// ===============================================================================
// remove points that are irrelevant for rendering the geometry within
@@ -320,16 +40,12 @@ static void removePoints(POINTARRAY *points, GBOX *bounds, bool closed) {
PG_FUNCTION_INFO_V1(ST_RemoveIrrelevantPointsForView);
Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
- unsigned int i, j, iw, jw;
-
- // gserialized logic see for example in /postgis/lwgeom_functions_basic.c,
- // type definitions see /liblwgeom/liblwgeom.h(.in)
-
GSERIALIZED *serialized_in;
GSERIALIZED *serialized_out;
LWGEOM *geom;
GBOX *bbox;
+ bool cartesian_hint = false;
// geom input check
if (PG_GETARG_POINTER(0) == NULL) {
@@ -344,6 +60,11 @@ Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
PG_RETURN_POINTER(serialized_in);
}
+ // get (optional) cartesian_hint flag for advanced optimizations
+ // that assume the the coordinates can be seen as coordinates
+ // to be rendered in a cartesian coordinate system.
+ cartesian_hint = (PG_NARGS() > 2 && !PG_ARGISNULL(2)) ? PG_GETARG_BOOL(2) : false;
+
// type check (only polygon and line types are supported yet)
if (gserialized_get_type(serialized_in) != POLYGONTYPE &&
gserialized_get_type(serialized_in) != MULTIPOLYGONTYPE &&
@@ -379,103 +100,8 @@ Datum ST_RemoveIrrelevantPointsForView(PG_FUNCTION_ARGS) {
PG_RETURN_POINTER(serialized_in);
}
- if (geom->type == LINETYPE) {
-
- LWLINE* line = (LWLINE*)geom;
- removePoints(line->points, bbox, false);
- }
-
- if (geom->type == MULTILINETYPE) {
-
- LWMLINE* mline = (LWMLINE*)geom;
- iw = 0;
- for (i=0; i<mline->ngeoms; i++) {
- LWLINE* line = mline->geoms[i];
- removePoints(line->points, bbox, false);
-
- if (line->points->npoints) {
- // keep (reduced) line
- mline->geoms[iw++] = line;
- }
- else {
- // discard current line
- lwfree(line);
- }
- }
- mline->ngeoms = iw;
- }
-
- if (geom->type == POLYGONTYPE) {
-
- LWPOLY* polygon = (LWPOLY*)geom;
- iw = 0;
- for (i=0; i<polygon->nrings; i++) {
- removePoints(polygon->rings[i], bbox, true);
-
- if (polygon->rings[i]->npoints) {
- // keep (reduced) ring
- polygon->rings[iw++] = polygon->rings[i];
- }
- else {
- if (!i) {
- // exterior ring outside, free and skip all rings
- unsigned int k;
- for (k=0; k<polygon->nrings; k++) {
- lwfree(polygon->rings[k]);
- }
- break;
- }
- else {
- // free and remove current interior ring
- lwfree(polygon->rings[i]);
- }
- }
- }
- polygon->nrings = iw;
- }
-
- if (geom->type == MULTIPOLYGONTYPE) {
-
- LWMPOLY* mpolygon = (LWMPOLY*)geom;
- jw = 0;
- for (j=0; j<mpolygon->ngeoms; j++) {
-
- LWPOLY* polygon = mpolygon->geoms[j];
- iw = 0;
- for (i=0; i<polygon->nrings; i++) {
- removePoints(polygon->rings[i], bbox, true);
-
- if (polygon->rings[i]->npoints) {
- // keep (reduced) ring
- polygon->rings[iw++] = polygon->rings[i];
- }
- else {
- if (!i) {
- // exterior ring outside, free and skip all rings
- unsigned int k;
- for (k=0; k<polygon->nrings; k++) {
- lwfree(polygon->rings[k]);
- }
- break;
- }
- else {
- // free and remove current interior ring
- lwfree(polygon->rings[i]);
- }
- }
- }
- polygon->nrings = iw;
-
- if (iw) {
- mpolygon->geoms[jw++] = polygon;
- }
- else {
- // free and remove polygon from multipolygon
- lwfree(polygon);
- }
- }
- mpolygon->ngeoms = jw;
- }
+ // now reduce points if possible
+ lwgeom_remove_irrelevant_points_for_view(geom, bbox, cartesian_hint);
// recompute bbox if computed previously (may result in NULL)
lwgeom_drop_bbox(geom);
diff --git a/postgis/postgis.sql.in b/postgis/postgis.sql.in
index e62a2c1c8..b45ac89ae 100644
--- a/postgis/postgis.sql.in
+++ b/postgis/postgis.sql.in
@@ -6982,7 +6982,7 @@ CREATE OR REPLACE FUNCTION ST_3DLineInterpolatePoint(geometry, float8)
-- ST_RemoveIrrelevantPointsForView
-----------------------------------------------------------------------
-- Availability: 3.5.0
-CREATE OR REPLACE FUNCTION ST_RemoveIrrelevantPointsForView(geometry, box2d)
+CREATE OR REPLACE FUNCTION ST_RemoveIrrelevantPointsForView(geometry, box2d, boolean default false)
RETURNS geometry
AS 'MODULE_PATHNAME','ST_RemoveIrrelevantPointsForView'
LANGUAGE 'c' IMMUTABLE STRICT PARALLEL SAFE
diff --git a/postgis/postgis_after_upgrade.sql b/postgis/postgis_after_upgrade.sql
index 8238c1709..327e6a05a 100644
--- a/postgis/postgis_after_upgrade.sql
+++ b/postgis/postgis_after_upgrade.sql
@@ -205,6 +205,7 @@ SELECT _postgis_drop_function_by_signature('ST_Distance(geography, geography)');
SELECT _postgis_drop_function_by_signature('ST_Distance(geography, geography, float8, boolean)');
SELECT _postgis_drop_function_by_signature('ST_Buffer(geometry, float8, cstring)');
SELECT _postgis_drop_function_by_signature('ST_IsValidDetail(geometry)');
+SELECT _postgis_drop_function_by_signature('ST_RemoveIrrelevantPointsForView(geometry, box2d)'); -- temporarely introduced in 3.5.0dev, replaced by ST_RemoveIrrelevantPointsForView(geometry, box2d, boolean) in 3.5.0dev
SELECT _postgis_drop_function_by_identity('ST_AsKML','int4, geometry, int4, text');
SELECT _postgis_drop_function_by_identity('ST_AsGeoJson','int4, geometry, int4, int4');
SELECT _postgis_drop_function_by_identity('_ST_AsGeoJson','int4, geometry, int4, int4');
diff --git a/regress/core/remove_irrelevant_points_for_view.sql b/regress/core/remove_irrelevant_points_for_view.sql
index 3777c5f02..700512b15 100644
--- a/regress/core/remove_irrelevant_points_for_view.sql
+++ b/regress/core/remove_irrelevant_points_for_view.sql
@@ -1,24 +1,39 @@
SELECT 0, ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('MULTIPOLYGON(((10 10, 20 10, 30 10, 40 10, 20 20, 10 20, 10 10)),((10 10, 20 10, 20 20, 10 20, 10 10)))'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
SELECT 1, ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('MULTILINESTRING((0 0, 10 0,20 0,30 0), (0 15, 5 15, 10 15, 15 15, 20 15, 25 15, 30 15, 40 15), (13 13,15 15,17 17))'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
SELECT 2, ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('LINESTRING(0 0, 10 0,20 0,30 0)'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
SELECT 3, ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('MULTIPOLYGON Z(((10 10 1, 20 10 2, 30 10 3, 40 10 4, 20 20 5, 10 20 6, 10 10 1)),((10 10 1, 20 10 2, 20 20 3, 10 20 4, 10 10 5)))'),
- ST_MakeEnvelope(12,12,18,18)));
+ ST_MakeEnvelope(12,12,18,18), true));
SELECT 4, ST_AsText(
ST_RemoveIrrelevantPointsForView(
ST_GeomFromText('LINESTRING Z(0 0 1, 10 0 2,20 0 3,30 0 1)'),
+ ST_MakeEnvelope(12,12,18,18), true));
+
+SELECT 5, ST_AsText(
+ ST_RemoveIrrelevantPointsForView(
+ ST_GeomFromText('POLYGON((0 30, 15 30, 30 30, 30 0, 0 0, 0 30))'),
ST_MakeEnvelope(12,12,18,18)));
+
+SELECT 6, ST_AsText(
+ ST_RemoveIrrelevantPointsForView(
+ ST_GeomFromText('POLYGON((0 30, 15 30, 30 30, 30 0, 0 0, 0 30))'),
+ ST_MakeEnvelope(12,12,18,18), false));
+
+SELECT 7, ST_AsText(
+ ST_RemoveIrrelevantPointsForView(
+ ST_GeomFromText('POLYGON((0 30, 15 30, 30 30, 30 0, 0 0, 0 30))'),
+ ST_MakeEnvelope(12,12,18,18), true));
diff --git a/regress/core/remove_irrelevant_points_for_view_expected b/regress/core/remove_irrelevant_points_for_view_expected
index 80c617523..e9c82baf0 100644
--- a/regress/core/remove_irrelevant_points_for_view_expected
+++ b/regress/core/remove_irrelevant_points_for_view_expected
@@ -3,3 +3,6 @@
2|LINESTRING EMPTY
3|MULTIPOLYGON Z (((10 10 1,40 10 4,20 20 5,10 20 6,10 10 1)),((10 10 1,20 10 2,20 20 3,10 20 4,10 10 1)))
4|LINESTRING Z EMPTY
+5|POLYGON((0 30,30 30,30 0,0 0,0 30))
+6|POLYGON((0 30,30 30,30 0,0 0,0 30))
+7|POLYGON((15 30,30 0,0 0,15 30))
-----------------------------------------------------------------------
Summary of changes:
doc/reference_editor.xml | 37 +-
liblwgeom/Makefile.in | 6 +-
liblwgeom/cunit/Makefile.in | 1 +
.../cunit/cu_remove_irrelevant_points_for_view.c | 50 +++
liblwgeom/cunit/cu_tester.c | 2 +
.../lwgeom_remove_irrelevant_points_for_view.c | 124 ++-----
... => lwgeom_remove_irrelevant_points_for_view.h} | 16 +-
postgis/lwgeom_remove_irrelevant_points_for_view.c | 392 +--------------------
postgis/postgis.sql.in | 2 +-
postgis/postgis_after_upgrade.sql | 1 +
regress/core/remove_irrelevant_points_for_view.sql | 23 +-
.../remove_irrelevant_points_for_view_expected | 3 +
12 files changed, 159 insertions(+), 498 deletions(-)
create mode 100644 liblwgeom/cunit/cu_remove_irrelevant_points_for_view.c
copy {postgis => liblwgeom}/lwgeom_remove_irrelevant_points_for_view.c (77%)
copy liblwgeom/{lwmcurve.c => lwgeom_remove_irrelevant_points_for_view.h} (71%)
hooks/post-receive
--
PostGIS
More information about the postgis-tickets
mailing list