Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
senritsu opened this issue Nov 11, 2019 · 10 comments · May be fixed by #2830
Open

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

senritsu opened this issue Nov 11, 2019 · 10 comments · May be fixed by #2830
Assignees

Comments

@senritsu
Copy link
Contributor

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 rowanwins added the bug label Jan 2, 2020
@rowanwins
Copy link
Member

Thanks for the detailed writeup @senritsu

@mbullington
Copy link
Contributor

mbullington commented Jan 9, 2020

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
Copy link
Contributor

mbullington commented Jun 12, 2020

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

@rowanwins
Copy link
Member

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
Copy link

hoonzis commented Nov 10, 2020

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
Copy link

stephkoltun commented Oct 25, 2021

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
Copy link

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
Copy link

pelord commented Apr 19, 2024

Any updates?

@petertoth-dev
Copy link

petertoth-dev commented May 17, 2024

same for me, unfortunately! Maybe MultiPolygons are the issue? At least for me it loops on a MultiPolygon too .
update: nope, sometimes it works with MultiPolygons, so it must be something else

@rowanwins could you take a look?

@smallsaucepan
Copy link
Member

Suspect this might be related to issues in cleanCoords. Just waiting for a couple of other PRs to merge first.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

10 participants