Boolean Operations on Polygons

I began extending the algorithm to handle paths containing Bézier curve segments:

This shows how far I've got. After the next step everything will drown in errors.

Debugging Boolean Operations on Polygons

Guess what! After fixing the 3rd issue, the algorithm suddenly feels stable. And because I'm so happy about it, below is a picture of my scribbling paper used to get there. Oh the irony of it: Requiring paper to get rid of paper. :)

Debugging Boolean Operations on Polygons

I replaced the algorithm which calculates the line intersections. The next class of errors are cases where dividing a line would place it somewhere else within the sweep line buffer. Currently the line's flags are calculated, then the line is divided and because the division might have changed the position of some lines in the sweep line buffer, the flags are recalculated for some known cases.
I found one case where this didn't happen and it seems that there are more.
A more reliable approach might be to reevaluate the order within the sweep line buffer and act accordingly. From there I could even brute force a list of all cases where the flags need to be recalculated.

TOAD & Fischland on Mac OS X

I'm slowly modernizing the C++ style in the library and this will come in handy: Bjarne Stroustrup announces C++ Core Guidelines.

Debugging Boolean Operations on Polygons

I'm beginning to grasp the algorithm. Pretty clever. The problem might be that the code to calculate line intersections isn't stable.

Debugging Boolean Operations on Polygons

Each iteration of the sweep algorithm is now printed into a PDF file. The trouble is that in a special case of overlapping lines of the subject and clipping polygons, none of these lines end up in the result when at least one should.

Debugging Boolean Operations on Polygons

What we see here is this:

  • the black line with the crosses is the previous polygon (subj)
  • the blue line with the circles is the polygon to be added (clip)
  • the red line is the result of the union operation (result)

My assumption is that the point on the right might be the same for subj and clip and this is causes the routine constructing the result from the sweep events to pick another point. In this case where the red line goes straight upwards it picked the next point right to it.
Which is strange, there shouldn't be a sweep event connecting these points at all...

TOAD & Fischland on Mac OS X

F. Martínez had warned me that the example code had some issues. But since I wanted to add support for curves

  1. I wanted to use the newest algorithm available and
  2. I had to debug and understand the algorithm anyway.

And to make this work as an absolute no-brainer, I began to write a debugger:

(But when I look at CGAL I might be totally wasting my time trying to implement this on my own... but it's so much fun! On the other hand, linking against CGAL might an adventure of it's own.)

TOAD & Fischland on Mac OS X

I've spend too much time trying to play guitar lately but here's an update: I began integrating the boolean path operations into the TOAD library, added some unit tests, build a little free hand drawing demo, which handles pressure and rotation... it looks okay but there are still some errors to hunt down.

TOAD & Fischland on Mac OS X

Porting the code for boolean operations on paths in Paper.js to C++ turned out too hard.

But there are quite a few documented algorithms available for this:

1974 "Reentrant polygon clipping", Sutherland and Hodgemann (convex clip polygon)
1980 "Polygon comparison using graph representation", Weiler
1982 "Plane-sweep algorithms for intersecting geometric figures", Nievergelt and Preparata
1983 "An analysis and algorithm for polygon clipping", Liang and Barsky
1989 "An algorithm for computing the union, intersection or different of two polygons", Margalit and Knott
1989 "Algorithm for clipping arbitrary polygons", Andereev
1992 "A generic solution to polygon clipping", Vatti
1998 "Efficient clipping of arbitrary polygons", Greiner and Hormann
2005 "A new algorithm for Boolean operations on general polygons", Yu Peng et al.
2007 "An algorithm for polygon clipping, for determining polygon intersections and unions", Liu et al.
2009 "A new algorithm for computing Boolean operations on polygons", F. Martínez et al.
2012 "An efficient algorithm for clipping operation based on trapezoidal meshes and sweep-line technique", Wang et al.
2013 "A simple Algorithm for Boolean operations on polygons", F. Martínez et al.

And I picked the most recent and F. Martínez was kind enough to mail me a copy of their C++ library which I'm now going to adapt to TOAD's data structures and bézier splines.


Subscribe to RSS