found non-noded intersection between LINESTRING

[ajmas]

I ran into the following error, when calling turf.intersect(poly, point1)

"found non-noded intersection between LINESTRING ( 180 -84.71338, -179.942499 -84.721443 ) and LINESTRING ( -143.107718 -85.040752, -142.892279 -84.570497 ) [ (-142.96105271343765, -84.720614586011) ]"

A bit of background:

I am using a combination of turf and turf-multipolygon, with the geojson outline at http://openlayers.org/en/v3.8.2/examples/data/geojson/countries.geojson

My code looks something as follows:

features = countryOutlines.features;
for (i=0; i<features.length; i++) {

    if ( features[i].geometry.type === 'MultiPolygon' ) {
        for (j=0; j<features[i].geometry.coordinates.length; j++) {
            poly = turf.polygon(features[i].geometry.coordinates[j]);
            try {
                if (turf.intersect(poly, point1)) {
                    return features[i].properties.name;
                }                             
            } catch (e) {
                console.error(e, features[i].id, j);
            }
        }
     } else {
        poly = turf.polygon(features[i].geometry.coordinates[0]); 

        if (turf.intersect(poly, point1)) {
            return features[i].properties.name;
        }        
     }
}

The issue happens with the entry for Antartica (ATA). Should the intersect function be dealing with situation or is there a function that would 'correct' the data for this situation?

BTW I did modify turf-multipolygon for use in browser based JS:

turf.multipolygon = function(coordinates, properties) {
  if (!coordinates) {
    throw new Error('No coordinates passed');
  }
  return {
    "type": "Feature",
    "geometry": {
      "type": "MultiPolygon",
      "coordinates": coordinates
    },
    "properties": properties || {}
  };
};

[rowanwins]

Hi @ajmas

Turf.intersect is designed to work with two polygons so I'm a bit confused why you're calling turf.intersect(poly, point1) ...

It's a bit hard to work out what else might be going wrong with your code from your description, you might be able to use something like Turfjs.party or jsfiddle to provide a better idea of what you've got so far.

Thanks,
Rowan

[sainsb]

I'm experiencing the same error with 2 polygons. Fairly simple ones at that...
https://jsfiddle.net/hc5v73tq/2/

It appears to happen when coordinates in a polygon are so close together so as to appear identical. In the above fiddle, it's the second to last and last one (of the more complex polygon (f1)).

Maybe I need to simplify first or something...

[ajmas]

My use case was to taking an existing geojson data source, which provides country outlines. I then wanted to find in which polygon a given coordinate existed, so I could derive which country was associated with the coordinate.

Except for where the error happens, get intersection of point and polygon does work.

BTW used the turf.interesect() function based on recommendations elsewhere on the web, such as here:

http://gis.stackexchange.com/questions/147829/how-to-check-for-geometry-intersection-point-in-polygon-using-openlayers3

[ajmas]

For my specific case, switching to turf.inside() resolved the issue.

I decided to put together a test case using purely polygons and I still see the issue. Should Turf be able to handle the issue in the geojson (I see Antartica has a line crossing issue)?

Have attached test-case, showing polygon issue with turf.intersect()

Issue 297 Testcase.zip

[rowanwins]

Hi @sainsb , i've taken a look at your polys and indeed it's to do with that second last point which is ridiculously close to the last point (eg less than 1mm). Turf intersect uses JSTS under the hood which is based on JTS which where the geometry validation is coming from.If you run a topology check in QGIS as well you get error (see the topology check on that poly from QGIS in this image). Perhaps you could reduce the complexity of your polygons by using something like turf-simplify (a bit annoying I know)?

Hi @ajmas the Antarctica poly is indeed also causing issues, if you remove that poly from the dataset then no issues are thrown.

[fplgusmao]

This is happening to me but for a different case. The cause is on the turf.intersect. I'm making an hex-grid, with 0.5km-sized hexagons, then cycling through it , searching for intersections with a given set of polygons, resulting a kind-of heatmap/hexagonal binning, as you can see in this image:

I first noticed the error was being thrown right when the first hexagon of the grid did:

var intersection = turf.intersect(hex, polygon)

