turf-mask crashes when creating a mask of 11 or more geometries

[arahansen]

I am finding when I try to create a mask using 11 or more geometries, the function completely locks up and never completes.

From my testing, it does not appear to matter what geometries are used, but I'm consistently reproducing this locking behavior when adding 11 or more geometries.

Here is a link to a repro: https://codesandbox.io/s/mystifying-bush-y8vvv. Just uncomment the commented coordinates in the example.

Full code in example:

import mask from "@turf/mask";

const data = {
  type: "Feature",
  properties: {},
  geometry: {
    type: "Polygon",
    coordinates: [
      // [
      //   [0.721452369148099, 5.590612277391147],
      //   [1.673901522832991, 5.590612277391147],
      //   [1.673901522832991, 5.972978008429339],
      //   [0.721452369148099, 5.972978008429339],
      //   [0.721452369148099, 5.590612277391147]
      // ],
      [
        [1.072354688926774, 3.375169534822903],
        [1.7240304256584942, 3.375169534822903],
        [1.7240304256584942, 3.9588068145192854],
        [1.072354688926774, 3.9588068145192854],
        [1.072354688926774, 3.375169534822903]
      ],
      [
        [1.5402244486276966, 4.258806831814067],
        [2.225319453913679, 4.258806831814067],
        [2.225319453913679, 4.575346500956282],
        [1.5402244486276966, 4.575346500956282],
        [1.5402244486276966, 4.258806831814067]
      ],
      [
        [2.1919001853594673, 1.5221747814434212],
        [3.8127347100589737, 1.5221747814434212],
        [3.8127347100589737, 2.2236001226286777],
        [2.1919001853594673, 2.2236001226286777],
        [2.1919001853594673, 1.5221747814434212]
      ],
      [
        [2.2420290881849705, 5.191355733894466],
        [3.0440915333932512, 5.191355733894466],
        [3.0440915333932512, 5.540719699007936],
        [2.2420290881849705, 5.540719699007936],
        [2.2420290881849705, 5.191355733894466]
      ],
      [
        [2.676479579343335, 3.208348946034526],
        [3.528670927377195, 3.208348946034526],
        [3.528670927377195, 3.7754194143618593],
        [2.676479579343335, 3.7754194143618593],
        [2.676479579343335, 3.208348946034526]
      ],
      [
        [3.762605807233496, 5.823387479016804],
        [4.364152641139713, 5.823387479016804],
        [4.364152641139713, 6.089298006294089],
        [3.762605807233496, 6.089298006294089],
        [3.762605807233496, 5.823387479016804]
      ],
      [
        [3.796025075776054, 4.175484873211606],
        [4.297314104031188, 4.175484873211606],
        [4.297314104031188, 4.408763503506678],
        [3.796025075776054, 4.408763503506678],
        [3.796025075776054, 4.175484873211606]
      ],
      [
        [4.731764595189628, 1.9564240698952464],
        [6.001696800098857, 1.9564240698952464],
        [6.001696800098857, 2.4072559528542996],
        [4.731764595189628, 2.4072559528542996],
        [4.731764595189628, 1.9564240698952464]
      ],
      [
        [4.731764595189628, 3.325126301310877],
        [5.817890823079764, 3.325126301310877],
        [5.817890823079764, 3.892125087778124],
        [4.731764595189628, 3.892125087778124],
        [4.731764595189628, 3.325126301310877]
      ],
      [
        [6.736920708210393, 3.658698052076907],
        [9.009430969630017, 3.658698052076907],
        [9.009430969630017, 2.7578013318391914],
        [6.736920708210393, 2.7578013318391914],
        [6.736920708210393, 3.658698052076907]
      ]
    ]
  }
};

const out = mask(data);

console.log(out);

[arahansen]

This may be the same issue as reported on #1537?

[rowanwins]

Hi @arahansen

Thanks for the report. We're hoping to release a new version of turf following the merge of #1916 which uses a more robust union algorithm which gets used consequently in mask so I suspect that will resolve it. I'll keep this issue open and will recheck after that release.

[arahansen]

I pulled the code from that PR into my local environment and it seems to help quite a bit. Though notably, I also had to also add the fix referenced in this comment.

I can't really tell if this fix is robust enough for all edge cases or not, but it has been working pretty well in my testing so far.

I also added this, which feels pretty hacky but the combination of the two has led to predictable performance:

var search = tree.search({
  minX: bbox[0],
  minY: bbox[1],
  maxX: bbox[2],
  maxY: bbox[3],
})
.filter(node => !removed[node.index])

[Stophface]

Unfortunatly, this is still a problem
#2054

@rowanwins The suggested edit from @arahansen works (for less than 600 geometries). Is there a reason why this fix is not in the repo?