@turf/simplify gets stuck in an infinite loop on certain geometries

[senritsu]

Under certain circumstances the turf/simplify function never terminates.

The issue appeared with a geometry resulting from a union of 2 adjacent geometries that left a small gap in between the original polygons.

Full geometry on geojson.io and the problematic ring by itself on geojson.io

This fiddle reproduces the issue using only the problematic ring itself, not the full geometry.

The freeze occurs in the commented part of this function here in simplify/index.js

function simplifyPolygon(coordinates, tolerance, highQuality) {
    return coordinates.map(function (ring) {
        var pts = ring.map(function (coord) {
            return {x: coord[0], y: coord[1]};
        });
        if (pts.length < 4) {
            throw new Error('invalid polygon');
        }
        var simpleRing = simplifyJS(pts, tolerance, highQuality).map(function (coords) {
            return [coords.x, coords.y];
        });
        //remove 1 percent of tolerance until enough points to make a triangle
        while (!checkValidity(simpleRing)) {
            tolerance -= tolerance * 0.01;
            simpleRing = simplifyJS(pts, tolerance, highQuality).map(function (coords) {
                return [coords.x, coords.y];
            });
        }
        if (
            (simpleRing[simpleRing.length - 1][0] !== simpleRing[0][0]) ||
            (simpleRing[simpleRing.length - 1][1] !== simpleRing[0][1])) {
            simpleRing.push(simpleRing[0]);
        }
        return simpleRing;
    });
}

For the given example geometry the simplifyJS call returns an invalid ring (with only 3 points: [[11.662180661499999, 50.1081498005], [11.662192661499999, 50.108041800500004], [11.662180661499999, 50.1081498005]]) no matter how small the tolerance gets. This means the loop never terminates, and the page hangs.

[rowanwins]

Thanks for the detailed writeup @senritsu

[mbullington]

Haven't heavily tested yet, however we ran into this issue in our codebase and swapping for simplify-geojson seems to work.

https://github.com/maxogden/simplify-geojson

[mbullington]

Is this still an issue with v6.2.0? If so I can try to come up with a reproducible case to help.

[rowanwins]

Thanks for the tip @mbullington - I believe it's still an issue. Would be interestenig to run a benchmark against simplify-geojson and the current turf (which is a wrapper around simplify.js)

[hoonzis]

Got this issue today, the problem is still here.

From my point of view simplify-geojson (https://github.com/maxogden/simplify-geojson) is just very tiny wrapper around simplify-geometry (https://github.com/seabre/simplify-geometry) and does not really provide any usefull code. simplify-geometry is an alternative to simplify-js.

So if turfjs wants to switch I would switch directly to simplify-geometry (simplify-geojson does not provide anything).

But the real question is what the code should produce when non-valid linear ring is returned from simplify-js/simplify-geometry and from my point of view it would be much better just to return an invalid polygon, let the user of the library handle it.

[stephkoltun]

I was able to also reproduce this using the following geometry:

{
  type: 'Feature',
  properties: {},
  geometry: { type: 'Polygon', coordinates: [
  [
    [ 4.0881641, 6.8121605 ],
    [ 4.0881639, 6.8121607 ],
    [ 4.0881638, 6.8121608 ],
    [ 4.0881641, 6.8121605 ]
  ]
] }
}

[Marcos-Correia]

I was able to reproduce this issue using the following code

const turf = require("@turf/turf");
const simplifyOptions = { tolerance: 0.00001, highQuality: true };
turf.simplify(
  {
    type: "Feature",
    properties: { },
    geometry: {
      type: "MultiPolygon",
      coordinates: [
        [
            [
                [-10.06762725, -17.428977611],
                [-10.067626613, -17.428977323],
                [-10.067625943, -17.428976957],
                [-10.06762725, -17.428977611]
              ]
            ],
            [
              [
                [-10.067625943, -17.428976957],
                [-10.067599027, -17.428963499],
                [-10.067625941, -17.428976956],
                [-10.067625943, -17.428976957]
              ]
        ],
      ],
    },
  },
  simplifyOptions
);

[pelord]

Any updates?