How to merge two poly Bézier curves?

Question

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.

Answer 1

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.