infinite loop during intersection

[levskaya]

martinez.intersection([[-24.820450799231946, 81.60424965743837],[-66.98439939287994, 65.9251157774066],[-67.17837257682962, 65.5743714314538],[-23.564139586577383, 84.46172863817043],[-35.3782801119441, 162.91715665949576],[-37.42674770001716, 159.79423125392117], [-24.820450799231946, 81.60424965743837]], [[-23.564139586577383, 84.46172863817043],[-67.17837257682962, 65.5743714314538],[-24.85941638876879, 26.87535085545798],[-23.564139586577383, 84.46172863817043]])

causes an infinite loop inside 'subdivide' function due to possibleIntersection not handling the case of a self-intersecting polygon. There's even a commented-out line that when reactivated seems to solve this issue.

// that disallows self-intersecting polygons,
// did cost us half a day, so I'll leave it
// out of respect
//if (se1.isSubject === se2.isSubject) return;

This loop badly hangs the browser when it's hit.

[levskaya]

Hmm, even with that uncommented I'm still getting infinite loops on other geometry. e.g.

martinez.intersection([[-36.24781525291243, 28.240373566184424],[-5.276960407892941, 69.94177839542625],[-10.689741059141994, 70.14384722952903],[10.59203885271558, 26.42123891266195],[9.619931709858415, 41.63423842491253],[-61.1981865514771, 44.346933376701756], [-36.24781525291243, 28.240373566184424]], [[-5.276960407892941, 69.94177839542625],[-36.24781525291243, 28.240373566184424],[-28.04892431686142, 27.43688541864268],[-5.276960407892941, 69.94177839542625]])

[w8r]

that line doesn't have much to do with it. As the comment suggests, it just stops at the first self-intersection

[Wotuu]

I don't know why or how, but I came here from https://github.com/w8r/polygon-offset/issues/14 since the infinite loop seems to be originating from this library, but commenting that line out seems to fix the issue. For what I use this library it's okay that some results may be wonky so I'll take any side effects in stride. Still, if there's some sort of proper fix for this I'd be happy to know. For now I'll fork and apply the above fix as that seemed to work.

[catalintatuta]

I found another case of infinite loop when intersecting, in my case it's stuck in connect_edges > orderEvents. Taking a look at the actual polygons it seems they share a pretty big chunk of a border, and I suspect this is why it's having issues sorting them. I'm also attaching a file with the 2 polygons test.js.zip

[w8r]

Thank you!

On Fri, 30 Sept 2022 at 13:01, Cătălin Tătuță @.***> wrote:

I found another case of infinite loop when intersecting, in my case it's stuck in connect_edges > orderEvents. Taking a look at the actual polygons it seems they share a pretty big chunk of a border, and I suspect this is why it's having issues sorting them. [image: Screenshot 2022-09-30 at 13 59 11] https://user-images.githubusercontent.com/80847665/193255789-3a2b20d7-c860-4f5c-ba4d-5b154bf39019.png I'm also attaching a file with the 2 polygons test.js.zip https://github.com/w8r/martinez/files/9683518/test.js.zip

— Reply to this email directly, view it on GitHub https://github.com/w8r/martinez/issues/98#issuecomment-1263430559, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAGSBAXLHDOU4JAP3OESSTWA3CALANCNFSM4GTQAYZA . You are receiving this because you were assigned.Message ID: @.***>

[crabmusket]

I seem to be seeing the same issue when unioning shapes with some overlapping edges - though in my case, intersection works fine! Here's a reproduction: https://codepen.io/crabmusket/pen/VwqbWXW

I wonder if I could patch this issue for my use case by randomly jiggling the vertices a little bit. But I'd prefer to dig into the cause and fix it if possible. I'm not sure why this would be such a problem 🤔