[postgis-tickets] r16619 - Fix infinite loop in linearization of a big radius small arc

[Sandro Santilli]

Author: strk
Date: 2018-06-15 15:23:30 -0700 (Fri, 15 Jun 2018)
New Revision: 16619

Modified:
   branches/2.4/NEWS
   branches/2.4/liblwgeom/cunit/cu_lwstroke.c
   branches/2.4/liblwgeom/lwstroke.c
Log:
Fix infinite loop in linearization of a big radius small arc

Closes #4058 in 2.4 branch (2.4.5dev)
Includes unit test

Modified: branches/2.4/NEWS
===================================================================
--- branches/2.4/NEWS	2018-06-15 22:16:06 UTC (rev 16618)
+++ branches/2.4/NEWS	2018-06-15 22:23:30 UTC (rev 16619)
@@ -5,6 +5,8 @@
 
   - #4031, Survive to big MaxError tolerances passed to ST_CurveToLine
            (Sandro Santilli)
+  - #4058, Fix infinite loop in linearization of a big radius small arc
+           (Sandro Santilli)
   - #4071, ST_ClusterKMeans crash on NULL/EMPTY fixed (Darafei Praliaskouski)
   - #4079, ensure St_AsMVTGeom outputs CW oriented polygons (Paul Ramsey)
   - #4070, use standard interruption error code on GEOS interruptions

Modified: branches/2.4/liblwgeom/cunit/cu_lwstroke.c
===================================================================
--- branches/2.4/liblwgeom/cunit/cu_lwstroke.c	2018-06-15 22:16:06 UTC (rev 16618)
+++ branches/2.4/liblwgeom/cunit/cu_lwstroke.c	2018-06-15 22:23:30 UTC (rev 16619)
@@ -237,6 +237,39 @@
 
 	lwgeom_free(in);
 
+	/*
+	 * ROBUSTNESS: big radius, small tolerance
+	 * See https://trac.osgeo.org/postgis/ticket/4058
+	 * NOTE: we are really only interested in not enterying
+	 *       an infinite loop here
+	 */
+	toltype = LW_LINEARIZE_TOLERANCE_TYPE_MAX_DEVIATION;
+	in = lwgeom_from_text("CIRCULARSTRING("
+			"2696000.553 1125699.831999999936670, "
+			"2695950.552000000141561 1125749.833000000100583, "
+			"2695865.195999999996275 1125835.189000)");
+	out = lwcurve_linearize(in, 0.0001, toltype, 0);
+	str = lwgeom_to_text(out, 2);
+	ASSERT_STRING_EQUAL(str, "LINESTRING(2696000 1125700,2695866 1125836)");
+	lwfree(str);
+	lwgeom_free(out);
+	out = lwcurve_linearize(in, 0.0001, toltype, LW_LINEARIZE_FLAG_SYMMETRIC);
+	str = lwgeom_to_text(out, 2);
+	ASSERT_STRING_EQUAL(str, "LINESTRING(2696000 1125700,2695866 1125836)");
+	lwfree(str);
+	lwgeom_free(out);
+#ifndef SKIP_TEST_RETAIN_ANGLE
+	out = lwcurve_linearize(in, 0.0001, toltype,
+		LW_LINEARIZE_FLAG_SYMMETRIC |
+		LW_LINEARIZE_FLAG_RETAIN_ANGLE
+	);
+	str = lwgeom_to_text(out, 2);
+	ASSERT_STRING_EQUAL(str, "LINESTRING(2696000 1125700,2695932 1125768,2695866 1125836)");
+	lwfree(str);
+	lwgeom_free(out);
+#endif /* SKIP_TEST_RETAIN_ANGLE */
+	lwgeom_free(in);
+
 	/***********************************************************
 	 *
 	 *  Maximum angle tolerance type

Modified: branches/2.4/liblwgeom/lwstroke.c
===================================================================
--- branches/2.4/liblwgeom/lwstroke.c	2018-06-15 22:16:06 UTC (rev 16618)
+++ branches/2.4/liblwgeom/lwstroke.c	2018-06-15 22:23:30 UTC (rev 16619)
@@ -154,8 +154,13 @@
 
 	LWDEBUG(2, "lwarc_linearize called.");
 
+	LWDEBUGF(2, " curve is CIRCULARSTRING(%.15g %.15f, %.15f %.15f, %.15f %15f)",
+		t1->x, t1->y, t2->x, t2->y, t3->x, t3->y);
+
 	p2_side = lw_segment_side(t1, t3, t2);
 
+	LWDEBUGF(2, " p2 side is %d", p2_side);
+
 	/* Force counterclockwise scan if SYMMETRIC operation is requsested */
 	if ( p2_side == -1 && flags & LW_LINEARIZE_FLAG_SYMMETRIC )
 	{
@@ -232,7 +237,7 @@
 		 *   angle = acos( 1 - tol/radius )
 		 *
 		 * Constraints: 1.0 - tol/radius must be between -1 and 1
-		 * which means tol/radius must be between 0 and 2 times
+		 * which means tol must be between 0 and 2 times
 		 * the radius, which makes sense as you cannot have a
 		 * sagitta bigger than twice the radius!
 		 *
@@ -244,7 +249,15 @@
 			LWDEBUGF(2, "lwarc_linearize: tolerance %g is too big, "
 			            "using arc-max 2 * radius == %g", tol, maxErr);
 		}
-		halfAngle = acos( 1.0 - maxErr / radius );
+		do {
+			halfAngle = acos( 1.0 - maxErr / radius );
+			/* TODO: avoid a loop here, going rather straight to
+			 *       a minimum angle value */
+			if ( halfAngle != 0 ) break;
+			LWDEBUGF(2, "lwarc_linearize: tolerance %g is too small for this arc"
+									" to compute approximation angle, doubling it", maxErr);
+			maxErr *= 2;
+		} while(1);
 		increment = 2 * halfAngle;
 		LWDEBUGF(2, "lwarc_linearize: maxDiff:%g, radius:%g, halfAngle:%g, increment:%g (%g degrees)", tol, radius, halfAngle, increment, increment*180/M_PI);
 	}}