Given two closed shapes made up of Bézier curves (and/or straight lines), I'm looking for an efficient way of calculating the resulting shape of the following Boolean operations:
- union
- difference
- intersection
- slice (imagine each of the shapes in the Venn diagram as its own shape; this operation is optional and can be expressed as a composite operation of the above)
To give this problem some context, I'm trying to implement Boolean operations for SVG shapes using Javascript processing; defining paths in SVG only gives you fill rules and clipping paths, but none of these helps with creating arbitrary boolean-derived shapes.
Addendum: I'm also looking for a way to determine if a point lies inside a closed Bézier shape.
Addendum 2: I found a page that explains such concepts, but is missing the chapter on boolean operations; there is a placeholder example in ProcessingJS demonstrating boolean operations, but as far as I can tell, it uses rasterizing to determine the inside/outside state of a point.
Best Answer
To perform those Boolean operations, you must be able find the intersections between two Bézier curves. This is a difficult problem. To gain some appreciation, look at this web page on the topic by Richard Kinch. If you are using the usual cubic Bézier curves, then you are seeking the intersection between two cubics, which, by Bézout's theorem, requires finding the roots of a 9th-degree polynomial if done numerically, and a deep recursion if done by divide and conquer. This is why sometimes the computation is avoided ("rasterizing," as you say).
Here is a useful description of this topic, written by Tom Sederberg of BYU: PDF link. See Section 7.4, "Computing the Intersection of Two Bézier Curves."