Infinite looping for /* Pass the sweep line over those endpoints */ loop in operation.js

[OliverColeman]

Using version 0.14.3.

I found a way to make the while loop commented with Pass the sweep line over those endpoints in operation.js (around line 62) run infinitely. Or at least until the memory heap is full...

Using my new novel technique (patent pending) it looks like it continuously adds segments to the sweepLine until it falls over. I could get it up to about 1,000,000 segments before it fell over with the default heap size. I'm guessing a million segments is more than expected for the below inputs...

To reproduce perform a union operation over the polygons below.

Additional info: the coordinates were already rounded to a precision of 1 decimal place (because that helped a lot with general stability, as noted previously in a different issue). Rounding them to integers makes the issue noted here go away for the below inputs.

[
      [
          [0,613.9],[14.6,570.6],[45.4,477.6],[61.4,431.4],[62.9,430.1],[65.2,431.1],[65.6,430.8],[66.4,432.6],[68.6,432.4],[69.1,429.4],[69.6,427.5],[73.1,424.6],[77.9,424.9],[80.4,427.4],[123.4,475.9],[157.7,515.6],[163.7,491.6],[179.7,514.5],[219.4,575.9],[383.4,832.4],[477.7,983.3],[474.9,983.1],[470.4,984.4],[465.4,986.4],[469.9,997.1],[475.4,999.1],[467.9,996.4],[464.6,996.9],[465.6,996.9],[456.4,1002.6],[448.6,1004.6],[440.6,1005.6],[438.1,1006.1],[438.1,1007.4],[441.9,1008.4],[459.1,1009.1],[463.9,1007.4],[468.6,1007.9],[473.4,1006.1],[476.1,1004.1],[473.7,1005.9],[483.6,1021.4],[491.1,1029.1],[495.1,1032.1],[495.1,1011.2],[500.5,1019.9],[501.7,1029.6],[526.9,1080],[293.4,1080],[295.1,1077.7],[296.5,1076.8],[304.2,1069.5],[313.8,1055.5],[319.8,1043.2],[323.8,1033.5],[324,1032.5],[327.7,1024.6],[326.2,1012.8],[326.2,1011.5],[324.8,1001.2],[324.5,1000.6],[323.7,994.1],[319.3,987.4],[318.8,986.2],[275.2,917.2],[206.2,816.2],[185.8,785.8],[183.2,782.7],[176.2,772.4],[166,765.8],[165.2,765.2],[151.5,756.5],[151.4,756.4],[134.2,745.4],[117.1,742.8],[116.1,742.5],[102.4,740.6],[87.7,738.4],[63.7,737.4],[38.2,744.9],[20.7,757.4],[0,776],[0,613.9]
      ]
  ],
  
  [
      [
          [0,613.9],[14.6,570.6],[45.4,477.6],[61.2,431.9],[65.2,432.5],[66,431.8],[66.4,432.6],[68.6,432.4],[69.1,429.4],[69.1,429.3],[70.7,428],[77.7,427.5],[154.6,512.4],[155,508.4],[155.6,508.6],[157.4,506.6],[161.9,490.4],[163.4,489.7],[400.6,860],[476.1,982.4],[476.8,982.9],[459.6,981.4],[467.3,990.8],[469.9,997.1],[473.2,998.3],[473.2,998.3],[467.9,996.4],[464.6,996.9],[465.6,996.9],[456.4,1002.6],[451,1004],[443.4,1005.3],[440.6,1005.6],[438.1,1006.1],[438.1,1006.1],[436.5,1006.4],[438.1,1006.8],[438.1,1007.4],[441.9,1008.4],[444,1008.5],[445.5,1008.9],[447.2,1008.6],[459.1,1009.1],[463.9,1007.4],[468.6,1007.9],[468.8,1007.8],[472,1008.4],[471.1,1007],[473.4,1006.1],[476.1,1004.1],[473.7,1005.9],[483.6,1021.4],[491.1,1029.1],[493.9,1031.2],[498.1,1037.9],[496.3,1013.2],[538.1,1080],[298.1,1080],[298.2,1079.4],[310.2,1063.4],[322.7,1044.9],[327.7,1019.4],[325.2,1003.8],[324.8,1001.2],[324.7,1000.9],[323.7,994.9],[319,986.7],[318.8,986.2],[317.8,984.6],[308.2,967.9],[286.8,935.5],[275.2,917.2],[206.2,816.2],[185.8,785.8],[175.8,773.8],[174.3,772.6],[173.7,771.7],[170.9,769.8],[165.2,765.2],[151.5,756.5],[149.9,755.7],[141.7,750.2],[134.7,748.5],[116.1,742.5],[96.5,739.8],[73.8,740.5],[68.4,741.2],[66.7,741.2],[41.2,745.2],[10.2,766.7],[0,774.5],[0,613.9]
      ]
  ],
  
  [
      [
          [0,610.3],[59.8,431.7],[65.2,432.5],[70.7,428],[77.7,427.5],[154.6,512.4],[154.6,512.1],[157.7,515.6],[163.7,491.6],[174.4,506.9],[400.6,860],[476.1,982.4],[476.8,982.9],[459.6,981.4],[472.6,997.4],[498.1,1037.9],[496.3,1012.6],[497.6,1013.9],[500.3,1018.2],[501.7,1029.6],[526.9,1080],[298.1,1080],[298.2,1079.4],[310.2,1063.4],[322.7,1044.9],[325.9,1028.4],[327.7,1024.6],[327.3,1021.5],[327.7,1019.4],[324.2,998.2],[323.7,994.1],[320.2,988.7],[308.2,967.9],[264.2,901.4],[241.7,869.8],[215.7,830.4],[176.2,772.4],[142.4,750.7],[141.7,750.2],[141.6,750.2],[134.2,745.4],[87.7,738.4],[63.7,737.4],[38.2,744.9],[20.7,757.4],[10.9,766.2],[10.2,766.7],[0,774.5],[0,610.3]
      ],
      [
          [436.5,1006.4],[445.5,1008.9],[460.5,1006.4],[472,1008.4],[467.5,1001.4],[460.5,1002.4],[436.5,1006.4]
      ]
  ]

