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... :)

[swill]

My first round of testing seems to be showing that my workaround is working. Here is the problem that I think exists and how I am currently handling it.

I think the problem is when the two objects being unioned share an edge. My failure rate when the two objects shared at least one edge was very large (like ~25-35%). I have modified my code to make sure that the two objects don't share edges. I basically changed the way one of my objects draws so it is 0.001mm smaller than it used to be. Since this is well below the tolerances of the cutting tool, this should not affect the resulting part (actually, in this case I know that the union will result in the correct size part regardless). By doing this I have made sure that the edges that would have been shared are actually 0.001mm apart, which seems to be enough for this library to correctly determine the union.

Hope this helps others who are having similar problem... Good Luck... :)

[ctessum]

I've looked into it some, and I'm pretty sure the issue is in the connector.add() and pointchain.linkSegment() functions.

My understanding is at the point in the algorithm that these functions are called, the polygons are in the form of a bunch of segments without any information about the original relationships among the segments. As each segment is added, these functions check whether the segment lines up with the beginning or the end of an existing pointchain. If it lines up, the segment is added to the pointchain, otherwise it is used to start a new pointchain.

The problem arises when you have more than two segments that converge on a single point. In this case, the first segment to be added extends the point chain and any subsequent ones get left out as unclosed polygons and don't form part of the final result.

My guess is that within the context of this algorithm, the solution would lie in making sure that the segments get added to the pointchain in the correct order, although I'm not sure whether that's possible without messing up the order for the rest of the algorithm. Another way to go about it could be to redesign the result constructor to consist of a graph structure with nodes and edges---where each node can have more than two edges attached to it---instead of point chains and then have some way to construct the appropriate polygon after all the segments have been added.

[swill]

I have quite a bit of experience with this problem and I just have not gotten around to implementing a better solution or changing algorithms.

If you want a small program which can consistently output the problem for testing, you can check my test program here: https://github.com/swill/polycliptest

I actually wrote a small monitoring software (https://github.com/swill/slackd) for my production application (http://builder.swillkb.com) in order to better understand how often this problem arises and I have collected hundreds of failing cases which I plan to validate are working when I rewrite this aspect of my code.

If anyone spends time on this and wants some data to validate their solution, let me know and I can help provide some cases or you can just use my polycliptest code to generate your own test data.

[ctessum]

There is now a potential fix for this in #9 .

Basically, I added a preprocessor that adds all of the segments to a graph structure before adding them to the event queue. If, when adding a segment to the graph:

1. it is discovered that the segment already exists as part of the same polygon, the new segment is not added.
2. it is discovered that the inverse of the segment already exists (i.e. we already have {1,2} and we want to add {2,1}, then the new segment is not added and the inverse segment is deleted from the graph.

With this fix, however, there is still one failing test. This test is basically a triangle that loops around itself twice. The text next to the test states that the result of this should be a nil polygon, because the second loop cancels out the first loop. The way I've designed the preprocessor this situation is just considered a single triangle, which makes sense to me, but if it's decided that the test is correct I should be able to fix the situation by changing condition 1 to also delete the existing segment.

This probably adds some processing time to the algorithm, but probably not a lot because most of the time appears to be spent in the meat part of the algorithm rather than in this setup part.