3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ since I noticed some people following the bezierinfo link: I recently fully redid the article, and it now contains examples and code for performing boolean shape operations. $\endgroup$ – Mike 'Pomax' Kamermans May 6 '13 at 21:40
4
$\begingroup$

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."

$\endgroup$
  • $\begingroup$ I meant rasterizing in my question above to mean rendering the actual shapes onto a bitmap buffer to map pixels as the inside/outside of a given shape. As for the intersections, the link above states that a simplification is to use line segment approximations to find the approximate t and split the Bezier using De Castelau's algorithm; I'm just looking for something that can be applied in a reasonable run time. $\endgroup$ – Klemen Slavič Oct 17 '11 at 13:11
  • $\begingroup$ "intersection between two cubics...requires finding the roots of a 6th-degree polynomial" Are you sure it's not 9th degree? For cubics, I think Bezout says that it's 3rd degree times 3rd degree. $\endgroup$ – Ecir Hana Feb 1 '16 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.