[OliverColeman]

Not sure if this is a related bug but the end result is the same (infinite looping in the same while loop) when performing union operation.

Differences are:

• The input polygons all have integer coordinates.
• The sweepLine segments are not growing infinitely, but the queue size does (again I got it up to size 1,000,000).

See attached file for the set of polygons.
polygon set 3.txt

[OliverColeman]

I made a simple script to generate smallish random polygons. It creates between 2 and 3 polygons, each with between 1 and 3 rings, each with between 3 and 10 points each. The coordinates are integers in the range [0, 100]. The coordinates are random; most polygons will not be simple, but these meet the input specifications for this library so I guess that shouldn't be a problem.

I got it to reproduce the infinite looping issue:

Infinite loop when passing sweep line over endpoints (queue size too big). Please file a bug report.
Polygons were:

  [[[18,66],[17,19],[24,25],[74,58],[0,98],[85,85],[44,71],[84,75],[7,1],[63,69]],[[77,80],[53,76],[86,15],[32,33],[35,73]],[[9,20],[15,50],[65,86],[49,50],[57,58],[11,88],[99,88],[89,82]]]

  [[[62,2],[67,77],[96,26],[11,52],[1,73],[68,54],[65,84],[68,73],[13,10]]]

I'm not sure how to add this to the tests. I went to add a new case in the end-to-end folder but then realised that that requires knowing what the output should be... 🤣

The script created lots of examples that triggered these other errors: "Unable to complete output ring", "Maximum call stack size exceeded", "Unable to find segment". Let me know if it would be useful to create a PR that includes such a script (perhaps with floating point variants as well). I added it to package.json for my own ease of use so could include this in the PR.

The script is:

const mfogel = require('..')

const randInt = (min, max) => Math.round(min + Math.random() * (max - min));
  
while (true) {
  const polys = [];
  for (let pi = 0; pi < 2; pi++) {
    const numRings = randInt(1, 3);
    const poly = [];
    for (let ri = 0; ri < numRings; ri++) {
      const numPoints = randInt(3, 10);
      const ring = [];
      for (let pi = 0; pi < numPoints; pi++) {
        ring.push([ randInt(0, 100), randInt(0, 100) ]);
      }
      poly.push(ring);
    }
    polys.push(poly);
  }
  try {
    mfogel.union(...polys);
  }
  catch (ex) {
    if (ex.message.indexOf("Infinite loop") != -1) console.log("==================");
    console.log(ex.message);
    for (const p of polys) {
      console.log("  " + JSON.stringify(p));
    }
  }
}

[mfogel]

I'm not sure how to add this to the tests. I went to add a new case in the end-to-end folder but then realised that that requires knowing what the output should be... 🤣

yeah gotcha! haha 😂

This, and the other bugs your script have generate are probably related to floating-point math round-off errors. As the test suite in this project has grown and grown it is increasingly hard to fix new issues without breaking some of the existing tests. If you (or anyone else) is able to put together a PR that fixes behavior a new set of failing coordinates without breaking any of the existing tests, I'll happily accept it.

[OliverColeman]

I'd be happy to give it a go, but in the meantime can you accept this PR (for which it's maybe not even possible to write a sensible test)? #97

It seems like it's at least possible for this to be an on-going issue no matter how many tests there are or fixes are applied for them. Being able to catch and gracefully handle an infinite-loop is far better than crashing the node process...