[postgis-tickets] [SCM] PostGIS; Spatial objects for PostgreSQL. branch master updated. bb78dff81d8610dd3bd60efc1618b0109d129f0e

[git at osgeo.org]

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; Spatial objects for PostgreSQL.".

The branch, master has been updated
       via  bb78dff81d8610dd3bd60efc1618b0109d129f0e (commit)
      from  53af04cf6267b6b7e9d3ebfe53920a8795566c8a (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 bb78dff81d8610dd3bd60efc1618b0109d129f0e
Author: Darafei Praliaskouski <me at komzpa.net>
Date:   Thu Oct 31 08:23:36 2019 +0300

    ST_Simplify: O(N) simplification for tolerance=0
    
    References #4149

diff --git a/NEWS b/NEWS
index 36c7083..478e3ce 100644
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,7 @@ PostGIS 3.1.0
 * Enhancements *
   - #4539, Unify libm includes (Raúl Marín)
   - #4569, Allow unknown SRID geometry insertion into typmod SRID column (Paul Ramsey)
+  - #4149, ST_Simplify(geom, 0) is now O(N) (Darafei Praliaskouski)
 
 * Bug fixes *
   - #4544, Fix leak when parsing a WKT geometry_list (Raúl Marín)
diff --git a/liblwgeom/ptarray.c b/liblwgeom/ptarray.c
index 6f72476..9894336 100644
--- a/liblwgeom/ptarray.c
+++ b/liblwgeom/ptarray.c
@@ -1583,6 +1583,49 @@ ptarray_dp_findsplit_in_place(const POINTARRAY *pts, uint32_t it_first, uint32_t
 	return split;
 }
 
+/* O(N) simplification for tolearnce = 0 */
+static void
+ptarray_simplify_in_place_tolerance0(POINTARRAY *pa)
+{
+	uint32_t kept_it = 0;
+	uint32_t last_it = pa->npoints - 1;
+	const POINT2D *kept_pt = getPoint2d_cp(pa, 0);
+	const size_t pt_size = ptarray_point_size(pa);
+
+	for (uint32_t i = 1; i < last_it; i++)
+	{
+		const POINT2D *curr_pt = getPoint2d_cp(pa, i);
+		const POINT2D *next_pt = getPoint2d_cp(pa, i + 1);
+
+		double ba_x = next_pt->x - kept_pt->x;
+		double ba_y = next_pt->y - kept_pt->y;
+		double ab_length_sqr = ba_x * ba_x + ba_y * ba_y;
+
+		double ca_x = curr_pt->x - kept_pt->x;
+		double ca_y = curr_pt->y - kept_pt->y;
+		double dot_ac_ab = ca_x * ba_x + ca_y * ba_y;
+		double s_numerator = ca_x * ba_y - ca_y * ba_x;
+
+		if (dot_ac_ab < 0.0 || dot_ac_ab > ab_length_sqr || s_numerator != 0)
+		{
+			kept_it++;
+			kept_pt = curr_pt;
+			if (kept_it != i)
+				memcpy(pa->serialized_pointlist + pt_size * kept_it,
+				       pa->serialized_pointlist + pt_size * i,
+				       pt_size);
+		}
+	}
+
+	/* Append last point */
+	kept_it++;
+	if (kept_it != last_it)
+		memcpy(pa->serialized_pointlist + pt_size * kept_it,
+		       pa->serialized_pointlist + pt_size * last_it,
+		       pt_size);
+	pa->npoints = kept_it + 1;
+}
+
 void
 ptarray_simplify_in_place(POINTARRAY *pa, double tolerance, uint32_t minpts)
 {
@@ -1590,6 +1633,12 @@ ptarray_simplify_in_place(POINTARRAY *pa, double tolerance, uint32_t minpts)
 	if (pa->npoints < 3 || pa->npoints <= minpts)
 		return;
 
+	if (tolerance == 0 && minpts <= 2)
+	{
+		ptarray_simplify_in_place_tolerance0(pa);
+		return;
+	}
+
 	/* We use this array to keep track of the points we are keeping, so
 	 * we store just TRUE / FALSE in their position */
 	uint8_t *kept_points = lwalloc(sizeof(uint8_t) * pa->npoints);

-----------------------------------------------------------------------

Summary of changes:
 NEWS                |  1 +
 liblwgeom/ptarray.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+)


hooks/post-receive
-- 
PostGIS; Spatial objects for PostgreSQL.