Infinite Loop in `turf.intersect` with Specific Input Data

[fheldtm]

Version Information

• turf.js version: 7.1.0

Description

When using turf.intersect with specific polygon and multipolygon inputs, the function enters an infinite loop. This issue occurs with Turf.js version 7.1.0 and appears to be related to the polygon-clipping.cjs.js library used within Turf.js.

Steps to Reproduce

The issue can be observed with the following code:

import * as turf from "@turf/turf";

const t1 = [
  [
    [126.55856392608325, 34.46272192666609],
    [126.55889007353417, 34.46273185169668],
    [126.55893420916493, 34.46182149433875],
    [126.55860547472139, 34.46181162317049],
    [126.55856392608325, 34.46272192666609],
    [126.55856392608325, 34.46272192666609],
  ],
];

const t2 = [
  [ [ [126.558597, 34.461803], [126.558614, 34.46182], [126.558657, 34.461791], [126.55864, 34.461774], [126.558597, 34.461803], ], ],
  [ [ [126.558599, 34.461789], [126.558602, 34.461822], [126.558657, 34.461819], [126.558654, 34.461786], [126.558599, 34.461789], ], ],
  [ [ [126.558584, 34.461796], [126.558607, 34.461816], [126.558647, 34.461784], [126.558624, 34.461764], [126.558584, 34.461796], ], ],
  [ [ [126.558599, 34.461811], [126.558626, 34.461818], [126.558642, 34.461775], [126.558615, 34.461768], [126.558599, 34.461811], ], ],
  [ [ [126.558597, 34.461808], [126.558621, 34.461819], [126.55865, 34.46178], [126.558626, 34.461769], [126.558597, 34.461808], ], ],
  ...
];

const intersectResult = turf.intersect(
  turf.featureCollection([turf.polygon(t1), turf.multiPolygon(t2)])
);
console.log(intersectResult);

You can see a demonstration of the issue and further details via this JSFiddle.

The function enters an infinite loop. Debugging suggests that the issue arises in the polygon-clipping.cjs.js library, specifically in the operation.run, within sweepLine.process.

The following code snippet from polygon-clipping.cjs.js seems to be where the problem originates:

while (prevSeg === undefined) {
  prevNode = this.tree.prev(prevNode);
  if (prevNode === null) prevSeg = null;
  else if (prevNode.key.consumedBy === undefined) prevSeg = prevNode.key;
}

In this code, prevSeg becomes undefined, causing an infinite loop.

[smallsaucepan]

Thanks for reporting this @fheldtm and tracking down where the problem is occurring. This is a known issue with the polygon-clipping library. We have an item our backlog to replace that library entirely, though can't provide an ETA.

Another way forward would be for polygon-clipping to fix this bug. Have you tried raising this issue with them?

[fheldtm]

Thank you for your response. I haven't tried raising the issue on the polygon-clipping side, I'll take it up with them.

[smallsaucepan]

Thanks @fheldtm. Will leave this issue open, and if we get the library replaced before they fix the bug, will tag you.