I'm very impressed. For the other readers out there, this is a
problem that has stumped a long line of very smart people (including
professional mathematicians and academia) and CGAL, a widely cited
geometry library, has a broken implementation. This is a surprisingly
hard problem to solve correctly. I agree it's publication worthy.
More importantly, this is not some theoretically wonderful
implementation, this is a working, practical implementation.
It also enables many interesting other tools which have either had to
work around the existing broken boolops, or have had hacks to
approximate sepecial cases. Being both fast and robust makes so
many things practical.
On Mon, Apr 20, 2015 at 02:04:32AM +0200, Krzysztof Kosiński wrote:
There is a new toy "boolops-new" in 2Geom's source
repository - it
computes an union of two paths using my new boolops code based on the
- Adding difference and XOR is trivial
Perhaps someone else could implement them as a learn-the-code
- Linear and Bezier segments of arbitrary degree
- Code is fairly clean and understandable
- Reasonably good performance, even though there are very few
This is almost certainly an improvement on what we have, to gain
confidence can you also write some unit tests that capture the various
edge cases as per that svg (and anything else you can think of).
What remains to be done:
- Could be simplified a bit and better documented.
- Intersection procedures for arc-arc and arc-Bezier cases. Currently
they throw UnimplementedError.
Two directions to consider:
use the implicit formula for conics (AX^2 + BXY + CY^2 + DX + EY + F =
0) that we have code to generate, then substitute in the bezier for X,
Y, and use roots(). This will double the degree of the curve, but
should be quite stable.
Or you could try and write something similar to bezier clipping
algorithm by projecting a linear approximation of the bezier against
the ellipse or vice versa. More fiddly but potentially more accurate.
Intersecting conics is already in 2geom I think.
- Handling of degeneracies and second-order intersections. I have
mostly planned out, except for a few nasty cases with overlapping
Also useful are the various combinations with 1d topology - given
paths A and B it is useful to compute the set ops between A*B, dA*B
and dA*dB (where d refers to the outline). This code implements A*B,
and we already have dA*dB.
- Add &, |, / operators to PathVector. I think / will be better
minus for set subtraction.
Agreed. It's sets, not arithmetic.
- Function that converts a nonzero winding pathvector to even-odd
winding pathvector with the same filled areas. It's a lot easier to do
this conversion than it is to do Booleans on nonzero winding fills.
I observed no crashes or hangs, though when two pathvectors overlap
exactly, some paths can be skipped in the output.
Yep, my inextensive testing with the toy also didn't crash (or
suddenly take mysterious amounts of time).
Since this code is already a lot better than the old attempts
in 2Geom (path-intersection.h, shape.h, region.h and the like), I'm
going to remove them to reduce cruft.
Very exciting work!