diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/hobby/hobby_doc.tex')
| -rw-r--r-- | Master/texmf-dist/doc/latex/hobby/hobby_doc.tex | 646 |
1 files changed, 646 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/hobby/hobby_doc.tex b/Master/texmf-dist/doc/latex/hobby/hobby_doc.tex new file mode 100644 index 00000000000..073c9d8c32b --- /dev/null +++ b/Master/texmf-dist/doc/latex/hobby/hobby_doc.tex @@ -0,0 +1,646 @@ +\immediate\write18{tex hobby.dtx} +\documentclass{ltxdoc} +\usepackage[T1]{fontenc} +\usepackage{csquotes} +\usepackage{lmodern} +\usepackage{tikz} +\usepackage{amsmath} +\usepackage{fancyvrb} +\usetikzlibrary{hobby,decorations.pathreplacing} +\usepackage[margin=3cm]{geometry} +\EnableCrossrefs +\CodelineIndex +\RecordChanges + +\tikzset{ + show curve controls/.style={ + decoration={ + show path construction, + curveto code={ + \draw [blue, dashed] + (\tikzinputsegmentfirst) -- (\tikzinputsegmentsupporta) + node [at end, draw, solid, red, inner sep=2pt]{}; + \draw [blue, dashed] + (\tikzinputsegmentsupportb) -- (\tikzinputsegmentlast) + node [at start, draw, solid, red, inner sep=2pt]{}; + } + },decorate + }, +} + + +%\bibliographystyle{plain} + + +\providecommand*{\url}{\texttt} +\title{The \textsf{Hobby} package} +\author{Andrew Stacey \\ \url{stacey@math.ntnu.no}} +\begin{document} +\maketitle + +\section{Introduction} + +John Hobby's algorithm, \cite{MR834054}, produces a curve through a given set of points. +The curve is constructed as a list of cubic B\'ezier curves with endpoints at subsequent points in the list. +The parameters of the curves are chosen so that the joins are ``smooth''. +The algorithm was devised as part of the MetaPost program. + +TikZ/PGF has the ability to draw a curve through a given set of points but its algorithm is somewhat simpler than Hobby's and consequently does not produce as aesthetically pleasing curve as Hobby's algorithm does. +This package implements Hobby's algorithm in \TeX{} so that TikZ/PGF can make use of it and thus produce nicer curves through a given set of points. + +Hobby's algorithm allows for considerable customisation in that it can take into account various parameters. +These are all allowed in this implementation. + +There is also a ``quick'' version presented here. +This is a modification of Hobby's algorithm with the feature that any point only influences a finite number (in fact, two) of the previous segments (in Hobby's algorithm the influence of a point dies out exponentially but never completely). +This is achieved by applying Hobby's algorithm to subpaths. +As this is intended as a simpler method, it does not (at present) admit the same level of customisation as the full implementation. + +The full algorithm is implemented in \LaTeX3 and makes extensive use of the \Verb+fp+ and \Verb+prop+ libraries for the computation steps. +The ``quick'' version does not use \LaTeX3 and relies instead on the \Verb+PGFMath+ library for the computation. + +Figure~\ref{fig:comparison} is a comparison of the three methods. +The red curve is drawn using Hobby's algorithm. +The blue curve is drawn with the \Verb+plot[smooth]+ method from TikZ/PGF. +The green curve uses the ``quick'' version. + +\begin{figure} +\centering +\begin{tikzpicture}[scale=.5] +\draw[red,line width=5pt] (0,0) to[curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\draw[ultra thick,blue] plot[smooth] coordinates {(0,0) (6,4) (4,9) (1,7) (3,5)}; +\draw[green,line width=2pt] (0,0) to[quick curve through={(6,4) (4,9) (1,7)}] (3,5); +\end{tikzpicture} +\caption{Comparison of the three algorithms} +\label{fig:comparison} +\end{figure} + + +\begin{figure} +\centering +\begin{tikzpicture}[scale=.5] +\draw[scale=.1,postaction=show curve controls,line width=1mm,red] (0,0) +.. controls (26.76463,-1.84543) and (51.4094,14.58441) .. (60,40) +.. controls (67.09875,61.00188) and (59.76253,84.57518) .. (40,90) +.. controls (25.35715,94.01947) and (10.48064,84.5022) .. (10,70) +.. controls (9.62895,58.80421) and (18.80421,49.62895) .. (30,50); +\fill[green] (0,0) circle[radius=2pt] +(6,4) circle[radius=2pt] +(4,9) circle[radius=2pt] +(1,7) circle[radius=2pt] +(3,5) circle[radius=2pt]; +\draw[postaction=show curve controls,thick] (0,0) to[curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\begin{scope}[xshift=10cm] +\draw[scale=.1,postaction=show curve controls,line width=1mm,red] (0,0) +.. controls (5.18756,-26.8353) and (60.36073,-18.40036) .. (60,40) +.. controls (59.87714,59.889) and (57.33896,81.64203) .. (40,90) +.. controls (22.39987,98.48387) and (4.72404,84.46368) .. (10,70) +.. controls (13.38637,60.7165) and (26.35591,59.1351) .. (30,50) +.. controls (39.19409,26.95198) and (-4.10555,21.23804) .. (0,0); % +\fill[green] (0,0) circle[radius=2pt] +(6,4) circle[radius=2pt] +(4,9) circle[radius=2pt] +(1,7) circle[radius=2pt] +(3,5) circle[radius=2pt]; +\draw[postaction=show curve controls,thick] (0,0) to[closed,curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\end{scope} +\end{tikzpicture} +\caption{Hobby's algorithm in TikZ overlaying the output of MetaPost} +\end{figure} +\section{Usage} +The package is provided in form of a TikZ library. +It can be loaded with +\begin{verbatim} +\usetikzlibrary{hobby} +\end{verbatim} +%% +The TikZ library installs a \Verb+to path+ which draws a smooth curve through the given points: +%% +\begin{verbatim} +\begin{tikzpicture} +\draw (0,0) to[curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[scale=.5] +\draw (0,0) to[curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\end{tikzpicture} +\end{center} +The path can be open, as above, or closed: +%% +\begin{verbatim} +\begin{tikzpicture} +\draw (0,0) to[closed,curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[scale=.5] +\draw (0,0) to[closed,curve through={(6,4) .. (4,9) .. (1,7)}] (3,5); +\end{tikzpicture} +\end{center} + +There is also the facility to subvert TikZ's path processor and define curves simply using the \Verb+..+ separator between points. +Note that this relies on something a little special in TikZ: the syntax \Verb+(0,0) .. (2,3)+ is currently detected and processed but there is no action assigned to that syntax. +As a later version of TikZ may assign some action to that syntax, this package makes its override optional via the key \Verb+use Hobby shortcut+. +\begin{verbatim} +\begin{tikzpicture}[use Hobby shortcut] +\draw (-3,0) -- (0,0) .. (6,4) .. (4,9) .. (1,7) .. (3,5) -- ++(2,0); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[scale=.5,use Hobby shortcut] +\draw (-3,0) -- (0,0) .. (6,4) .. (4,9) .. (1,7) .. (3,5) -- ++(2,0); +\end{tikzpicture} +\end{center} +The algorithm can deal with open or closed paths, it is possible to vary the ``tensions'' between the specified points of the paths, and for an open path it is possible to specify the incoming and outgoing angles either directly or via certain ``curl'' parameters. +See the Examples section for more examples. +The algorithm is actually implemented in \LaTeX3 with (almost\footnote{At the moment, \LaTeX3 lacks a \Verb+atan2+ function so \Verb+PGFMath+ is used to remedy that.}) no reference to TikZ or PGF. +The TikZ library is simply a wrapper that takes the user's input, converts it into the right format for the \LaTeX3 code, and then calls that code to generate the path. +There is also a ``quick'' version of Hobby's algorithm. +This is described in Section~\ref{sec:quick}. +The reason for this modification of Hobby's algorithm was to find a variant in which adding more points does not change the path between earlier points (or rather that there is some point earlier than which the path is not changed). +The resulting path produced with this ``quick'' version is not as ideal as that produced by Hobby's full algorithm, but is still much better than that produced by the \Verb+plot[smooth]+ method in TikZ/PGF, as can be seen in Figure~\ref{fig:comparison}. + +\section{Examples} + +\begin{itemize} +\item Basic curve. +\begin{verbatim} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. (2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. (2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{center} +\item Specifying the angle at which the curve goes \emph{out} and at which it comes \emph{in}. +The angles given are absolute. +\begin{verbatim} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[out angle=0,in angle=180,curve through={(1,.5) .. (2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[out angle=0,in angle=180,curve through={(1,.5) .. (2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{center} +\item Applying tension as the curve comes in to a point. +\begin{verbatim} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. ([tension in=2]2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. ([tension in=2]2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{center} +\item Applying the same tension as a curve comes in and goes out of a point. +\begin{verbatim} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. ([tension=2]2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture} +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. ([tension=2]2,0) .. (3,.5)}] (4,0); +\end{tikzpicture} +\end{center} +\item Specifying the \emph{curl} parameters (if using the shortcut, these have to be passed via one of the points but obviously apply to the whole curve). +\begin{verbatim} +\begin{tikzpicture}[use Hobby shortcut] +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. (2,0) .. (3,.5)},in curl=.1,out curl=3] (4,0); +\begin{scope}[yshift=-1cm] +\draw[postaction=show curve controls] +(0,0) .. ([in curl=.1,out curl=3]1,.5) .. (2,0) .. (3,.5) .. (4,0); +\end{scope} +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[use Hobby shortcut] +\draw[postaction=show curve controls] +(0,0) to[curve through={(1,.5) .. (2,0) .. (3,.5)},in curl=.1,out curl=3] (4,0); +\begin{scope}[yshift=-1cm] +\draw[postaction=show curve controls] +(0,0) .. ([in curl=.1,out curl=3]1,.5) .. (2,0) .. (3,.5) .. (4,0); +\end{scope} +\end{tikzpicture} +\end{center} +\item Closed curve. +\begin{verbatim} +\begin{tikzpicture}[scale=.5,use Hobby shortcut] +\draw (0,0) .. (6,4) .. (4,9) .. (1,7) .. (3,5) .. cycle; +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[scale=.5,use Hobby shortcut] +\draw (0,0) .. (6,4) .. (4,9) .. (1,7) .. (3,5) .. cycle; +\end{tikzpicture} +\end{center} +\end{itemize} + +\section{Edge Cases} +Angles are constrained to lie in the interval \((-\pi,\pi]\). +This can introduce edge cases as there is a point where we have to compare an angle with \(-\pi\) and if it is equal, add \(2 \pi\). +This will occur if the path ``doubles back'' on itself as in the next example. +By nudging the repeated point slightly, the behaviour changes drastically. +\begin{verbatim} +\begin{tikzpicture}[use Hobby shortcut] +\draw (0,0) .. (1,0) .. (0,0) .. (0,-1); +\draw[xshift=2cm] (0,0) .. (1,0) .. (0,0.1) .. (0,-1); +\draw[xshift=4cm] (0,0) .. (1,0) .. (0,-0.1) .. (0,-1); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[use Hobby shortcut] +\draw (0,0) .. (1,0) .. (0,0) .. (0,-1); +\draw[xshift=2cm] (0,0) .. (1,0) .. (0,0.1) .. (0,-1); +\draw[xshift=4cm] (0,0) .. (1,0) .. (0,-0.1) .. (0,-1); +\end{tikzpicture} +\end{center} +Due to the precision of the computations, it is not possible to always get this test correct. +The simplest solution is to nudge the repeated point in one direction or the other. +Experimenting shows that the ``nudge factor'' can be extremely small (note that it will be proportional to the distance between the specified points). +It is best to nudge it in the direction most normal to the line between the specified points as the goal is to nudge the difference of the angles. +An alternative solution is to add an additional point for the curve to go through. +\begin{verbatim} +\begin{tikzpicture}[use Hobby shortcut] +\draw (0,0) .. (1,0) .. (0,0) .. (0,-1); +\draw[xshift=2cm] (0,0) .. (1,0) .. (0,0.002) .. (0,-1); +\draw[xshift=4cm] (0,0) .. (1,0) .. (0,-0.002) .. (0,-1); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[use Hobby shortcut] +\draw (0,0) .. (1,0) .. (0,0) .. (0,-1); +\draw[xshift=2cm] (0,0) .. (1,0) .. (0,0.002) .. (0,-1); +\draw[xshift=4cm] (0,0) .. (1,0) .. (0,-0.002) .. (0,-1); +\end{tikzpicture} +\end{center} +Lastly, it is possible to add an \Verb+excess angle+ key to a coordinate. +This will add the corresponding multiple of \(2\pi\) to the angle difference. +\begin{verbatim} +\begin{tikzpicture}[use Hobby shortcut] +\draw (0,0) .. (1,0) .. (0,0) .. (0,-1); +\draw[xshift=2cm] (0,0) .. ([excess angle=1]1,0) .. (0,0) .. (0,-1); +\draw[xshift=4cm] (0,0) .. ([excess angle=-1]1,0) .. (0,0) .. (0,-1); +\end{tikzpicture} +\end{verbatim} +\begin{center} +\begin{tikzpicture}[use Hobby shortcut] +\draw (0,0) .. (1,0) .. (0,0) .. (0,-1); +\draw[xshift=2cm] (0,0) .. ([excess angle=1]1,0) .. (0,0) .. (0,-1); +\draw[xshift=4cm] (0,0) .. ([excess angle=-1]1,0) .. (0,0) .. (0,-1); +\end{tikzpicture} +\end{center} +Although this is intended to be an integer, no check is done and so some quite odd curves can result from changing this parameter. + +\section{Implementing Hobby's Algorithm} +We start with a list of \(n+1\) points, \(z_0, \dotsc, z_n\). +The base code assumes that these are already stored in two arrays\footnote{Arrays are thinly disguised property lists}: the \(x\)--coordinates in \Verb+\l_hobby_points_x_array+ and the \(y\)--coordinates in \Verb+\l_hobby_points_y_array+. +As our arrays are \(0\)--indexed, the actual number of points is one more than this. +For a closed curve, we have \(z_n = z_0\)\footnote{Note that there is a difference between a closed curve and an open curve whose endpoints happen to overlap}. +For closed curves it will be convenient to add an additional point at \(z_1\): thus \(z_{n+1} = z_1\). +This makes \(z_n\) an internal point and makes the algorithms for closed paths and open paths agree longer than they would otherwise. +The number of apparent points is stored as \Verb+\l_hobby_npoints_int+. +Thus for an open path, \Verb+\l_hobby_npoints_int+ is \(n\), whilst for a closed path, it is \(n+1\)\footnote{In fact, we allow for the case where the user specifies a closed path but with \(z_n \ne z_0\). +In that case, we assume that the user meant to repeat \(z_0\). +This adds another point to the list.}. +Following Hobby, let us write \(n'\) for \(n\) if the path is open and \(n+1\) if closed. +From this we compute the distances and angles between successive points, storing these again as arrays. +These are \Verb+\l_hobby_distances_array+ and \Verb+\l_hobby_angles_array+. +The term indexed by \(k\) is the distance (or angle) of the line between the \(k\)th point and the \(k+1\)th point. +For the internal nodes\footnote{Hobby calls the specified points \emph{knots}}, we store the difference in the angles in \Verb+\l_hobby_psi_array+. +The \(k\)th value on this is the angle subtended at the \(k\)th node. +This is thus indexed from \(1\) to \(n'-1\). +The bulk of the work consists in setting up a linear system to compute the angles of the control points. +At a node, say \(z_i\), we have various pieces of information: +\begin{enumerate} +\item The angle of the incoming curve, \(\phi_i\), relative to the straight line from \(z_{i-1}\) to \(z_i\) +\item The angle of the outgoing curve, \(\theta_i\), relative to the straight line from \(z_i\) to \(z_{i+1}\) +\item The tension of the incoming curve, \(\overline{\tau}_i\) +\item The tension of the outgoing curve, \(\tau_i\) +\item The speed of the incoming curve, \(\sigma_i\) +\item The speed of the outgoing curve, \(\rho_i\) +\end{enumerate} +The tensions are known at the start. +The speeds are computed from the angles. +Thus the key thing to compute is the angles. +This is done by imposing a ``mock curvature'' condition.% +The formula for the mock curvature is: +%% +\[ +\hat{k}(\theta,\phi,\tau,\overline{\tau}) = \tau^2 \left( \frac{2(\theta + \phi)}{\overline{\tau}} - 6\theta\right) +\] +%% +and the condition that the mock curvatures have to satisfy is that at each \emph{internal} node, the curvatures must match: +% +\[ +\hat{k}(\phi_i,\theta_{i-1},\overline{\tau}_i,\tau_{i-1})/d_{i-1} = \hat{k}(\theta_i,\phi_{i+1},\tau_i,\overline{\tau}_{i+1})/d_i. +\] +%% +Substituting in yields: +%% +\[ +\frac{\overline{\tau}_i^2}{d_{i-1}} \left( \frac{2(\phi_i + \theta_{i-1})}{\tau_{i-1}} - 6\phi_i\right) = \frac{\tau_i^2}{d_i} \left( \frac{2(\theta_i + \phi_{i+1})}{\overline{\tau}_{i+1}} - 6\theta_i \right). +\] +%% +Let us rearrange that to the following: +%% +\begin{align*} +d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 &\theta_{i-1} \\ +%% ++ +d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (1 - 3 \tau_{i-1}) &\phi_i \\ +%% +- +d_{i-1} \tau_{i-1} \tau_i^2 (1 - 3 \overline{\tau}_{i+1}) &\theta_i \\ +%% +- +d_{i-1} \tau_{i-1} \tau_i^2 &\phi_{i+1} \\ +%% += +0 +\end{align*} +%% +For both open and closed paths this holds for \(i=1\) to \(i=n' - 1\). +We also have the condition that \(\theta_i + \phi_i = -\psi_i\) where \(\psi_i\) is the angle subtended at a node by the lines to the adjacent nodes. +This holds for the internal nodes\footnote{Recall that by dint of repetition, all nodes are effectively internal for a closed path}. +Therefore for \(i=1\) to \(n'-1\) the above simplifies to the following: +% +\begin{align*} +d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 &\theta_{i-1} \\ ++ +(d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (3 \tau_{i-1} - 1) ++ +d_{i-1} \tau_{i-1} \tau_i^2 (3 \overline{\tau}_{i+1} - 1)) &\theta_i \\ ++ +d_{i-1} \tau_{i-1} \tau_i^2 & \theta_{i+1} \\ += +- d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (3 \tau_{i-1} - 1) &\psi_i \\ +- d_{i-1} \tau_{i-1} \tau_i^2& \psi_{i+1} +\end{align*} +For an open path we have two more equations. +One involves \(\theta_0\). +The other is the above for \(i = n'-1 = n-1\) with additional information regarding \(\psi_n\). +It may be that one or either of \(\theta_0\) or \(\phi_n\) is specified in advance. +If so, we shall write the given values with a bar: \(\overline{\theta}_0\) and \(\overline{\phi}_n\). +In that case, the first equation is simply setting \(\theta_0\) to that value and the last equation involves substituting the value for \(\phi_n\) into the above. +If not, they are given by formulae involving ``curl'' parameters \(\chi_0\) and \(\chi_n\) and result in the equations: +% +\begin{align*} +\theta_0 &= \frac{\tau_0^3 + \chi_0 \overline{\tau}_1^3(3 \tau_0 - 1)}{\tau_0^3(3 \overline{\tau}_1 - 1) + \chi_0 \overline{\tau}_1^3} \phi_1 \\ +\phi_n &= \frac{\overline{\tau}_n^3 + \chi_n \tau_{n-1}^3(3 \overline{\tau}_n - 1)}{\overline{\tau}_n^3(3 \tau_{n-1} - 1) + \chi_n \tau_{n-1}^3} \theta_{n-1} +\end{align*} +%% +Using \(\phi_1 = - \psi_1 - \theta_1\), the first rearranges to: +%% +\[ +(\tau_0^3(3 \overline{\tau}_1 - 1) + \chi_0 \overline{\tau}_1^3) \theta_0 + (\tau_0^3 + \chi_0 \overline{\tau}_1^3(3 \tau_0 - 1)) \theta_1 = - (\tau_0^3 + \chi_0 \overline{\tau}_1^3(3 \tau_0 - 1)) \psi_1. +\] +%% +The second should be substituted in to the general equation with \(i = n-1\). +This yields: +%% +\begin{align*} +d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 &\theta_{n-2} \\ ++ +(d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 (3 \tau_{n-2} - 1) ++ +d_{n-2} \tau_{n-2} \tau_{n-1}^2 (3 \overline{\tau}_{n} - 1) \\ +- d_{n-2} \tau_{n-2} \tau_{n-1}^2 \frac{\overline{\tau}_n^3 + \chi_n \tau_{n-1}^3(3 \overline{\tau}_n - 1)}{\overline{\tau}_n^3(3 \tau_{n-1} - 1) + \chi_n \tau_{n-1}^3}) & \theta_{n-1} \\ += +- d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 (3 \tau_{n-2} - 1) &\psi_{n-1} +\end{align*} +%% +This gives \(n'\) equations in \(n'\) unknowns (\(\theta_0\) to \(\theta_{n-1}\)). +The coefficient matrix is tridiagonal. +It is more natural to index the entries from \(0\). +Let us write \(A_i\) for the subdiagonal, \(B_i\) for the main diagonal, and \(C_i\) for the superdiagonal. +Let us write \(D_i\) for the target vector. +Then for an open path we have the following formulae: +%% +\begin{align*} +A_i &= d_i \overline{\tau}_{i+1} \overline{\tau}^2_i \\ +B_0 &= \begin{cases} +1 & \text{if}\; \overline{\theta}_0\; \text{given} \\ +\tau_0^3(3 \overline{\tau}_1 - 1) + \chi_0 \overline{\tau}^3_1 & \text{otherwise} +\end{cases} \\ +B_i &= d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (3 \tau_{i-1} -1) + d_{i-1} \tau_{i-1} \tau_i^2(3 \overline{\tau}_{i+1} - 1) \\ +B_{n-1} &= \begin{cases} d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 (3 \tau_{n-2} - 1) + d_{n-2} \tau_{n-2} \tau_{n-1}^2(3 \overline{\tau}_{n} - 1) & \text{if}\; \overline{\phi}_n\; \text{given} \\ +d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 (3 \tau_{n-2} - 1) + d_{n-2} \tau_{n-2} \tau_{n-1}^2(3 \overline{\tau}_{n} - 1) +\\ +- d_{n-2} \tau_{n-2} \tau_{n-1}^2 \frac{\overline{\tau}_n^3 + \chi_n \tau_{n-1}^3(3 \overline{\tau}_n - 1)}{\overline{\tau}_n^3(3 \tau_{n-1} - 1) + \chi_n \tau_{n-1}^3}) & \text{otherwise} +\end{cases} \\ +C_0 &= \begin{cases} +0 & \text{if}\; \overline{\theta}_0\; \text{given} \\ +\tau_0^3 + \chi_0 \overline{\tau}_1^3(3\tau_0 - 1) & \text{otherwise} +\end{cases} \\ +C_i &= d_{i-1} \tau_{i-1} \tau_i^2 \\ +D_0 &= \begin{cases} +\overline{\theta}_0 & \text{if}\; \overline{\theta}_0\; \text{given} \\ +- (\tau_0^3 + \chi_0 \overline{\tau}_1^3(3 \tau_0 - 1)) \psi_1 & \text{otherwise} +\end{cases} \\ +D_i &= - d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (3 \tau_{i-1} - 1) \psi_i +- d_{i-1} \tau_{i-1} \tau_i^2 \psi_{i+1} \\ +D_{n-1} &= \begin{cases} +- d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 (3 \tau_{n-2} - 1) \psi_{n-1} - d_{n-2} \tau_{n-2} \tau_{n-1}^2 \overline{\phi}_n & \text{if}\; \overline{\phi}_n\; \text{given} \\ +- d_{n-1} \overline{\tau}_{n} \overline{\tau}_{n-1}^2 (3 \tau_{n-2} - 1) \psi_{n-1} & \text{otherwise} +\end{cases} +\end{align*} +For a closed path, we have \(n\) equations in \(n+2\) unknowns (\(\theta_0\) to \(\theta_{n+1}\)). +However, we have not included all the information. +Since we have repeated points, we need to identify \(\theta_0\) with \(\theta_n\) and \(\theta_1\) with \(\theta_{n+1}\). +To get a system with \(n'\) equations in \(n'\) unknowns, we add the equation \(\theta_0 - \theta_n = 0\) and substitute in \(\theta_{n+1} = \theta_1\). +The resulting matrix is not quite tridiagonal but has extra entries on the off-corners. +However, it can be written in the form \(M + u v^\top\) with \(M\) tridiagonal. +There is some freedom in choosing \(u\) and \(v\). +For simplest computation, we take \(u = e_0 + e_{n'-1}\). +This means that \(v = d_{n'-2} \tau_{n'-2} \tau_{n'-1}^2 e_1 - e_{n'-1}\). +With the same notation as above, the matrix \(M\) is given by the following formulae: +%% +\begin{align*} +A_i &= d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 \\ +%% +B_0 &= 1 \\ +%% +B_i &= d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (3 \tau_{i-1} -1) + d_{i-1} \tau_{i-1} \tau_i^2(3 \overline{\tau}_{i+1} - 1) \\ +%% +B_{n'-1} &= d_{n'-1} \overline{\tau}_{n'} \overline{\tau}_{n'-1}^2 (3 \tau_{n'-2} -1) + d_{n'-2} \tau_{n'-2} \tau_{n'-1}^2(3 \overline{\tau}_{n'} - 1) + 1\\ +%% +C_0 &= - d_{n'-2} \tau_{n'-2} \tau_{n'-1}^2 \\ +%% +C_i &= d_{i-1} \tau_{i-1} \tau_i^2 \\ +%% +D_0 &= 0 \\ +%% +D_i &= - d_i \overline{\tau}_{i+1} \overline{\tau}_i^2 (3 \tau_{i-1} - 1) \psi_i +- d_{i-1} \tau_{i-1} \tau_i^2 \psi_{i+1} \\ +%% +D_{n'-1} &= - d_{n'-1} \overline{\tau}_{n'} \overline{\tau}_{n'-1}^2 (3 \tau_{n'-2} - 1) \psi_{n'-1} +- d_{n'-2} \tau_{n'-2} \tau_{n'-1}^2 \psi_1 +\end{align*} +The next step in the implementation is to compute these coefficients and store them in appropriate arrays. +Having done that, we need to solve the resulting tridiagonal system. +This is done by looping through the arrays doing the following substitutions (starting at \(i = 1\)): +% +\begin{align*} +B_i' &= B_{i-1}' B_i - A_i C_{i-1}' \\ +C_i' &= B_{i-1}' C_i \\ +D_i' &= B_{i-1}' D_i - A_i D_{i-1}' +\end{align*} +%% +followed by back-substitution: +%% +\begin{align*} +\theta_{n-1} &= D_{n-1}'/B_{n-1}' \\ +\theta_i &= (D_i' - C_i' \theta_{i+1})/B_i' +\end{align*} +%% +For a closed path, we run this both with the vector \(D\) and the vector \(u = e_0 + e_{n'-1}\). +Then to get the real answer, we use the Sherman--{}Morrison formula: +%% +\[ +(M + u v^\top)^{-1} D = M^{-1} D - \frac{M^{-1} u v^\top M^{-1} D}{1 + v^\top M^{-1} u}. +\] +%% +This leaves us with the values for \(\theta_i\). +We now substitute these into Hobby's formulae for the lengths: +%% +\begin{align*} +\rho_i &= \frac{2 + \alpha_i}{1 + (1 - c) \cos \theta_i + c \cos \phi_{i+1}} \\ +\sigma_{i+1} &= \frac{2 - \alpha_i}{1 + (1 - c) \cos \phi_{i+1} + c \cos \theta_i} \\ +\alpha_i &= a (\sin \theta_i - b \sin \phi_{i+1})(\sin \phi_{i+1} - b \sin \theta_i)(\cos \theta_i - \cos \phi_{i+1}) +\end{align*} +%% +where \(a = \sqrt{2}\), \(b = 1/16\), and \(c = (3 - \sqrt{5})/2\). +These are actually the \emph{relative} lengths so need to be adjusted by a factor of \(d_i/3\). +Now \(\theta_i\) is the angle relative to the line from \(z_i\) to \(z_{i+1}\), so to get the true angle we need to add back that angle. +Fortunately, we stored those angles at the start. +So the control points are: +%% +\begin{gather*} +d_i \rho_i (\cos (\theta_i + \omega_i), \sin (\omega_{i+1} - \phi_{i+1}))/3 + z_i \\ +- d_i \sigma_{i+1} (\cos(\omega_{i+1} - \phi_{i+1}), \sin(\theta_i + \omega_i))/3 + z_{i+1} +\end{gather*} + +\section{A Piecewise Version of Hobby's Algorithm} +\label{sec:quick} +Here we present a variant of Hobby's algorithm. +One difficulty with Hobby's algorithm is that it works with the path as a whole. +It is therefore not possible to build up a path piecewise. +We therefore modify it to correct for this. +Obviously, the resulting path will be less ``ideal'', but will have the property that adding new points will not affect earlier segments. +The method we use is to employ Hobby's algorithm on the two-{}segment subpaths. +This provides two cubic Bezier curves: one from the \(k\)th point to the \(k+1\)st point and the second from the \(k+1\)st to the \(k+2\)nd. +Of this data, we keep the first segment and use that for the path between the \(k\)th and \(k+1\)st points. +We also remember the outgoing angle of the first segment and use that as the incoming angle on the next computation (which will involve the \(k+1\)st, \(k+2\)nd, and \(k+3\)rd) points. +The two ends are slightly different to the middle segments. +On the first segment, we might have no incoming angle. +On the last segment, we render both pieces. +This means that for the initial segment, we have a \(2 \times 2\) linear system: +%% +\[ +\begin{bmatrix} +B_0 & C_0 \\ +A_1 & B_1 +\end{bmatrix} +\Theta = \begin{bmatrix} +D_0 \\ D_1 +\end{bmatrix} +\] +%% +This has solution: +%% +\[ +\Theta = \frac{1}{B_0 B_1 - C_0 A_1} \begin{bmatrix} B_1 & - C_0 \\ -A_1 & B_0 \end{bmatrix} \begin{bmatrix} D_0 \\ D_1 \end{bmatrix} = \frac{1}{B_0 B_1 - C_0 A_1} \begin{bmatrix} B_1 D_0 - C_0 D_1 \\ B_0 D_1 - A_1 D_0 \end{bmatrix} +\] +Now we have the following values for the constants: +%% +\begin{align*} +A_1 &= d_1 \overline{\tau}_2 \overline{\tau}_1^2 \\ +%% +B_0 &= \tau_0^3 (3 \overline{\tau}_1 - 1) + \chi_0 \overline{\tau}_1^3 \\ +%% +B_1 &= d_1 \overline{\tau}_2 \overline{\tau}_1^2 (3 \tau_0 - 1) + d_0 \tau_0 \tau_1^2(3 \overline{\tau}_2 - 1) - d_0 \tau_0 \tau_1^2 \frac{\overline{\tau}_2^3 + \chi_2 \tau_1^3 (3 \overline{\tau}_2 - 1)}{\overline{\tau}_2^3 (3 \tau_1 - 1) + \chi_2 \tau_1^3} \\ +%% +C_0 &= \tau_0^3 + \chi_0 \overline{\tau}_1^3 (3 \tau_0 - 1) \\ +%% +D_0 &= - (\tau_0^3 + \chi_0 \overline{\tau}_1^3 ( 3 \tau_0 - 1)) \psi_1 \\ +%% +D_1 &= - d_1 \overline{\tau}_2 \overline{\tau}_1^2 (3 \tau_0 - 1) \psi_1 +\end{align*} + +Let us, as we are aiming for simplicity, assume that the tensions and curls are all \(1\). +Then we have \(A_1 = d_1\), \(B_0 = 3\), \(B_1 = 2 d_1 + 2 d_0 - d_0 = 2 d_1 + d_0\), \(C_0 = 3\), \(D_0 = - 3 \psi_1\), \(D_1 = - 2 d_1 \psi_1\). +Thus the linear system is: +%% +\[ +\begin{bmatrix} +3 & 3 \\ +d_1 & 2 d_1 + d_0 +\end{bmatrix} +\Theta = - \psi_1 \begin{bmatrix} +3 \\ 2 d_1 +\end{bmatrix} +\] +%% +which we can row reduce to: +%% +\[ +\begin{bmatrix} +1 & 1 \\ +0 & d_1 + d_0 +\end{bmatrix} +\Theta = -\psi_1 \begin{bmatrix} +1 \\ d_1 +\end{bmatrix} +\] +%% +whence \(\theta_1 = -\psi_1 \frac{d_1}{d_0 + d_1}\) and \(\theta_0 = -\psi_1 - \theta_1 = -\psi_1\frac{d_0 }{d_0 + d_1}\). +We also compute \(\phi_1 = -\psi_1 - \theta_1 = \theta_0\) and \(\phi_2 = \theta_1\) (in the simple version). +We use \(\theta_0\) and \(\phi_1\) to compute the bezier curve of the first segment, make a note of \(\theta_1\), and -- assuming there are more segments -- throw away \(\phi_2\). + +For the inner segments, we have the system: +%% +\[ +\begin{bmatrix} +1 & 0 \\ +A_1 & B_1 +\end{bmatrix} +\Theta = \begin{bmatrix} +\theta_0 \\ +D_1 +\end{bmatrix} +\] +%% +which has the solution \(\theta_1 = (D_1 - A_1 \theta_0)/B_1\). +The values of the constants in this case are: +%% +\begin{align*} +A_1 &= d_1 \overline{\tau}_2 \overline{\tau}_1^2 \\ +%% +B_1 &= d_1 \overline{\tau}_2 \overline{\tau}_1^2 (3 \tau_0 - 1) + d_0 \tau_0 \tau_1^2(3 \overline{\tau}_2 - 1) - d_0 \tau_0 \tau_1^2 \frac{\overline{\tau}_2^3 + \chi_2 \tau_1^3 (3 \overline{\tau}_2 - 1)}{\overline{\tau}_2^3 (3 \tau_1 - 1) + \chi_2 \tau_1^3} \\ +%% +D_1 &= - d_1 \overline{\tau}_2 \overline{\tau}_1^2 (3 \tau_0 - 1) \psi_1 +\end{align*} +Again, let us consider the simpler case. +Then \(A_1 = d_1\), \(B_1 = 2 d_1 + d_0\), and \(D_1 = - 2 d_1 \psi_1\). +Thus \(\theta_1 = (-2 d_1 \psi_1 - d_1 \theta_0)/(2 d_1 + d_0) = - (2 \psi_1 + \theta_0) \frac{d_1}{2 d_1 + d_0}\). +We compute \(\phi_1 = -\psi_1 - \theta_1 = \frac{- \psi_1 d_0 + \theta_0 d_1}{2 d_1 + d_0}\) and \(\phi_2 = \theta_1\). + +\begin{thebibliography}{1} \bibitem{MR834054} John~D. Hobby. \newblock Smooth, easy to compute interpolating splines. \newblock {\em Discrete Comput. Geom.}, 1:123--140, 1986. \end{thebibliography} + +\end{document} |