4
$\begingroup$

It is well known that a Bézier curve is contained within the convex hull of its control points. This is basically a consequence of the fact that the Bernstein polynomials are non-negative and sum to $1$. The property is useful in a variety of ways, as explained in these answers.

However, the convex hull is often quite a bit larger than the curve itself, and is not a "tight" fit. This leads to inefficiencies when using the convex hull in computations (e.g. intersection calculations).

Is there some other simple enclosing shape that is a tighter fit and is reasonably easy to calculate?

For example, for a quadratic Bézier curve with control points $\mathbf{P}_0$, $\mathbf{P}_1$, $\mathbf{P}_2$, the quadilateral with corners $\mathbf{P}_0$, $\tfrac12(\mathbf{P}_0 + \mathbf{P}_1)$, $\tfrac12(\mathbf{P}_1 + \mathbf{P}_2)$, $\mathbf{P}_2$ is a much tighter fit than the triangle with vertices $\mathbf{P}_0$, $\mathbf{P}_1$, $\mathbf{P}_2$. In fact, the quadrilateral is only two-thirds the size of the triangle (measured by area).

For a cubic curve with control points $\mathbf{P}_0$, $\mathbf{P}_1$, $\mathbf{P}_2$, $\mathbf{P}_3$, it's reasonable to try the quadrilateral with corners $\mathbf{P}_0$, $\tfrac14\mathbf{P}_0 + \tfrac34\mathbf{P}_1$, $\tfrac34\mathbf{P}_2 + \tfrac14\mathbf{P}_3$, $\mathbf{P}_3$. This almost works, but not quite -- the curve creeps a little bit outside of the quadrilateral.

Edit:I want an enclosing shape that is a single convex polygon. Obviously you can get an arbitrarily tight bounding shape by subdividing the curve and constructing bounding shapes for the individual pieces (as in Yves Daoust's answer below). But that's not what I want.

$\endgroup$
  • $\begingroup$ How about finding the convex hull of the set of points containing the maxima and minima of the curve at hand, and an appropriate subset of its control points? $\endgroup$ – wltrup Aug 11 '15 at 9:44
  • $\begingroup$ @wltrup -- Finding the maxima and minima of the curve is too expensive computationally. It's not too bad for quadratic and cubic curves, but it gets more difficult rapidly as the degree increases. $\endgroup$ – bubba Aug 11 '15 at 10:10
  • $\begingroup$ Yes, I realise that. I should have been more specific in my comment. I was thinking of lower degree curves only. $\endgroup$ – wltrup Aug 11 '15 at 10:11
1
$\begingroup$

Such bounding boxes can be obtained from the iterative construction of Bézier curves from Bézier curves of lower order.

In the quadratic case, the construction shows that the quadrilateral $\mathbf P_0$, $\lambda\mathbf P_0+(1-\lambda)\mathbf P_1$, $\lambda\mathbf P_1+(1-\lambda)\mathbf P_2$, $\mathbf P_2$ bounds the curve; both the triangle (for $\lambda=0$ or $\lambda=1$) and your quadrilateral ($\lambda=1/2$) are special cases of this.

In the cubic case, things are more complicated since the curve can cross the line from $\mathbf P_0$ to $\mathbf P_3$. In that case, the bounding shape needs to take care of both sides of that line. On either or both sides of the line, we can use points from the iterative construction to bound the curve: $\mathbf P_0$, $\lambda\mathbf P_0+(1-\lambda)\mathbf P_1$, $\lambda(\lambda\mathbf P_0+(1-\lambda)\mathbf P_1)+(1-\lambda)(\lambda\mathbf P_1+(1-\lambda)\mathbf P_2)$, $\lambda(\lambda\mathbf P_1+(1-\lambda)\mathbf P_2)+(1-\lambda)(\lambda\mathbf P_2+(1-\lambda)\mathbf P_3)$, $\lambda\mathbf P_2+(1-\lambda)\mathbf P_3$, $\mathbf P_3$. In the symmetric case, with $\lambda=1/2$, this becomes $\mathbf P_0$, $\frac12\left(\mathbf P_0+\mathbf P_1\right)$, $\frac14\left(\mathbf P_0+2\mathbf P_1+\mathbf P_2\right)$, $\frac14\left(\mathbf P_1+2\mathbf P_2+\mathbf P_3\right)$, $\frac12\left(\mathbf P_2+\mathbf P_3\right)$, $\mathbf P_3$.

$\endgroup$
  • $\begingroup$ Thanks. This is essentially subdivision again. The points you listed are the ones generated by the de Casteljau algorithm when dividing the curve at parameter value $\lambda$. $\endgroup$ – bubba Aug 12 '15 at 1:55
1
$\begingroup$

I found an answer, for quadratic and cubic curves, at least: "Polynomial bases for quadratic and cubic polynomials which yield control points with small convex hulls", by Gary Herron, Computer-Aided Geometric Design, Vol. 6, No. 1 (1989), pages 1-9.

$\endgroup$

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.