Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Mike 'Pomax' Kamermans May 6 '13 at 21:40

1 Answer 1

up vote 3 down vote accepted

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 6th-degree polynomial. 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."

share|improve this answer
    
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. –  Krof Drakula Oct 17 '11 at 13:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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