turf.intersect(geometry 1, geometry 2) gets stuck for endless time

[usmanijaaz]

• The version of Turf using: 6.5.0

I am using a 3rd party API to get geometry data based on a bounding box and that data consists of multi polygons with rings having hundreds of coordinates. Everything works fine in such cases, I recently came across an example where API response had multi polygon with 1 or 2 rings having 150k+ coordinates (geometry feature of some river or a forest) and that feature had 1000+ rings.

Taking intersection of that multi polygon with my site polygon using turf.intersect(incomingFeature, sitePolygon) gets stuck and never complete its execution.

What I have done for now:
I have split incoming feature rings in two separate multi polygons, one with rings having coordinates greater than 10k and the other one with rings having coordinates less than 10k. turf.intersect seems to be working fine in this way, which seems weird. Why can't it process the multipolygon without splitting the rings ?

//Code snippet
//make polygon from incoming features
let incomingMultiPolygon = returnedFeatures[i].geometry.rings.filter(x => x.length <= 10000);
if (incomingMultiPolygon.length > 0)
  this.checkIntersection(incomingMultiPolygon, siteBoundary);

incomingMultiPolygon = returnedFeatures[i].geometry.rings.filter(x => x.length > 10000);
if (incomingMultiPolygon.length > 0) 
  this.checkIntersection(incomingMultiPolygon, siteBoundary);

//this.checkIntersection calls turf.intersect(incomingMultiPolygon, siteBoundary) and do something with the result.

[smallsaucepan]

Hi @usmanijaaz . Can you please attach geojson files of returnedFeatures and siteBoundary? Also, have you commented out other code in your checkIntersection function to eliminate other potential causes?

[usmanijaaz]

Hi @usmanijaaz . Can you please attach geojson files of returnedFeatures and siteBoundary? Also, have you commented out other code in your checkIntersection function to eliminate other potential causes?

Hi @smallsaucepan , thanks for your response. I am attaching the siteBoundary file you requested and I'm also attaching a screenshot for your convenience to understand returnedFeatures data as I am not able to upload file due to its size. As you can see in the screenshot, there are multiple rings in geometry and 1st ring contains 155036 coordinates.

And the first line of code in checkIntersection function is if (turf.intersect(ourSiteBoundary, polygonFromReturnedFeatures)) , the code freezes here and never move past this line.

siteboundary.json

[smallsaucepan]

Thanks @usmanijaaz . There will limitations in any system, especially when large datasets are involved. Ideally though we'd be able to handle those gracefully. Or at least add something in the documentation to set user expectations.

Do you have other options for providing returnedFeatures geojson as well e.g. dropbox? That's going to be key in reproducing and potentially narrowing down the cause.

[usmanijaaz]

Thanks @usmanijaaz . There will limitations in any system, especially when large datasets are involved. Ideally though we'd be able to handle those gracefully. Or at least add something in the documentation to set user expectations.

Do you have other options for providing returnedFeatures geojson as well e.g. dropbox? That's going to be key in reproducing and potentially narrowing down the cause.

Hi @smallsaucepan,
Sure thing, here is a link to a drive folder where I have uploaded the file for you: https://drive.google.com/file/d/1jhG28WNTWb6R9qznLfvTjYcSPyT-sdfc/view?usp=drive_link

[smallsaucepan]

Thanks @usmanijaaz . Investigated and found a safety check in the polygon-clipping library that is meant to stop infinite loops. The behaviour wasn't exactly what you were seeing (the code threw an error, rather than hanging), however it sounds too similar not to be related.

Taking the returnedFeatures json you provided, I loaded different combinations of the rings (big rings, small rings, all rings) and tried calling intersect. Big rings and small rings by themselves worked ok, but all rings together produced this error after a few seconds:

turf-issue-2601/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1726
          throw new Error("Infinite loop when putting segment endpoints in a priority queue " + "(queue size too big).");
                ^
Error: Infinite loop when putting segment endpoints in a priority queue (queue size too big).

Looking further in to that, polygon-clipping has some code that says "if I need to run this loop more than a million times I'm probably in an infinite loop so abort". Turns out you can also hit this threshold with a big enough polygon!

polygon-clipping lets you override this env.POLYGON_CLIPPING_MAX_QUEUE_SIZE so from the command line you could try:

$ POLYGON_CLIPPING_MAX_QUEUE_SIZE=10000000 npx tsx ./test.ts

(that's 10 million)

Doing this allowed intersect to run through all the rings at once and produce the below polygon in about 5 seconds.

Give that a try and see if it helps or changes the situation.

[usmanijaaz]

Thanks @usmanijaaz . Investigated and found a safety check in the polygon-clipping library that is meant to stop infinite loops. The behaviour wasn't exactly what you were seeing (the code threw an error, rather than hanging), however it sounds too similar not to be related.

Taking the returnedFeatures json you provided, I loaded different combinations of the rings (big rings, small rings, all rings) and tried calling intersect. Big rings and small rings by themselves worked ok, but all rings together produced this error after a few seconds:

turf-issue-2601/node_modules/polygon-clipping/dist/polygon-clipping.cjs.js:1726
          throw new Error("Infinite loop when putting segment endpoints in a priority queue " + "(queue size too big).");
                ^
Error: Infinite loop when putting segment endpoints in a priority queue (queue size too big).

Looking further in to that, polygon-clipping has some code that says "if I need to run this loop more than a million times I'm probably in an infinite loop so abort". Turns out you can also hit this threshold with a big enough polygon!

polygon-clipping lets you override this env.POLYGON_CLIPPING_MAX_QUEUE_SIZE so from the command line you could try:

$ POLYGON_CLIPPING_MAX_QUEUE_SIZE=10000000 npx tsx ./test.ts

(that's 10 million)

Doing this allowed intersect to run through all the rings at once and produce the below polygon in about 5 seconds.

Give that a try and see if it helps or changes the situation.

Oh got it @smallsaucepan, thanks a lot for looking into this. I have currently deployed the solution where i split rings into two categories and process them separately and it is working fine for me.
However, I was wondering that I am using turf's npm package in my angular app, How can i set an environment variable for polygon_clipping library in my application.

[smallsaucepan]

Happy to help!

Hmm, setting it via Angular in the browser sounds a bit fiddly. Maybe take a look at this for some ideas - https://stackoverflow.com/a/46269080/3606644

Also note that if you increase that value and then get into the type of infinite loop the code is checking for, it will take 10x as long / use 10x as much memory before the failsafe activates.

Best of luck!

[smallsaucepan]

FYI @usmanijaaz we're almost finished upgrading to a different clipping library. Re-ran your data through that, and while it takes several seconds it produces an identical result to the POLYGON_CLIPPING_MAX_QUEUE_SIZE=10000000 workaround.

This fix should hopefully be available soon in Turf v7.2.0 or 7.3.0