Union bug

[nicoulaj]

package main

import (
    "fmt"
    "github.com/akavel/polyclip-go"
)

func main() {
    subject  := polyclip.Polygon{{{1,1}, {1,2}, {2, 2}, {2, 1}}}
    clipping := polyclip.Polygon{{{2,1}, {2,2}, {3, 2}, {3, 1}},
                                 {{1,2}, {1,3}, {2, 3}, {2, 2}},
                                 {{2,2}, {2,3}, {3, 3}, {3, 2}}}
    result := subject.Construct(polyclip.UNION, clipping)
    fmt.Println(result)
}

prints:

[[{2 2} {2 3} {1 3} {1 2} {1 1} {2 1} {3 1} {3 2}]]

which looks incorrect...

(4 touching rectangles, the upper right one is lost after union)

[akavel]

Indeed, interesting, thanks! I'll have to dig back through the algorithm to try debugging it, haven't looked at the stuff for quite long.

[akavel]

Reopening this, as my attempt at fixing it was too optimistic and actually has broken more than it fixed, unfortunately (see #4, especially some discussion, and #5).

Also, from some further discussion @mourner had with F. Martínez, it seems that the original algorithm as described in the paper wasn't supporting polygons with overlapping edges, such as those above. So, the hunt for a solution is still open.

To give some visual aid, the input is as below:

with the result:

[swill]

This does not solve the problem, but here is a potential workaround for this issue that may help some people.

Instead of trying to do a union of many contours at the same time, treat each contour as its own polygon and then do the union of those polygons. So the described example could be solved with the following code:

package main

import (
    "fmt"
    "github.com/akavel/polyclip-go"
)

func main() {
    subject := polyclip.Polygon{{{1, 1}, {1, 2}, {2, 2}, {2, 1}}}
    result := subject.Construct(polyclip.UNION, polyclip.Polygon{{{2, 1}, {2, 2}, {3, 2}, {3, 1}}})
    result = result.Construct(polyclip.UNION, polyclip.Polygon{{{1, 2}, {1, 3}, {2, 3}, {2, 2}}})
    result = result.Construct(polyclip.UNION, polyclip.Polygon{{{2, 2}, {2, 3}, {3, 3}, {3, 2}}})
    fmt.Println(result)
}

Which produces the following output:

[[{2 3} {1 3} {1 2} {1 1} {2 1} {3 1} {3 2} {3 3}]]

Here is an SVG of the output (scaled up by 10x) to illustrate graphically that it does work as a workaround.

I hope this helps someone...

[swill]

I am using this lib in production and I am getting WAY too many errors because of this. About 25% of my unions fail (which sucks).

Here is an example of a union which failed (and shouldn't have). The format looks a little different because I am using my own point system, but you get the idea.

[{X:274.2973574304023 Y:-84.26594832858831} {X:274.55617647550486 Y:-83.30002250229924} {X:275.3289171365361 Y:-83.50707773838127} {X:276.13125617635393 Y:-80.51270767688516} {X:275.35851551532267 Y:-80.30565244080313} {X:276.85966597691726 Y:-74.70328264832654} {X:277.6324066379485 Y:-74.91033788440856} {X:278.43474567776633 Y:-71.91596782291245} {X:277.66200501673507 Y:-71.70891258683042} {X:277.9208240618376 Y:-70.74298676054136} {X:264.3978624937906 Y:-67.11952012910606} {X:264.1390434486881 Y:-68.08544595539513} {X:263.3663027876568 Y:-67.87839071931312} {X:262.563963747839 Y:-70.87276078080923} {X:263.3367044088703 Y:-71.07981601689124} {X:261.8355539472757 Y:-76.68218580936784} {X:261.0628132862444 Y:-76.47513057328582} {X:260.2604742464266 Y:-79.46950063478194} {X:261.0332149074579 Y:-79.67655587086395} {X:260.77439586235533 Y:-80.64248169715302}]

and

[{X:274.2973574304023 Y:-84.26594832858831} {X:274.884876662785 Y:-82.07329670291213} {X:276.4062098391903 Y:-82.4809366989486} {X:276.1991546031083 Y:-83.25367735997985} {X:277.86537665345696 Y:-83.7001402127817} {X:277.62726313196265 Y:-84.58879197296764} {X:280.8148183587166 Y:-85.44289482180596} {X:281.0529318802109 Y:-84.55424306162003} {X:282.6225613479306 Y:-84.97482400991163} {X:283.4585468636118 Y:-81.85488359099793} {X:284.3037319616147 Y:-82.08135025546264} {X:285.0284252879017 Y:-79.37675794185324} {X:284.1832401898988 Y:-79.15029127738855} {X:285.8060356026916 Y:-73.09393634655609} {X:284.2364061349719 Y:-72.67335539826449} {X:284.49004879917237 Y:-71.7267480885012} {X:281.3024935724184 Y:-70.87264523966287} {X:281.04885090821796 Y:-71.81925254942617} {X:279.3826288578693 Y:-71.37278969662431} {X:279.1755736217873 Y:-72.14553035765556} {X:277.654240445382 Y:-71.7378903616191} {X:277.9208240618376 Y:-70.74298676054136} {X:264.3978624937906 Y:-67.11952012910606} {X:264.13127887733503 Y:-68.1144237301838} {X:262.60994570092976 Y:-67.70678373414734} {X:262.81700093701176 Y:-66.93404307311609} {X:261.1507788866631 Y:-66.48758022031423} {X:261.40442155086356 Y:-65.54097291055093} {X:258.2168663241097 Y:-64.68687006171263} {X:257.9632236599092 Y:-65.63347737147592} {X:256.3935941921894 Y:-65.21289642318432} {X:254.7707987793966 Y:-71.26925135401677} {X:253.92561368139368 Y:-71.04278468955206} {X:253.20092035510663 Y:-73.74737700316146} {X:254.04610545310956 Y:-73.97384366762617} {X:253.21011993742843 Y:-77.09378408653986} {X:254.77974940514818 Y:-77.51436503483146} {X:254.54163588365387 Y:-78.4030167950174} {X:257.7291911104078 Y:-79.2571196438557} {X:257.9673046319021 Y:-78.36846788366977} {X:259.63352668225076 Y:-78.81493073647162} {X:259.84058191833276 Y:-78.04219007544037} {X:261.36191509473804 Y:-78.44983007147684} {X:260.77439586235533 Y:-80.64248169715302}]

produces

[]

I have hundreds of similar examples. This is such a problem I am considering just writing a Cgo wrapper around GPC to try to solve this. :(

Any ideas for solving this?

[akavel]

Sorry, still can't help you :( a serious analysis of the underlying algorithm & paper is required to find a correct solution. That said, thanks for the new testcases! They might hopefully become useful at some point in future.

[swill]

Ya no worries. This is what I was expecting. I was reading some other stuff on this algorithm (sorry I can't find the link now), but it seemed to imply that this algorithm has problems when two polygons share an edge. Unfortunately this is often the case for my polygons. I may actually see if I can modify my software to make the lines 0.001mm apart and see if that reduces the chance of union failing. If I can reduce my error frequency by doing this I will report back. My software generates CAD, so I have to be careful about fudging the user's numbers too much, but I think I can get away with 0.001mm. Thanks for the hard work with this code... :)