| 1 |
% Copyright 2021 by marmotghost |
| 2 |
% v0.1 |
| 3 |
% |
| 4 |
% This file may be distributed and/or modified under the |
| 5 |
% LaTeX project public license (LPPL), version 1.3c |
| 6 |
% see |
| 7 |
% https://www.latex-project.org/lppl/lppl-1-3c/ |
| 8 |
% |
| 9 |
% It has been claimed that the license of this library had been changed so that this |
| 10 |
% library is no longer part of pgf. This claim is a lie. There was no license change |
| 11 |
% at all. Now, in 2021, the license got changed to LaTeX project public license |
| 12 |
% (LPPL), version 1.3c. |
| 13 |
|
| 14 |
\section{Bounding Boxes for B\'ezier Curves} |
| 15 |
|
| 16 |
|
| 17 |
\begin{pgflibrary}{bbox} |
| 18 |
This library provides methods to determine tight bounding boxes for |
| 19 |
B\'ezier curves. This library loads and uses the |
| 20 |
|fpu| library. While this library might |
| 21 |
possibly work with |TeX| or |ConTeXt|, this has never been tested. |
| 22 |
\end{pgflibrary} |
| 23 |
|
| 24 |
\subsection{Bounding box without the library} |
| 25 |
|
| 26 |
\tikzname\ determines the bounding box of (cubic) Bezier curves by establishing the |
| 27 |
smallest rectangle that contains the end point and the two control points of the |
| 28 |
curve. |
| 29 |
|
| 30 |
\begin{codeexample}[width=5cm] |
| 31 |
\begin{tikzpicture}[% |
| 32 |
bullet/.style={circle,fill, |
| 33 |
inner sep=1pt}] |
| 34 |
\draw (0,0) .. controls (-1,1) |
| 35 |
and (1,2) .. (2,0); |
| 36 |
\draw (current bounding box.south west) |
| 37 |
rectangle |
| 38 |
(current bounding box.north east); |
| 39 |
\draw[red,dashed] |
| 40 |
(0,0) -- (-1,1) |
| 41 |
node[bullet,label=above:{$(x_a,y_a)$}]{} |
| 42 |
(2,0) -- (1,2) |
| 43 |
node[bullet,label=above:{$(x_b,y_b)$}]{}; |
| 44 |
\path (0,0) |
| 45 |
node[bullet,label=below:{$(x_0,y_0)$}]{} |
| 46 |
(2,0) |
| 47 |
node[bullet,label=below:{$(x_1,y_1)$}]{}; |
| 48 |
\end{tikzpicture} |
| 49 |
\end{codeexample} |
| 50 |
|
| 51 |
As one can see from this illustration, this may lead to drastic overestimates of |
| 52 |
the bounding box. |
| 53 |
|
| 54 |
\subsection{Computing the bounding box} |
| 55 |
|
| 56 |
Establishing the precise bounding box has been discussed in various places, the |
| 57 |
following discussion uses in part the results from |
| 58 |
\url{https://pomax.github.io/bezierinfo/}. What is a cubic B\'ezier curve? A |
| 59 |
cubic B\'ezier curve running from $(x_0,y_0)$ to $(x_1,y_1)$ with control points |
| 60 |
$(x_a,y_a)$ and $(x_b,y_b)$ can be parametrized by |
| 61 |
\begin{equation} |
| 62 |
\gamma(t)~=~ |
| 63 |
\begin{pmatrix} x(t)\\ y(t) \end{pmatrix}~=~ |
| 64 |
\begin{pmatrix}t^3 x_{1}+3 t^2 (1-t) x_{b}+(1-t)^3 |
| 65 |
x_{0}+3 t (1-t)^2 x_{a}\\ |
| 66 |
t^3 y_{1}+3 |
| 67 |
t^2 (1-t) y_{b}+(1-t)^3 y_{0}+3 t (1-t)^2 |
| 68 |
y_{a}\end{pmatrix}\;,\label{eq:gammaBezier} |
| 69 |
\end{equation} |
| 70 |
where $t$ runs from $0$ to $1$ (and $\gamma(0)=(x_0,y_0)$ and |
| 71 |
$\gamma(1)=(x_1,y_1)$). Surely, the bounding box has to contain |
| 72 |
$(x_0,y_0)$ and $(x_1,y_1)$. If the functions $x(t)$ and $y(t)$ have extrema in |
| 73 |
the interval $[0,1]$, then the bounding box will in general be larger than that. |
| 74 |
In order to determine the extrema of the curve, all |
| 75 |
we need to find the extrema of the functions $x(t)$ and $y(t)$ for $0\le t\le |
| 76 |
1$. That is, we need to find the solutions of the quadratic equations |
| 77 |
\begin{equation} |
| 78 |
\frac{\mathrm{d}x}{\mathrm{d}t}(t)~=~0\quad\text{and}\quad |
| 79 |
\frac{\mathrm{d}y}{\mathrm{d}t}(t)~=~0\;. |
| 80 |
\end{equation} |
| 81 |
% (*parametrization of x:*) |
| 82 |
% myx = x0 (1 - t)^3 + 3 xa (1 - t)^2 t + 3 xb (1 - t) t^2 + x1 t^3 |
| 83 |
% (*d1\ne0 condition for t1 and t2 to exist*) |
| 84 |
% === (*case d1\ne0*) == |
| 85 |
% d1 = x0 - x1 - 3 xa + 3 xb |
| 86 |
% (*square root, d2=0 \[Rule] only one solution,d2<0 \[Rule] no solution*) |
| 87 |
% d2 = x0*x1 - x1*xa + xa*xa - x0*xb - xa xb + xb*xb |
| 88 |
% (*first t*) |
| 89 |
% t1 = (x0 - 2*xa + xb - sqrt(d2))/(x0 - x1 - 3*xa + 3*xb) |
| 90 |
% = (x0 - 2*xa + xb - sqrt(d2))/d1 |
| 91 |
% (*second t*) |
| 92 |
% t2 = (x0 - 2*xa + xb + sqrt(d2))/(x0 - x1 - 3*xa + 3*xb) |
| 93 |
% = (x0 - 2*xa + xb + sqrt(d2))/d1 |
| 94 |
% === (*case d1=0*) == |
| 95 |
% (*2nd condition for extra condition: d3\ne0*) |
| 96 |
% d3 = x1 + xa - 2 xb |
| 97 |
% (*third t*) |
| 98 |
% t3 = (x1 + 2*xa - 3*xb)/(2*d3)% d3 = x1 + 3 xa - 3 xb - x0 |
| 99 |
Let's discuss $x$ first. If the discriminant |
| 100 |
\begin{equation} |
| 101 |
d~:=~x_0\,x_1 - x_1\,x_a + x_a\,x_a - x_0\,x_b - x_a x_b + x_b\,x_b |
| 102 |
\end{equation} |
| 103 |
is greater than 0, there are two solutions |
| 104 |
\begin{equation} |
| 105 |
t_\pm~=~\frac{x_{0}-2x_{a}+x_{b}\pm\sqrt{d}}{% |
| 106 |
x_{0}-x_{1}-3(x_{a}- x_{b})} \;. |
| 107 |
\end{equation} |
| 108 |
If the denominator $x_{0}-x_{1}-3(x_{a}- x_{b})$ vanishes, one may use the |
| 109 |
l'Hospital rule to determine the solutions. |
| 110 |
In this case, we need to make sure that the bounding box contains, say |
| 111 |
$(x(t_-),y_0)$ and $(x(t_+),y_0)$. If $d\le0$, the bounding box does not need to |
| 112 |
be increased in the $x$ direction. On the other hand, if there are solutions, |
| 113 |
one needs include the points $\bigl(x(t_\pm),y_0\bigr)$ with $x(t)$ from |
| 114 |
\eqref{eq:gammaBezier} in the bounding box. |
| 115 |
|
| 116 |
The analogous statements apply to $y(t)$. |
| 117 |
|
| 118 |
\subsection{Using the library} |
| 119 |
|
| 120 |
\begin{key}{/pgf/bezier bounding box=\meta{boolean} (default true)} |
| 121 |
Turn the tight bounding box algorithm on and off. The initial value is |
| 122 |
|false|. |
| 123 |
|
| 124 |
\emph{Caveat:} As can be seen from the derivations, the necessary |
| 125 |
computations involve the squaring of lengths and taking ratios of lengths, |
| 126 |
which can easily lead to |dimension too large| errors. The library uses |
| 127 |
|fpu| to account for that, but errors may still occur. |
| 128 |
\end{key} |
| 129 |
|
| 130 |
|
| 131 |
\begin{codeexample}[width=5cm] |
| 132 |
\begin{tikzpicture}[bezier bounding box,% |
| 133 |
bullet/.style={circle,fill, |
| 134 |
inner sep=1pt}] |
| 135 |
\draw (0,0) .. controls (-1,1) |
| 136 |
and (1,2) .. (2,0); |
| 137 |
\draw (current bounding box.south west) |
| 138 |
rectangle |
| 139 |
(current bounding box.north east); |
| 140 |
\draw[red,dashed] |
| 141 |
(0,0) -- (-1,1) |
| 142 |
node[bullet,label=above:{$(x_a,y_a)$}]{} |
| 143 |
(2,0) -- (1,2) |
| 144 |
node[bullet,label=above:{$(x_b,y_b)$}]{}; |
| 145 |
\path (0,0) |
| 146 |
node[bullet,label=below:{$(x_0,y_0)$}]{} |
| 147 |
(2,0) |
| 148 |
node[bullet,label=below:{$(x_1,y_1)$}]{}; |
| 149 |
\end{tikzpicture} |
| 150 |
\end{codeexample} |
| 151 |
|
| 152 |
A few comments are in order. |
| 153 |
\begin{enumerate} |
| 154 |
\item For paths with arrow heads one may need to load the \texttt{bending} |
| 155 |
library. This is because otherwise the quick arrow head distorts the path, and |
| 156 |
this happens after the bounding box has been computed. Even worse, arrow heads |
| 157 |
could get deformed. |
| 158 |
\item If you shorten a path by some negative length, the bounding box will not |
| 159 |
be accurate either. However, this has nothing to do with curves, it also |
| 160 |
applies to straight lines. So this is not specific to the |bbox| library but |
| 161 |
something that one may want to keep in mind. |
| 162 |
\item Let us also note that the computations can lead to |Dimension too large| |
| 163 |
errors. These errors do not come directly from the computations done by the |
| 164 |
library, which uses |fpu| for its computations, but from the aftermath. Many of |
| 165 |
these problems can be avoided by using the |fpu| library also for computing |
| 166 |
reciprocals, which can be achieved using the key |
| 167 |
|/pgf/fpu/install only={reciprocal}|. This allows one to fix many |
| 168 |
|Dimension too large| errors in other libraries, which are not related to the |
| 169 |
present one, and also fixes inaccuracies of (inverse) transformations when the |
| 170 |
scale factors are not integer. |
| 171 |
\end{enumerate} |
| 172 |
|
| 173 |
\subsection{Reporting a bug} |
| 174 |
|
| 175 |
This library is maintained at the GitHub repository |
| 176 |
\href{https://github.com/marmotghost/tikz-bbox}{tikz-bbox}, where issues can get |
| 177 |
reported. The author is also active on the noncommercial \TeX\ Q\,\&\,A site |
| 178 |
\href{https://topanswers.xyz/tex}{topanswers.xyz/tex}, where requests that are not |
| 179 |
issues in the strict sense can be discussed. |
| 180 |
|
| 181 |
\endinput |