TX_ - 3 months ago 16

C++ Question

Probably very simple question (I just want to ensure I'm right). Title is not 100% correct but below is what I need:

I want to compute bounding box (rectangle) for cubic bezier curve. I know that rectangle containing curve's control points is not literally bounding box, its most probably bigger, but I want to ensure that it can't be smaller, that is, it will always contain the curve.

I have spline defined by multiple successive cubic bezier curves, and I'd like to have its bounding box, or the closest thing to it (I'm not into complex formulas to calculate it, but if there is some not-too-complicated way of coding it, I'd appreciate to know).

Clarification: by "rectangle containing curve's control points" I mean the rectangle calculated like this: I take minimal X and minimal Y coordinates of control points as rectangle's top-left corner, and maximal X and maximal Y coordinates of control points as rectangle's lower-right corner. (Y axis goes from top to bottom). Then I want to ensure that curve certainly lies inside this rectangle.

Hope you understand what I mean :)

Answer

Yes, that's a safe assumption (ignoring any precision issues).

A degree-*n* Bezier curve (let's call it *A*) can be expressed as a linear interpolation of two degree-(*n*-1) Bezier curves (let's call them *B* and *C*). If *B* and *C* are within the bounding box, then clearly so is *A*. But you can apply this recursively; *B* and *C* can each be expressed as the linear interpolation of two degree-(*n*-2) curves, and so on. The base case is when you recurse down to degree-1 curves, which are just linear interpolations of the control points themselves.