Boolean operations
Path boolean operations are supported using a modified Bentley-Ottmann algorithm, ensuring a time-complexity of O(n log n) (which is much better than the naive O(n^2)). Work is mostly based on Martínez et al. [1], with some additional modifications to make it work in all edge cases. Unlike the majority of other implementations, the implementation in Canvas allows many overlapping segments even from the same path. Specifically, the implementation has the following characteristics:
- Allows paths, subject or clipping, with any number of (overlapping) contours.
- Allows contours with any orientation, clockwise or anticlockwise.
- Contours may be concave or of any shape.
- Contours may self-intersect any number of times.
- Segments may overlap any number of times by any contour.
- Points may be crossed any number of times.
- Segments may be vertical.
- Clipping path is implicitly closed (it makes no sense if it's an open path).
- Subject path may be either open or closed.
- Paths are currently flattened, but supporting Bézier or elliptical arcs is a WIP (not anytime soon).
Supporting Béziers is non-trivial as it requires implementing the detection of intersections between all pairs of (line,quad,cube,arc), where especially cube-cube, quad-arc, and cube-arc are notoriously difficult.
The resulting paths have the following characteristics:
- Paths are counter clockwise oriented when filling, and clockwise oriented for holes.
- Paths are split into the smallest contours possible.
- Paths have no self-intersections and do not overlap.
- Paths are X-monotone (ie. segment endpoints are always at a minimum/maximum along X).
- If the subject path is open, it does not include overlapping segments with the clipping path.
This ensures that the resulting path is "simple" and while drawing is independent of the a NonZero or EvenOdd fill rule.
Performance is really good at O((n+k) log n), with n the number of segments and k the number of intersections. However, for handling huge paths it is recommended that you clip the path first using Path.Clip to the area of interest. When the final representation has a precision much lower than the path (eg. for geographical paths), it is recommended to use to simplify the path using Path.SimplifyVisvalingamWhyatt to collapse most of the segments without loss of detail in the final representation (eg. a raster image).
Numerical stability is guaranteed using Hobby's [2] algorithm.
| Command | LineTo | QuadTo | CubeTo | ArcTo |
|---|---|---|---|---|
| LineTo | yes | yes | yes | yes |
| QuadTo | no | no | no | |
| CubeTo | no | no | ||
| ArcTo | yes |
[1] F. Martínez, et al., "A simple algorithm for Boolean operations on polygons", Advances in Engineering Software 64 (2013), p. 11–19, http://dx.doi.org/10.1016/j.advengsoft.2013.04.004
[2] J.D. Hobby, "Practical segment intersection with finite precision output", Computational Geometry (1997), https://doi.org/10.1016/S0925-7721%2899%2900021-8