From 8ce453e6dd82fb9f4ff4e7ab77c223d7bc4d53f0 Mon Sep 17 00:00:00 2001 From: Sandro Santilli Date: Fri, 15 Jun 2018 22:23:30 +0000 Subject: [PATCH] Fix infinite loop in linearization of a big radius small arc Closes #4058 in 2.4 branch (2.4.5dev) Includes unit test git-svn-id: http://svn.osgeo.org/postgis/branches/2.4@16619 b70326c6-7e19-0410-871a-916f4a2858ee --- NEWS | 2 ++ liblwgeom/cunit/cu_lwstroke.c | 33 +++++++++++++++++++++++++++++++++ liblwgeom/lwstroke.c | 17 +++++++++++++++-- 3 files changed, 50 insertions(+), 2 deletions(-) diff --git a/NEWS b/NEWS index ed852e29c..b29935aaf 100644 --- a/NEWS +++ b/NEWS @@ -5,6 +5,8 @@ PostGIS 2.4.5 - #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 diff --git a/liblwgeom/cunit/cu_lwstroke.c b/liblwgeom/cunit/cu_lwstroke.c index c43f5fdb4..c151c821c 100644 --- a/liblwgeom/cunit/cu_lwstroke.c +++ b/liblwgeom/cunit/cu_lwstroke.c @@ -237,6 +237,39 @@ static void test_lwcurve_linearize(void) 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 diff --git a/liblwgeom/lwstroke.c b/liblwgeom/lwstroke.c index a89f0c4c1..71fe74f6f 100644 --- a/liblwgeom/lwstroke.c +++ b/liblwgeom/lwstroke.c @@ -154,8 +154,13 @@ lwarc_linearize(POINTARRAY *to, 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 @@ lwarc_linearize(POINTARRAY *to, * 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 @@ lwarc_linearize(POINTARRAY *to, 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); }} -- 2.50.1