new tikz package hobby (3sep12)

git-svn-id: svn://tug.org/texlive/trunk@27584 c570f23f-e606-0410-a88d-b1316a301751

3 files changed, 660 insertions, 0 deletions

diff --git a/Master/texmf-dist/doc/latex/hobby/README b/Master/texmf-dist/doc/latex/hobby/README
new file mode 100644
index 00000000000..d48c4b90e17
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/hobby/README
@@ -0,0 +1,14 @@
+----------------------------------------------------------------
+hobby --- a TikZ/PGF library for drawing smooth(ish) curves using
+          Hobby's algorithm (implemented in LaTeX3)
+E-mail: stacey@math.ntnu.no
+Released under the LaTeX Project Public License v1.3c or later
+See http://www.latex-project.org/lppl.txt
+----------------------------------------------------------------
+
+This package defines a path generation function for TikZ/PGF
+which implements Hobby's algorithm for a path built out of Bezier
+curves which passes through a given set of points.
+
+The implementation is in LaTeX3.  It can be used as as a TikZ
+`to path`.
diff --git a/Master/texmf-dist/doc/latex/hobby/hobby_doc.pdf b/Master/texmf-dist/doc/latex/hobby/hobby_doc.pdf
new file mode 100644
index 00000000000..3f17f5112bd
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/hobby/hobby_doc.pdf
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}