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

fheldtm commented 2 weeks ago

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 commented 2 weeks ago

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 commented 2 weeks ago

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 commented 2 weeks ago

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

Turfjs / turf