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 Greiner-Hormann algorithm.
What works:
- Union
- Intersection
- Adding difference and XOR is trivial
Perhaps someone else could implement them as a learn-the-code experience, Jabier?
- Linear and Bezier segments of arbitrary degree
- Code is fairly clean and understandable
- Reasonably good performance, even though there are very few
optimizations
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 this
mostly planned out, except for a few nasty cases with overlapping Bezier segments.
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 than
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.
And uncross.
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 present in 2Geom (path-intersection.h, shape.h, region.h and the like), I'm going to remove them to reduce cruft.
Please do!
Very exciting work!
njh