2015-04-20 7:15 GMT+02:00 Nathan Hurst <njh@...1927...>:
- 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).
The results will be slightly different than in that SVG, because the algorithm I used does not require uncrossing as a preprocessing step. I think this is a nice feature, since it preserves self-intersections in places where they don't affect the result. I wrote a short summary of the underlying algorithm on Wikipedia recently: https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm
My modification is different in that it evaluates the even-odd rule for every portion between two intersections. However, the extra robustness this gives isn't used yet. I could have simply assigned alternating flags like in the original algorithm, but at least now I know that doing it this way won't be prohibitively expensive.
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.
For the arc-Bezier case, my thesis advisor suggested to convert elliptical arcs to four rational quadratic Beziers, each representing 1/4 of the ellipse between its conjugate diameters and intersect that using well known algorithms, then go back to the elliptical arc representation by using the fact that the weight of the middle control point is related to the time on the elliptical arc (the angle in the untransformed unit circle). I'm not sure about this. I'll first try the conic equation route, since it's the simplest and requires minimal new code.
The conic code implements some interesting stuff that I could use, but it needs to be refactored first. I'm pretty certain that If I hadn't spent substantial time on refactoring, writing unit tests for existing stuff and fixing the uncovered bugs, I wouldn't have managed to get this far.
Regards, Krzysztof