More infinite looping in CircularLinkedList (for v1.2.10)

[OliverColeman]

Some examples: https://codesandbox.io/s/flatten-js-infinite-loop-181sh?file=/src/index.ts

[alexbol99]

Still working on it

[jovankrajevski]

Do you have any suggestions on which types of polygons we should be avoiding so that we can avoid the infinite looping while you are working on this issue?

[OliverColeman]

@alexbol99 Any chance of getting PR #56 merged? I'm currently using that branch on a webserver to avoid this bug crashing the webserver...

@jovankrajevski In case it's useful: you can use the branch for PR #56 from npm with npm i OliverColeman/flatten-js#preventinfiniteloop. Then you can catch the exception thrown when an infinite loops seems to be occurring and handle it gracefully.

[jovankrajevski]

I would prefer to see PR #56 merged tbh. imo it is better to have an error thrown, so that we could fall back on some other heuristic, than have the browser/server looping forever.

[alexbol99]

I would not fix it in this way. The reason of infinite loop is illegal merge of two polygon caused by numeric errors. I know how to prevent it in the way that it throw error before it comes to infinite loop. It just takes me some time to implement. Sorry for delay.

[alexbol99]

@jovankrajevski

Do you have any suggestions on which types of polygons we should be avoiding so that we can avoid the infinite looping while you are working on this issue?

Operation is stable when polygon has no almost zero length edges. Intersection between two edges when one of them is big and other has length closed to zero is numerically unstable. Try to filter your polygons from tiny edges that have no meaning, and the result will be fine.

[jovankrajevski]

@alexbol99 thanks. I actually solved my problem by just casting the coordinates to ints, but I will make sure that I do not have edges with length < 1. I am not sure if you are aware that this bug happens sometimes with floating point coordinates, and not just with edges that are really small, so I just wanted to point that out.

[alexbol99]

@jovankrajevski , @OliverColeman
Ok, I added infinite loop detection using infamous "turtle and rabbit" algorithm.
It throws an "Infinite loop" error if additional loop detected in the chain of edges supposed to form face.
Fix available in the version v1.2.11.
Best,
Alex

[OliverColeman]

Awesome, thanks for this :). I am wondering if it would be even better to put that code into CircularLinkedList.js rather than face.js? At the moment face.js is the only code that uses CircularLinkedList, but if in the future some other code uses it and causes an infinite loop, it would still be caught.