Infinite loop

[ctessum]

Hello,

I have found a bug. Adding the test below to bugs_test.go causes an infinite loop.

    {
        subject: polyclip.Polygon{{{1.427255375e+06, -2.3283064365386963e-10},
            {1.4271285e+06, 134.7111358642578}, {1.427109e+06, 178.30108642578125}}},
        clipping: polyclip.Polygon{{{1.416e+06, -12000}, {1.428e+06, -12000},
            {1.428e+06, 0}, {1.416e+06, 0}, {1.416e+06, -12000}}},
        result: polyclip.Polygon{},
    },

Uncommenting the text below fixes the infinite loop, but it causes some of the other bug tests to fail.

////if numIntersections == 2 && e1.p.Equals(e2.p) {
//if numIntersections == 2 && e1.polygonType == e2.polygonType {
//  return // the line segments overlap, but they belong to the same polygon
//}

I've been trying to find a way to fix both problems at the same time, but it seems to be over my head. If you have time to take a look at it I'd be grateful!

[akavel]

Ouch; I commented out this fragment of code as a part of an attempt to fix #3; not nice :) I'll have a look, although I admit that parts of this library are over my head too, unfortunately :/ (this is a port of the original authors' C code + some other port's Flex code, and while I got the main idea, some dark corners are still unclear to me...) I'll try my best to do something about it, though I can't promise I'll be able to resolve it.

That said, many thanks for the report, and for providing a nice reduced case! Also, if you find energy to try digging into it again at some point, if still not fixed then, I totally encourage you towards that :) and the algorithm is quite nice overally, although I noticed that the authors' website seemed to be down recently :/ but I think at least the .pdf paper is still searchable via google.

[mourner]

@akavel have you had a chance to look at this? I'm going to write a JavaScript implementation so wondering if it makes sense to write it from scratch to try to figure everything out or just port your awesome port (love Go btw) :)

Also can't seem to find the Flex code, any chance you have it saved somewhere?..

[dmitshur]

I'm going to write a JavaScript implementation so wondering if it makes sense to write it from scratch to try to figure everything out or just port your awesome port (love Go btw) :)

Have you considered using GopherJS to compile the Go library to JavaScript without having to do manual porting work?

[akavel]

@mourner As to the bug, a quick fix/workaround would be to revert to 2562f79. Unfortunately, this will reintroduce issue #3. But #3 shows up only for certain kinds of polygons (where some edge is traced over more than once by the same polygon). Then, you can say "I don't support such polygons". Other than that, unfortunately I didn't have enough time yet to have a deep look into this, and it looks harder than #3, so I can't say when I'll be able to dwell on that.

As to the AS version, I can't find it on my disk unfortunately; however, from quick googling I seem to have found another port of it, to Haxe. I believe it's very similar to AS/JS, so you should probably be able to use it too. Actually, if I recall correctly, Haxe can even compile straight to JS, so it might shorten your work significantly. If you decide to continue with this project, I'd be very grateful if you let me know whether #3 and/or #4 show up in the Haxe library too.

If you decide to go on by yourself, I'd be very grateful too if you let me know later and shared the results. The original paper is quite readable if given enough time and patience; however, IIUC they seem to skim over various details. Thus, I based on the AS3 library more, sometimes consulting with the original authors' C++ implementation (which was the source for the AS3 one too, I believe). This one I found much harder to read, and seems to be lost from the Internet too, anyway.... :/ Still, you can try to contact the original author of the paper, his address is still to be found on The Internet Archive. He did answer me once upon a time, when I let him know that I ported a new implementation of the stuff.

Good luck!

[mourner]

@akavel thanks so much for you thorough response! I'm picking this up again due to huge interest in an efficient boolean ops JS implementation in my company, and just a couple days ago discovered that Martinez published another paper on this algorithm in 2013: http://www.sciencedirect.com/science/article/pii/S0965997813000379. It clears up some of the vague points, describes logic for figuring out holes, and greatly improves logic for reconstructing contours, making it simpler.

I'm halfway through implementation at https://github.com/mapbox/polyclip. It doesn't yet reconstruct contours and doesn't handle overlapping cases, but at least finds intersections and classifies edges correctly, which is the meat of the algorithm.

[akavel]

Thanks for the info @mourner, that's interesting. That said, the paper seems behind a paywall, and $35 seems waaaay over my head for it, given that it's still totally 100% a hobby project for me as of now. Unless you/your company would be willing to share the paper or something.

Other than that, I could possibly try comparing your JS code with my Go code after you're finished, though without the paper I suppose it has high chance of being... extremely hard. (Given that I don't have idea how heavy their changes are.) That said, this could actually, paradoxically, make it... more stimulating for me...

[akavel]

By the way, as to the original C and AS3 code, it occurred to me today to search in one more place, and I found it. Not sure if it's still interesting to anyone, but just in case, I've put it up at: https://github.com/akavel/martinez-src

[mourner]

@akavel just sent you the paper in an e-mail. Let me know what you think! It's still tricky, going to take time until I figure out how to implement everything :)

[swill]

I have also run into this problem periodically, but I have not isolated the root cause.

[akavel]

@swill please try the workaround I mentioned in a comment above, i.e. revert to commit 2562f79 and see if that helps for you. (Please note that it will reintroduce issue #3.) _Please_ report if that makes things better for you; if yes, I'll revert the repository to this commit, and reopen #3, I think that will be better for users of the package. Also, from recent email discussions it seems that #3 is actually inherent in the original algorithm, according what the original author has said (although improving on that should still be possible with enough care). Also, _please do_ try and report any cases if you manage to reproduce them, this may _hugely_ help any people trying to improve on #3 in future.

[swill]

@akavel yes, I will test the workaround... i have not tried it yet, so i will try it. i was planning to give it a shot, but i wanted to post anyway to note i had also encountered this.

[akavel]

I'm reverting my ill-fated attempt at fixing #3, thus closing #4 and #5, but reopening #3. Especially #5 proved that the fix was totally breaking stuff :( Big thanks @swill.