Turf simplify hangs on this input.

[jfgorski]

Running v4.6.0, this input caused simplify to hang the nodejs process in a compute loop:

# coffeescript
ts=require '@turf/simplify'
ts {"type":"Feature","geometry":{"coordinates":[[[[0,90],[0,90],[0,90],[0,90],[0,90],[0,90],[0,90],[0,90],[0,90],[0,90],[0,90]]]],"type":"MultiPolygon"},"properties":{}},1

(I realize it's unusual input.)

[jfgorski]

Some other troublesome inputs:

{"coordinates":[[[[0,1],[0,2],[0,3],[0,2.5],[0,1]]]],"type":"MultiPolygon"}
{"coordinates":[[[[0,1],[0,1],[1,2],[0,1]]]],"type":"MultiPolygon"}

[rowanwins]

Hey @jfgorski

Thanks for the report. Yeah obviously the crazy input is going to be problematic however we should be able to find a way to at least throw an error rather than just killing node. We'll have a think and report back.

[stebogit]

@rowanwins @DenisCarriere
It seems here we are actually dealing with invalid geometries, which I believe should not be handled by Turf.
Reading the PostGIS documentation about validity I like their approach, which I find quite reasonable:

PostGIS is compliant with the Open Geospatial Consortium’s (OGC) OpenGIS Specifications. As such, many PostGIS methods require, or more accurately, assume that geometries that are operated on are both simple and valid. For example, it does not make sense to calculate the area of a polygon that has a hole defined outside of the polygon, or to construct a polygon from a non-simple boundary line.

By default, PostGIS does not apply this validity check on geometry input, because testing for validity needs lots of CPU time for complex geometries, especially polygons. If you do not trust your data sources, you can manually enforce such a check

Having said that, I think we should implement a @turf/boolean-valid so user can apply it when/if they deem necessary.
I'll be happy to start working on it.

[jfgorski]

A boolean-valid makes sense and would be helpful. Eliminating the infinite loop in invalid cases would be nice, but I think a reasonable alternative is to have a cautionary note in the documentation to run boolean-valid if necessary to avoid the infinite loop. Anything to avoid the infinite loop surprise ...

[rowanwins]

Thanks for those thoughts and doco @stebogit , I agree with your proposal. I also think it would be good to have some of these principles nailed down, applied consistently, and documented.

[DenisCarriere]

Great PostGIS reference @stebogit, I agree that we shouldn't be testing invalid geometries, but include that as a separate module.

[stebogit]

Is this still a bug then?
Maybe a wontfix?

[DenisCarriere]

@jfgorski I've tried to create MultiPolygon's using your coordinates and they are all "invalid", so unless you can provide valid geometries then this wouldn't be fixed.

simplify(multiPolygon([[[[0, 90], [0, 90], [0, 90], [0, 90], [0, 90], [0, 90], [0, 90], [0, 90], [0, 90], [0, 90], [0, 90]]]]));
simplify(multiPolygon([[[[0, 1], [0, 2], [0, 3], [0, 2.5], [0, 1]]]]));
simplify(multiPolygon([[[[0, 1], [0, 1], [1, 2], [0, 1]]]]));

All of them throws this error:

/Users/mac/Github/turf/packages/turf-simplify/index.js:132
            throw new Error('invalid polygon');
            ^

Error: invalid polygon
    at /Users/mac/Github/turf/packages/turf-simplify/index.js:132:19
    at Array.map (native)
    at simplifyPolygon (/Users/mac/Github/turf/packages/turf-simplify/index.js:127:24)
    at /Users/mac/Github/turf/packages/turf-simplify/index.js:92:20
    at Array.map (native)
    at simplify (/Users/mac/Github/turf/packages/turf-simplify/index.js:91:47)
    at /Users/mac/Github/turf/packages/turf-simplify/index.js:54:9
    at geomEach (/Users/mac/Github/turf/packages/turf-meta/index.js:460:17)
    at module.exports (/Users/mac/Github/turf/packages/turf-simplify/index.js:53:5)
    at Test.t (/Users/mac/Github/turf/packages/turf-simplify/test.js:80:14)
npm ERR! Test failed.  See above for more details.

@jfgorski Please don't hesitate to re-open this issue if you can replicate these errors with valid geometries using @turf/helpers.

[DenisCarriere]

@stebogit Actually the error is coming from simplifyPolygon.

/**
 * Simplifies the coordinates of a Polygon with simplify-js
 *
 * @private
 * @param {Array<number>} coordinates to be processed
 * @param {number} tolerance simplification tolerance
 * @param {boolean} highQuality whether or not to spend more time to create a higher-quality
 * @returns {Array<Array<Array<number>>>} simplified coords
 */
function simplifyPolygon(coordinates, tolerance, highQuality) {
    console.log(coordinates, coordinates.length);
    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');
        }

When it applies cleanCoords it goes from:

[ [ [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ],
    [ 0, 90 ] ] ]

To:

[ [ [ 0, 90 ], [ 0, 90 ] ] ]

However... it seems like the latest release doesn't "hang" it simply returns an error saying invalid polygon.

@stebogit Was this a fix we did post v4.6.0? Maybe this will get solved in the next release because my NodeJS isn't hanging.

[jfgorski]

@DenisCarriere Here's another try I made that passed the multiPolygon helper but still exhibits the hanging.

$ node --version
v6.11.2
$ npm list|grep @turf
├── @turf/helpers@4.6.0
├─┬ @turf/simplify@4.6.0
$ node
> ts=require('@turf/simplify')
[Function]
> th=require('@turf/helpers')
{ feature: [Function: feature],
  geometry: [Function: geometry],
  featureCollection: [Function: featureCollection],
  geometryCollection: [Function: geometryCollection],
  point: [Function: point],
  multiPoint: [Function: multiPoint],
  lineString: [Function: lineString],
  multiLineString: [Function: multiLineString],
  polygon: [Function: polygon],
  multiPolygon: [Function: multiPolygon],
  radiansToDistance: [Function: radiansToDistance],
  distanceToRadians: [Function: distanceToRadians],
  distanceToDegrees: [Function: distanceToDegrees],
  radians2degrees: [Function: radians2degrees],
  degrees2radians: [Function: degrees2radians],
  bearingToAngle: [Function: bearingToAngle],
  convertDistance: [Function: convertDistance],
  convertArea: [Function: convertArea],
  round: [Function: round] }
> mp=th.multiPolygon([[[[0,1],[0,2],[0,3],[0,2.5],[0,1]]]])
{ type: 'Feature',
  properties: {},
  geometry: { type: 'MultiPolygon', coordinates: [ [Object] ] } }
> ts(mp,1)

and then node got stuck using CPU. Makes sense that it could be these versions 4.6.0 without the fix.

[stebogit]

Was this a fix we did post v4.6.0? Maybe this will get solved in the next release because my NodeJS isn't hanging.

@DenisCarriere yes: #903
Also on my computer it returns invalid polygon.

[mickeyjohn]

My case with version 6.5.0, it hangs when 'invalid polygon' exception has happened twice. I think you all agreed that this is not the expected output. Any ideas on how to fix this? Or Could you suggest alternatives which does not hang?

Thanks.