[postgis-tickets] r16977 - Proper repeated point removal for small polygons
Paul Ramsey
pramsey at cleverelephant.ca
Mon Nov 5 09:57:17 PST 2018
Author: pramsey
Date: 2018-11-05 09:57:16 -0800 (Mon, 05 Nov 2018)
New Revision: 16977
Modified:
branches/2.4/NEWS
branches/2.4/liblwgeom/ptarray.c
Log:
Proper repeated point removal for small polygons
Closes #4136
Modified: branches/2.4/NEWS
===================================================================
--- branches/2.4/NEWS 2018-11-04 19:41:49 UTC (rev 16976)
+++ branches/2.4/NEWS 2018-11-05 17:57:16 UTC (rev 16977)
@@ -14,6 +14,7 @@
- #4215, Use floating point compare in ST_DumpAsPolygons (Darafei Praliaskouski)
- #4059, #4177, Remove use of variable length arrays
- #4216, Return to slicing for bbox access in gserialized
+ - #4136, Proper repeated point removal on small polygons
PostGIS 2.4.5
Modified: branches/2.4/liblwgeom/ptarray.c
===================================================================
--- branches/2.4/liblwgeom/ptarray.c 2018-11-04 19:41:49 UTC (rev 16976)
+++ branches/2.4/liblwgeom/ptarray.c 2018-11-05 17:57:16 UTC (rev 16977)
@@ -1428,73 +1428,117 @@
}
}
+static void
+ptarray_copy_point(POINTARRAY *pa, uint32_t from, uint32_t to)
+{
+ int ndims = FLAGS_NDIMS(pa->flags);
+ switch (ndims)
+ {
+ case 2:
+ {
+ POINT2D *p_from = (POINT2D*)(getPoint_internal(pa, from));
+ POINT2D *p_to = (POINT2D*)(getPoint_internal(pa, to));
+ *p_to = *p_from;
+ return;
+ }
+ case 3:
+ {
+ POINT3D *p_from = (POINT3D*)(getPoint_internal(pa, from));
+ POINT3D *p_to = (POINT3D*)(getPoint_internal(pa, to));
+ *p_to = *p_from;
+ return;
+ }
+ case 4:
+ {
+ POINT4D *p_from = (POINT4D*)(getPoint_internal(pa, from));
+ POINT4D *p_to = (POINT4D*)(getPoint_internal(pa, to));
+ *p_to = *p_from;
+ return;
+ }
+ default:
+ {
+ lwerror("%s: unsupported number of dimensions - %d", __func__, ndims);
+ return;
+ }
+ }
+ return;
+}
-/*
- * Returns a POINTARRAY with consecutive equal points
- * removed. Equality test on all dimensions of input.
- *
- * Always returns a newly allocated object.
- *
- */
-POINTARRAY *
-ptarray_remove_repeated_points_minpoints(const POINTARRAY *in, double tolerance, int minpoints)
+static void
+ptarray_remove_repeated_points_in_place(POINTARRAY *pa, double tolerance, uint32_t min_points)
{
- POINTARRAY* out;
- size_t ptsize;
- size_t ipn, opn;
- const POINT2D *last_point, *this_point;
+ uint32_t i;
double tolsq = tolerance * tolerance;
+ const POINT2D *last = NULL;
+ const POINT2D *pt;
+ uint32_t n_points = pa->npoints;
+ uint32_t n_points_out = 1;
+ size_t pt_size = ptarray_point_size(pa);
- if ( minpoints < 1 ) minpoints = 1;
+ double dsq = FLT_MAX;
- LWDEBUGF(3, "%s called", __func__);
+ /* No-op on short inputs */
+ if ( n_points <= min_points ) return;
- /* Single or zero point arrays can't have duplicates */
- if ( in->npoints < 3 ) return ptarray_clone_deep(in);
+ last = getPoint2d_cp(pa, 0);
+ for (i = 1; i < n_points; i++)
+ {
+ int last_point = (i == n_points-1);
- ptsize = ptarray_point_size(in);
+ /* Look straight into the abyss */
+ pt = getPoint2d_cp(pa, i);
- LWDEBUGF(3, " ptsize: %d", ptsize);
+ /* Don't drop points if we are running short of points */
+ if (n_points + n_points_out > min_points + i)
+ {
+ if (tolerance > 0.0)
+ {
+ /* Only drop points that are within our tolerance */
+ dsq = distance2d_sqr_pt_pt(last, pt);
+ /* Allow any point but the last one to be dropped */
+ if (!last_point && dsq <= tolsq)
+ {
+ continue;
+ }
+ }
+ else
+ {
+ /* At tolerance zero, only skip exact dupes */
+ if (memcmp((char*)pt, (char*)last, pt_size) == 0)
+ continue;
+ }
- /* Allocate enough space for all points */
- out = ptarray_construct(FLAGS_GET_Z(in->flags),
- FLAGS_GET_M(in->flags), in->npoints);
-
- /* Now fill up the actual points (NOTE: could be optimized) */
-
- opn=1;
- /* Keep the first point */
- memcpy(getPoint_internal(out, 0), getPoint_internal(in, 0), ptsize);
- last_point = getPoint2d_cp(in, 0);
- LWDEBUGF(3, " first point copied, out points: %d", opn);
- for ( ipn = 1; ipn < in->npoints; ++ipn)
- {
- this_point = getPoint2d_cp(in, ipn);
- if ( ipn < in->npoints-minpoints+1 || opn >= minpoints ) /* need extra points to hit minponts */
- {
- if (
- (tolerance == 0 && memcmp(getPoint_internal(in, ipn-1), getPoint_internal(in, ipn), ptsize) == 0) || /* exact dupe */
- (tolerance > 0.0 && distance2d_sqr_pt_pt(last_point, this_point) <= tolsq) /* within the removal tolerance */
- ) continue;
+ /* Got to last point, and it's not very different from */
+ /* the point that preceded it. We want to keep the last */
+ /* point, not the second-to-last one, so we pull our write */
+ /* index back one value */
+ if (last_point && n_points_out > 1 && tolerance > 0.0 && dsq <= tolsq)
+ {
+ n_points_out--;
+ }
}
- /*
- * The point is different (see above) from the previous,
- * so we add it to output
- */
- memcpy(getPoint_internal(out, opn++), getPoint_internal(in, ipn), ptsize);
- last_point = this_point;
- LWDEBUGF(3, " Point %d differs from point %d. Out points: %d", ipn, ipn-1, opn);
+ /* Compact all remaining values to front of array */
+ ptarray_copy_point(pa, i, n_points_out++);
+ last = pt;
}
- /* Keep the last point */
- if ( memcmp(last_point, getPoint_internal(in, ipn-1), ptsize) != 0 )
- {
- memcpy(getPoint_internal(out, opn-1), getPoint_internal(in, ipn-1), ptsize);
- }
+ /* Adjust array length */
+ pa->npoints = n_points_out;
+ return;
+}
- LWDEBUGF(3, " in:%d out:%d", out->npoints, opn);
- out->npoints = opn;
-
+/*
+ * Returns a POINTARRAY with consecutive equal points
+ * removed. Equality test on all dimensions of input.
+ *
+ * Always returns a newly allocated object.
+ *
+ */
+POINTARRAY *
+ptarray_remove_repeated_points_minpoints(const POINTARRAY *in, double tolerance, int minpoints)
+{
+ POINTARRAY *out = ptarray_clone_deep(in);
+ ptarray_remove_repeated_points_in_place(out, tolerance, minpoints);
return out;
}
More information about the postgis-tickets
mailing list