I knew the hex wasn't supposed to intersect the polygon, and thought the error derived from there, or maybe because the intersection was too small, promptly making a catch clause and dealing with the problem by making intersection = undefined. However, I noticed that it was happening where the given hexagon was supposed to intersect ALL the provided polygons, and intersect them fully, which discarded the possibility of the intersection being too small.

I have two plunkers showing this. The first plunker shows my initial handling, where I handled the error by assuming it was a non-existent intersection. The second plunker, shows what happens when I decide to skip the whole polygon because of the error (I don't count it in the normalisation of the total intersection). (Plunkers not available anymore)

Am I using turf.intersect in a wrong way? or is it related to how hexagons are implemented? (NOTE: the algorithm is yet to be optimised, so it takes around 40 seconds for the results to show in the preview of the plunker)

UPDATE: the problem was only happening with some strange polygons. However I wonder if the error could be more explicit, or if the intersect could even support these kind of polygons. Heres a detail of one the strange shapes:

[morganherlocker]

the problem was only happening with some strange polygons.

non-noded intersection

The non-noded intersection error is thrown when self-intersecting polygons are detected. These polygons are invalid, since the interiors & exteriors of the hulls are ambiguous.

[fplgusmao]

@morganherlocker Is there anyway to test if a given polygon is a self-intersecting polygon beforehand?

That way, I could test it and try to create an approximate convex polygon before the intersection.

[morganherlocker]

@fplgusmao turf-kinks finds all self intersections in a Polygon.

[fplgusmao]

@morganherlocker Cool! Thank you very much

[chriswhong]

I also experienced this "found non-noded intersection between LINESTRING..." error with two polygons that passed ST_IsValid() in postGIS. I got around it by doing a turf.buffer on the offendiong polygons before calling turf.intersect, but I am not sure what the performance implications are of this method

[sainsb]

This can also result from passing in MultiPolygon geometry (with no self-intersections)

[panuhorsmalahti]

I'm seeing this relatively often. The cause for me is that the underlying library, JSTS, loses some coordinate accuracy when converting to and back from JSTS's own format. After this apparently two "identical" coordinates end up being slightly different:

found non-noded intersection between LINESTRING ( 26.354054995086468 60.814164001413886, 26.354071880268343 60.81332589477252 ) and LINESTRING ( 26.354071880274574 60.81332589446338, 26.354054995088205 60.81416400132764 ) [ (26.354056376031796, 60.81409545732238, undefined) ]

I got the error from dissolve. My workaround is to specify a different PrecisionModel from the default one used. I had to fork turf-dissolve and turf-union for this (note the different API for union).

            try {
                featureCollection.features[i] = union([polygon, matchFeature]);
            } catch (error) {
                if (error && error.message && error.message.includes("found non-noded intersection between")) {
                    const precisionModel = new jsts.geom.PrecisionModel(jsts.geom.PrecisionModel.FIXED);
                    const geometryFactory = new jsts.geom.GeometryFactory(precisionModel);
                    featureCollection.features[i] = union([polygon, matchFeature], geometryFactory);
                } else {
                    throw error;
                }
            }

[njriordan]

I had a similar issue and found that using turf.truncate() on the geometries solved the problem. This might be useful for some people if their geometries currently have an unnecessary level of precision.

[DenisCarriere]

👍 Thanks for the update @njriordan , agreed that using @turf/truncate or @turf/clean-coords might solve some precision level issues.

[mfogel]

I'm getting this found non-noded intersection between LINESTRING error using @turf/difference v5.1.5 with valid polygons (pass geojsonhint, and have no kinks).

I wrote up a test case demonstrating the error, only to find that it is already fixed on #1225. Looking forward to that getting merged in!

[fredmilhau]

Hi, I'm also experiencing the same error (turf 5.1.6), with 2 simple polygons.

https://stackblitz.com/edit/turf-non-noded-intersection-error

[kgloveyou]

Hi, I'm also experiencing the same error (turf 5.1.6), with 2 simple polygons.

https://stackblitz.com/edit/turf-non-noded-intersection-error
I have gotten the same error. Did you solve this ?

[ajmas]

@fredmilhau I resolved it by switching the method I used. See: #297 (comment)

[1994sunshine]

use turf.simplify.see: #463