I am battling with a programming problem.

Given two or more overlapping and interacting Bézier polygons, how can I perform merge (union) operations on a list of input Bézier polygons so as to produce merged Bézier polygons (polygons specified in Bézier format)?

Any resources in the Internet or algorithms about such implementations is very much appreciated.

  • $\begingroup$ If they were simple polygons, would you be able to do it? Can you find the intersection of two Bézier curves? Can you generate a Bézier curve which is a continuous subset of another Bézier curve? $\endgroup$ – Peter Taylor May 8 '12 at 9:24
  • $\begingroup$ Hi Peter, I know how to do simple polygons merge. I have not yet figure out how to do intersection and computing continuous subset of another Bezier curve. I only manage to understood the basic definition per Wikipedia definition for Bezier curve. Any resources on the net where I could read about the rest of such operations? Thanks! $\endgroup$ – Benny Khoo May 8 '12 at 9:29

There is an approach called de Casteljau subdivision which allows you to split a Bézier curve $B$ (parameterised by $t \in [0, 1]$) into two Bézier curves such that the first contains the points of $B(t) : t \in [0, t_0]$ and the second contains the points of $B(t) : t \in [t_0, 1]$. Details can be searched for on the web or found in a textbook on computational geometry.

Bézier curves have an important property called the convex hull property: because the weights of the control points are all non-negative in the relevant range of the parameter, the curve lies within the convex hull of the control points.

You can combine de Casteljau subdivision with the convex hull property to find the intersections of two Bézier curves to a desired level of precision.

findIntersections(Bézier b, Bézier c):
  if (b.convexHull intersect c.convexHull == {}):
    return {}
  if (b.convexHull.diameter() < epsilon):
    return {b.P0};
  // Simple approach: de Casteljau around t = 0.5
  // More sophisticated approach: use some heuristic
  // or trial-and-error technique
  (b1, b2) = b.splitAround(0.5);
  (c1, c2) = c.splitAround(0.5);
  return findIntersections(b1, c1) union
         findIntersections(b1, c2) union
         findIntersections(b2, c1) union
         findIntersections(b2, c2);

This can be adapted to unwind the de Casteljau subdivision and return values of the parameter $t$ instead.

After applying this to all pairs of Bézier curves (using intelligent filtering of some kind, e.g. a scan across the bounding boxes, to skip the pairs which obviously won't intersect), you can build up a cluster of disjoint curve segments, and then apply a wrapping algorithm to find the exterior ones.

  • $\begingroup$ Thanks Peter. I found a lot of clues from de Casteljau algorithm. I will update here once I got it working. Thanks again! $\endgroup$ – Benny Khoo May 11 '12 at 8:23

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.