Infinite Loop when intersecting Polygons (v1.3.4)

[DeveloperUX]

This is a similar issue to: https://github.com/alexbol99/flatten-js/issues/81 (Infinite Loop when Subtracting). Only difference is it now happens when intersecting.

Using version 1.3.4, The intersect polygon operation seems to fail and throw an infinite loop exception.

Sandbox replication: https://codesandbox.io/s/still-tdd-jjzu0y?file=/src/index.js

[alexbol99]

Hi, @DeveloperUX , This issue fixed in v1.3.11, see also PR https://github.com/alexbol99/flatten-js/pull/145 I removed redundant check from segment intersection function, it may help to solve many issues. Please send me more examples of InfiniteLoop error, if you still experience them

[accounts01]

Thanks for the fixes @alexbol99! All but one of my own infinite loop errors were resolved by upgrading from v1.3.8 to v1.3.12. I still have one left in one of my test cases however. Here is code to reproduce it (also available here):

import Flatten from "@flatten-js/core";

const pA = new Flatten.Polygon([
  [ 101.201, 2.97 ],
  [ 101.202, 2.97 ],
  [ 101.202, 2.9706 ],
  [ 101.201, 2.9706 ]
]);

const pB = new Flatten.Polygon([
  [ 101.19,  2.99 ],
  [ 101.22,  2.99 ],
  [ 101.22,  2.97 ],
  [ 101.2,  2.97]
]);

const p0 = Flatten.BooleanOperations.intersect(pA, pB);

I'd love to help but I'm out of my depth in debugging this. Good luck and thank you for this awesome library!

[alexbol99]

Hi, @accounts01 , Indeed, points are too close and probably gives inaccurate intersections. I can suggest you a workaround to scale polygon by 10000 scale factor. And again, two polygons have different orientations, need to reverse one of them.

  let pA_scaled = pA.transform(new Flatten.Matrix().scale(10000,10000))
  let pB_scaled = pB.transform(new Flatten.Matrix().scale(10000,10000))

  if ([...pA_scaled.faces][0].orientation() != [...pB_scaled.faces][0].orientation()) {
      pB_scaled = pB_scaled.reverse();
  }

  const p0 = Flatten.BooleanOperations.intersect(pA_scaled, pB_scaled);

This way you can get an expected result

[accounts01]

Thanks for that @alexbol99. I successfully played around with those 2 ideas when looking for a workaround actually so it's good to have your confirmation. Are you planning on baking in such workarounds within future versions of the library?

[alexbol99]

@accounts01 Actually only scaling is a workaround, setting both polygons to same orientation is a necessary prerequisite. I am not planning to take it into the library. Instead, I am looking for the way to increase accuracy of intersection using, for example, decimals.js library. Any ideas will be very appreciated

[accounts01]

Noted about orientation, thanks! And understood about the direction you're taking. I'm actually a bit fuzzy about why your current DP_TOL-based approach is not sufficient but I am happy to take a look at the relevant code if you can point me towards it :)

[alexbol99]

problem fixed, item closed