summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/hobby/hobby_doc.tex
blob: 073c9d8c32bcb935db6003fbb2b552dd3a59c6f1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
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}