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:
- Paths may be concave or of any shape
- Paths may consist of any number of "subpaths", creating overlapping parts or holes
- Paths may self-intersect
- Path edges may overlap any number of times
For now, the implementation only supports flattened paths (it will flatten automatically) but in a future it will support for paths with circular/elliptical arcs. 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 subpaths possible, that is it will split into subpaths when touching in one point
- Paths have no self-intersections and do not overlap
- Paths are X-monotone (ie. segment endpoints are always at a minimum/maximum along X)
This ensures that the resulting path is "simple" and while drawing is independent of the a NonZero or EvenOdd fill rule.
Many numerical stability issues have been fixed, but it remains a problem. It is suggested to use Path.Gridsnap to snap all endpoints to a fine grid. This is somewhat equivalent to using fixed-precision decimal numbers with a certain precision.
A quick test comparing to the previous (buggy) naive implementation shows that, with a combined segment count of 512 of both paths, an Path.And operation takes 16ms instead of 300ms. That an almost 20x improvement of speed with the previous implementation. But more importantly, the new implementation scale as O(n log n) instead of O(n^2), which ensure good performance even for very huge paths.
It is recommended that for huge paths, where the final representation determines a required precision much lower than given by the path (eg. for geographical paths), to use Path.Decimate to collapse most of the segments without loss of detail in the final representation (eg. a raster image).
| 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