One advantageous operation is rendering a Bezier curve when working with path nodes. In most cases, you do not care about the bounds of the curve itself because it is a line, the drawing area is of fixed size, or the view is movable. On the other hand, wanting to size an SVG view box to a Bezier curve means that calculating the precise bounds of the curve is very useful.
Where to begin
Calculating the bounds first requires the equation by which Beziers are defined. The equation for a point on a cubic Bezier \(\textbf{B}(t)\) is defined as (notice the presence of the binomial theorem):
$$ \textbf{B}(t) = (1 - t)^3\textbf{P}_0 + 3(1 - t)^2t\textbf{P}_1 + 3(1 - t)t^2\textbf{P}_2 + t^3\textbf{P}_3 $$
The curve is officially defined for the \([0,1]\) range. Locating the bounds requires finding precisely where the curve "turns around" in either the \(x\) or \(y\) direction. These are called the inflection points and are readily found by the proper application of calculus. If you do not want to see how the calculus is done, you can skip past it.
Calculus
The first step to finding the inflection points is calculating the curve's derivative. It is possible to find the inflection points in every dimension using the calculated derivative. Due to the nature of the curve, every inflection point that is both a real number and within the \([0,1]\) range will be an excellent candidate for calculating the overall bounds.
Deriving Beziers
The derivative is pretty straightforward if you know how to apply the chain rule, the product rule. Remember that the points are constants and work one chunk at a time.
The first chunk is pretty easy, thanks to the chain rule.
\begin{align}
\textbf{B}(t) &= (1 - t)^3\textbf{P}_0 + \dots & u &= 1 - t\cr
&= u^3\textbf{P}_0 + \dots\cr\cr
\textbf{B}'(t) &= 3u^2u'\textbf{P}_0 + \dots & u' &= -1\cr
&= -3(1-t)^2\textbf{P}_0 + \dots \cr
&= -3(t^2 - 2t + 1)\textbf{P}_0 + \dots
\end{align}
The second chunk is a bit more complicated, and at first glance, there are two ways to do it. One way involves simply expanding the term, and the other way uses a combination of the product rule and the chain rule.
By way of expansion, there are only a few steps.
\begin{align}
\textbf{B}(t) &= \dots + 3(1 - t)^2t\textbf{P}_1 + \dots \cr
&= \dots + 3(t^2 -2t + 1)t\textbf{P}_1 + \dots \cr
&= \dots + 3(t^3 -2t^2 + t)\textbf{P}_1 + \dots \cr
\textbf{B}'(t) &= \dots + 3(3t^2 -4t + 1)\textbf{P}_1 + \dots
\end{align}
Combining the product and chain rules is more complex than expanding the term, even though the first step seems like a logical jump.
\begin{align}
\textbf{B}(t) &= \dots + 3(1 - t)^2t\textbf{P}_1 + \dots \cr
&= \dots + 3u^2t\textbf{P}_1 + \dots & u &= 1 - t \cr
\textbf{B}'(t) &= \dots + (6uu't + 3u^2)\textbf{P}_1 + \dots & u' &= -1 \cr
&= \dots + 3(u^2 - 2ut)\textbf{P}_1 + \dots \cr
&= \dots + 3((1-t)^2 - 2(1-t)t)\textbf{P}_1 + \dots\cr
&= \dots + 3(t^2 - 2t + 1 - 2t + 2t^2)\textbf{P}_1 + \dots \cr
&= \dots + 3(3t^2 -4t + 1)\textbf{P}_1 + \dots \cr
\end{align}
Both ultimately yielded the same result, though an initial substitution instinct resulted in more work. Being aware of this while looking at the third term expansion seems like the better choice, especially considering the simplicity.
\begin{align}
\textbf{B}(t) &= \dots + 3(1 - t)t^2\textbf{P}_2 + \dots \cr
&= \dots + 3(t^2 - t^3)\textbf{P}_2 + \dots \cr
\textbf{B}'(t) &= \dots + 3(2t - 3t^2)\textbf{P}_2 + \dots \cr
\end{align}
The final term is straightforward to derive and is just one step.
\begin{align}
\textbf{B}(t) &= \dots + t^3\textbf{P}_3 \cr
\textbf{B}'(t) &= \dots + 3t^2\textbf{P}_3
\end{align}
Adding all the pieces together results in a derivative similar to the original equation.
$$ \textbf{B}'(t) = -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3 $$
Rearranging the Derivative
From the previous section we calculated that the derivative is:
$$ \textbf{B}'(t) = -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3 $$
The next step to finding the points of inflection for each dimension \((x, y, z)\) is to solve that equation for the values of \(t\) that make \(\textbf{B}'(t) = 0\) for that dimension. This seems like an impossible task given the size of the equation, but on closer inspection, it is clear that there are no higher-order terms than \(t^2\). Perhaps the equation can be rearranged in terms of \(t\) so that the quadratic equation can be used to solve it. Turning the equation into standard quadratic form takes only a few steps.
\begin{align}
\textbf{B}'(t) &= -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3\cr
0 &= 3(-(t^2 - 2t + 1)\textbf{P}_0 + (3t^2 -4t + 1)\textbf{P}_1 + (2t - 3t^2)\textbf{P}_2 + t^2\textbf{P}_3)\cr
&= -(t^2 - 2t + 1)\textbf{P}_0 + (3t^2 -4t + 1)\textbf{P}_1 + (2t - 3t^2)\textbf{P}_2 + t^2\textbf{P}_3\cr
&= -\textbf{P}_0t^2 + 2\textbf{P}_0t - \textbf{P}_0 + 3\textbf{P}_1t^2 - 4\textbf{P}_1t + \textbf{P}_1 - 3\textbf{P}_2t^2 + 2\textbf{P}_2t + \textbf{P}_3t^2\cr
&= -\textbf{P}_0t^2 + 3\textbf{P}_1t^2 - 3\textbf{P}_2t^2 + \textbf{P}_3t^2 + 2\textbf{P}_0t - 4\textbf{P}_1t + 2\textbf{P}_2t - \textbf{P}_0 + \textbf{P}_1\cr
&= (-\textbf{P}_0 + 3\textbf{P}_1 - 3\textbf{P}_2 + \textbf{P}_3)t^2 + (2\textbf{P}_0 - 4\textbf{P}_1 + 2\textbf{P}_2)t + (-\textbf{P}_0 + \textbf{P}_1)
\end{align}
To make things a little easier, it makes sense to go ahead and save off the groupings in simple variables, making composition into the quadratic formula much easier.
\begin{align}
0 &= at^2 + bt + c\cr
\text{where:}\cr
a &= \textbf{P}_3 - 3\textbf{P}_2 + 3\textbf{P}_1 - \textbf{P}_0\cr
b &= 2\textbf{P}_2 - 4\textbf{P}_1 + 2\textbf{P}_0\cr
c &= \textbf{P}_1 - \textbf{P}_0
\end{align}
I flipped the order of the points around so the subtraction lines up a little nicer, but other than that, it is a simple substitution that plugs nicely into the quadratic formula.
\begin{gather}
\Delta = b^2 - 4ac\cr
\frac{-b \pm \sqrt\Delta}{2a}
\end{gather}
Notice that the delimiter is kept separate because there is no real answer if \(\Delta < 0\).
Application
Now that things are in easy-to-digest pieces, it is time to implement all the hard work into some code. Since the derivative only gives the values in terms of \(t\), they will need to be plugged into the Bezier equation in order to get the actual \((x,y)\) points of the inflection.
There will be four functions in total. The first accepts the \((x,y)\) points to apply the derivative. The second accepts just a single dimension for each point to apply the derivative. The third calculates the result of \((x,y)\) points and a \(t\) value with the Bezier equation. The fourth and final function calculates the Bezier equation for a single dimension. In JavaScript it looks like this:
function getBezierInflectionPoints(p0, p1, p2, p3) {
return getBezierInflectionPointsForDimension(p0.x, p1.x, p2.x, p3.x)
.concat(getBezierInflectionPointsForDimension(p0.y, p1.y, p2.y, p3.y))
.map(function(t) {
return getBezierPoint(p0, p1, p2, p3, t);
});
}
function getBezierInflectionPointsForDimension(p0, p1, p2, p3) {
var a = p3 - 3 * p2 + 3 * p1 - p0,
b = 2 * p2 - 4 * p1 - 2 * p0,
c = p1 - p0,
delimiter = b * b - 4 * a * c,
value = 0,
values = [];
if (delimiter >= 0) {
value = (-b + Math.sqrt(delimiter)) / (2 * a);
if (value > 0 && value < 1) {
values.push(value);
}
value = (-b - Math.sqrt(delimiter)) / (2 * a);
if (value > 0 && value < 1) {
values.push(value);
}
}
return values;
}
function getBezierPoint(p0, p1, p2, p3, t) {
return {
x: getBezierPointForDimension(p0.x, p1.x, p2.x, p3.x, t),
y: getBezierPointForDimension(p0.y, p1.y, p2.y, p3.y, t)
};
}
function getBezierPointForDimension(p0, p1, p2, p3, t) {
return Math.pow(1 - t, 3) * p0
+ 3 * Math.pow(1 - t, 2) * t * p1
+ 3 * (1 - t) * Math.pow(t, 2) * p2
+ Math.pow(t, 3) * p3;
}
Final Thoughts and Observations
The critical thing to remember is that rendered Bezier curves have a width (otherwise, you could not see it unless it is filled in, of course). It is a good idea to add and subtract half of the stroke-width to both the \(x\), and \(y\) coordinates that come back from the function to ensure that the curve is not "cut in half" at the boundaries.
It is also a good idea to avoid unnecessary calculations whenever possible. This is very easy because of how Bezier curves are defined mathematically. If the middle points in the set exist within the bounds of the outer points (\(\textbf{P}_1\) and \(\textbf{P}_2\) exist within \([\textbf{P}_0, \textbf{P}_3]\)) no additional calculation needs to be done beyond the bounds of the outer points (factoring in stroke-width of course). While this may only eliminate a few cases here and there, quite a few operations get saved in the process. The thing to keep in mind is that if either point strays outside the \([\textbf{P}_0, \textbf{P}_3]\) bounds, the full calculations should be run.
Are there any approximations that can be done to save on math? Sure, but this gives you precise boundaries, and the number of calculations saved is generally not going to be significant. Besides, how frequently will this code be run, and is it the bottleneck?