summaryrefslogtreecommitdiff
path: root/graphics/pgf/contrib/tikz-nfold/tikz-nfold-doc.tex
blob: 60b1d03202c09c827657303e97e1eac3c1ec56a8 (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
%% tikz-nfold.sty
%% Copyright 2023 Jonathan Schulz
%
% This work may be distributed and/or modified under the
% conditions of the LaTeX Project Public License, either version 1.3c
% of this license or (at your option) any later version.
% The latest version of this license is in
% http://www.latex-project.org/lppl.txt
% and version 1.3c or later is part of all distributions of LaTeX
% version 2008-05-04 or later.
%
% This work has the LPPL maintenance status 'maintained'.
%
% The Current Maintainer of this work is Jonathan Schulz.
%
% This work consists of the files pgflibrarybezieroffset.code.tex,
% tikzlibrarynfold.code.tex, tikz-nfold-doc.tex, and tikz-nfold-doc.pdf.


\documentclass[12pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usepackage{tkzexample}
\usetikzlibrary{calc}
\usetikzlibrary{nfold}
\usepackage{parskip}
\usepackage[margin=2.5cm]{geometry}

% recommended order: 1) hyperref 2) amsthm 3) cleveref 4) \newtheorem
\usepackage[colorlinks]{hyperref}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[capitalize]{cleveref}
\usepackage{datetime}
\usepackage{enumitem}

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

%\newcommand{\todo}[1]{{\color{red}\bfseries#1}}
\newcommand{\tikzdouble}{\texttt{/tikz/double}}
\newcommand{\nfold}{\texttt{nfold}}
\newcommand{\tikznfold}{\texttt{/tikz/nfold}}

\pgfkeys{/tkzexample/every tkzexample/.style={
    code=violet!15, graphic=orange!20, very small,above skip={\vskip1em},below skip={\vskip1em}
  }
}

\newcommand{\tv}{\vec{t}}
\newcommand{\uv}{\vec{u}}
\newcommand{\vv}{\vec{v}}

% to be used in pre=... to stop the proparation of warnings outside of tkzexample environments
\makeatletter
\def\disablewarnings{\def\pgfutil@packagewarning##1##2{}}
\makeatother

\begin{document}

\title{The \textsf{tikz-nfold} package}
\author{Jonathan Schulz}
\date{\monthname{} \the\year}

\maketitle

\begin{abstract}
  This package provides an alternative to TikZ' \verb|/tikz/double| option, avoiding some shortcomings of the original approach. Further features include options to draw triple, quadruple, and n-fold paths as well as macros to offset arbitrary paths.
\end{abstract}

\section*{Compatibility}
This package has been tested with \texttt{pdflatex}, \texttt{lualatex}, \texttt{xelatex}, and plain \texttt{pdftex}.

\section{Quick start}

Add
\begin{verbatim}
\usetikzlibrary{nfold}
\end{verbatim}
to your preamble. Now you can add \tikznfold{} to any path that uses \tikzdouble. Be sure to specify \verb|/tikz/double distance| before \tikznfold, as otherwise the latter will not be applied.
\begin{tkzexample}[latex=4cm]
\begin{tikzpicture}
  \draw[double distance=3pt]
    (0,2) to[out=0, in=180] (3,3);
  \draw[double distance=3pt, nfold]
    (0,0) to[out=0, in=180] (3,1);
  \node[right] at (0,3) {double:};
  \node[right] at (0,1) {nfold:};
\end{tikzpicture}
\end{tkzexample}
While it appears that adding \nfold{} does not do much here, it avoids some rendering issues of \tikzdouble, hence I recommend using it in most cases (see \cref{sec:doubleIssues} for details).
Specify a number for n-fold lines:
\begin{tkzexample}[latex=4cm]
\begin{tikzpicture}
  \draw[double distance=7pt, nfold=5]
    (0,0) to[out=0, in=180] (3,1) -- (3,0);
\end{tikzpicture}
\end{tkzexample}
All arrow tips are supported, and there is special treatment for the \texttt{Implies} tip:
\begin{tkzexample}[latex=4cm]
\begin{tikzpicture}
  \draw[double distance=7pt, nfold=5,
        arrows={Bar[width=18pt]-Implies[red]}]
    (0,1.5) to[bend left] (3,1.5);
  \draw[double distance=7pt, nfold=5, arrows=Implies-Implies]
    (0,0) to[bend left] (3,0);
\end{tikzpicture}
\end{tkzexample}
Use \texttt{/tikz/scaling nfold} to preserve the distance between component lines instead of the overall width of the arrow:
\begin{tkzexample}[latex=4cm,pre={\usetikzlibrary{intersections}}]
\begin{tikzpicture}
  \draw[double equal sign distance, nfold,
        arrows=-Implies] (0,.75) -- (3,.75);
  \draw[double equal sign distance, scaling nfold=4,
        arrows=-Implies] (0,0) -- (3,0);
  \draw[double equal sign distance, scaling nfold=6,
        arrows=-Implies] (0,-1) -- (3,-1);
\end{tikzpicture}
\end{tkzexample}
Different line joins are supported:
\begin{tkzexample}[latex=2cm]
\begin{tikzpicture}[line join=bevel]
  \draw[line join=miter, double distance=7pt, nfold=4]
    (0,2) -- (1, 2) -- (1,2.5);
  \draw[double distance=7pt, nfold=4]
    (0,1) -- (1, 1) -- (1,1.5);
  \draw[line join=round,  double distance=7pt, nfold=4]
    (0,0) -- (1, 0) -- (1,.5);
\end{tikzpicture}
\end{tkzexample}
There is also support for \texttt{tikz-cd} with custom label positions for \texttt{scaling nfold}:
\begin{tkzexample}[pre={\usetikzlibrary{cd}}, latex=3cm]
\begin{tikzcd}
  a \ar[r, Mapsto, bend left, scaling nfold=3] &
  b \ar[d, Rightarrow, nfold, "\alpha", "\beta"'] \\
  c \ar[r, Mapsfrom, scaling nfold=4, "\gamma" near end] &
  d
\end{tikzcd}
\end{tkzexample}


\section{Comparison to \tikzdouble}
\label{sec:doubleIssues}

This package does \emph{not} aim to supersede \tikzdouble, as both the original and the \nfold{} approach have their own strengths and weaknesses. The main difference is that \tikzdouble{} achieves its goal by drawing the original path twice, once very thick with the foreground colour and then slightly less thick with the background colour. By contrast, \nfold{} offsets the path:
\begin{equation}
  \label{eq:compareApproaches}
  \begin{tikzpicture}[baseline=.5cm]
    \fill[orange!20] (-4.5,-.5) rectangle (6, 1.5);
    \node[left] at (-1,1) {\tikzdouble:};
    \draw[line width=7pt] (0,1) -- (1,1);
    \node at (1.5,1) {+};
    \draw[white, line width=5pt] (2,1) -- (3,1);
    \node at (3.5,1) {=};
    \draw[double distance=5pt] (4,1) -- (5,1);
    \node[left] at (-1,0) {\tikznfold:};
    \draw (0, 3pt) -- (1, 3pt);
    \node at (1.5,0) {+};
    \draw (2, -3pt) -- (3, -3pt);
    \node at (3.5,0) {=};
    \draw[double distance=5pt, nfold] (4,0) -- (5,0);
  \end{tikzpicture}
\end{equation}
While the approach of \tikzdouble{} is very robust and efficient, it does have a few pitfalls:
\begin{itemize}[beginpenalty=10000]
  \item Different types of visual glitches can occur in PDF renderers:
  \begin{itemize}
    \item One common issue is that the white foreground piece completely covers the black background piece at certain zoom levels, leading to the top or bottom part of the doubled path missing (depending on your PDF viewer and zoom level, this issue might be visible in \cref{eq:compareApproaches}).
    \item Another common glitch is the appearance of a thin horizontal line at the start and end of the doubled path (visible in most examples of curved paths if your viewer has this problem). The reason is that the larger black path in the background is not perfectly covered by the smaller white foreground piece, most likely due to rounding errors.
  \end{itemize}
  \item The approach assumes that the background has a uniform colour, and it is the user's responsibility to correctly set the background colour:
\begin{tkzexample}[latex=3.5cm]
\begin{tikzpicture}
  \draw[red, line width=1pt] (2.5, 3.3) -- (2.5, 0);
  \draw[line width=2pt, double distance=3pt]
    (0,2) to[out=0, in=180] (3,3);
  \node[right] at (0,3) {double:};
  \draw[line width=2pt, double distance=3pt, nfold]
    (0,0) to[out=0, in=180] (3,1);
  \node[right] at (0,1) {nfold:};
\end{tikzpicture}
\end{tkzexample}
  \item Transparency does not work correctly:
\begin{tkzexample}[latex=3.5cm]
\begin{tikzpicture}[line width=1pt]
  \draw[double distance=3pt, opacity=.5]
    (0,2) to[out=0, in=180] (3,3);
  \draw[double distance=3pt, opacity=.5, nfold]
    (0,0) to[out=0, in=180] (3,1);
  \node[right] at (0,3) {double:};
  \node[right] at (0,1) {nfold:};
\end{tikzpicture}
\end{tkzexample}
  \item Triple and n-fold paths are not supported (although this could be implemented in principle).
\end{itemize}
However, there are still situations where \tikznfold{} struggles and \tikzdouble{} is the only viable option, which will be discussed in the next section.

\section{Known issues}

This package is by no means perfect, and even if it were, there would still be some cases where the approach of \tikzdouble{} is better suited. The known issues are roughly sorted into those that can be fixed in principle and the fundamental limitations of this approach. If you find any bugs not listed here, please report them \href{https://github.com/jonschz/tikz-nfold/issues/}{here}.

\subsection{Fixable / wish list}
\begin{itemize}
  \item \nfold{} is significantly slower than \tikzdouble. Part of the reason is that the construction is far more complex, but the code is also far from fully optimised.
  \item Some rare cases of curves are not offset correctly. The reasons for that are discussed below in \cref{subsec:subdivisionUsed}. Usually, slightly changing the control points or values of the curve will fix the problem. If you find any, please open an issue.
  \item Closed paths can glitch slightly when the final segment is very short and has non-zero angles on both ends.
\end{itemize}

\subsection{Impossible or very hard to fix}
\begin{itemize}
  \item \nfold{} struggles with high curvatures and wide paths: Let $\kappa(t)$ be the curvature of the path in a given point, and let $\texttt{double distance} = \alpha$. If $\kappa(t) > \frac{2}{\alpha}$ (i.e. the radius of the osculating circle is smaller than half the width of the path) for some $0 \leq t \leq 1$, the output of \nfold{} will not be correct:
\begin{tkzexample}[latex=4.25cm]
\begin{tikzpicture}
  \draw[double distance=5pt, line width=1pt]
    (0,2) .. controls (4,2) and (0,3) .. (3,2.5);
  \node[right] at (0,3) {double:};
  \draw[double distance=5pt, line width=1pt, nfold]
    (0,0) .. controls (4,0) and (0,1) .. (3,.5);
  \node[right] at (0,1) {nfold:};
\end{tikzpicture}
\end{tkzexample}
  Some, but not all of these cases raise warnings (this feature is on the wish list). This is one of the cases where using \tikzdouble{} is the only viable option.
  \item Dashed paths with significant curvature will desynchronise:
\begin{tkzexample}[latex=3cm]
\begin{tikzpicture}
  \draw[arrows=-Implies, double equal sign distance, dashed,
        scaling nfold=4] (0,0) to[out=30, in=150] (2,0);
\end{tikzpicture}
\end{tkzexample}
  \item Curves of \nfold{} slightly deviate from the curves of \tikzdouble{} near joins with a non-zero angle:
\begin{tkzexample}[latex=3.5cm]
\begin{tikzpicture}[line width=1pt]
  \draw[red, double distance=20pt]
    (0,2) -- (2,2) to [out=-90, in=0] (.5,.5);
  \draw[blue, double distance=20pt, opacity=.5, nfold]
    (0,2) -- (2,2) to [out=-90, in=0] (.5,.5);
  \node[right, red] at (0,3) {double};
  \node[left, blue] at (3, 3) {nfold};
\end{tikzpicture}
\end{tkzexample}
  This cannot be fixed without extensive use of the \texttt{intersections} library, hurting the performance, and the result might still not look great for orders $\geq 3$.
  \item Very short \emph{curves} with large angles at the ends result in a glitched output:\nopagebreak
\begin{tkzexample}[latex=3.75cm,pre=\disablewarnings]
\begin{tikzpicture}[line join=round]
  \draw[black] (1,0) -- (3,0) -- (1.5,1.2) -- (3.8,0.85);
  \draw[red, line width=1pt, double distance=.7cm, nfold]
    (1,0) -- (3,0) -- (1.5, 1.2) -- (3.8,0.85);
  \draw[blue, double distance=.7cm, nfold] (1,0) -- (3,0)
    to[relative, out=1, in=179] (1.5, 1.2) -- (3.8,0.85);
\end{tikzpicture}
\end{tkzexample}
  This issue has been fixed for \emph{straight} lines in version \texttt{0.1.0} (note how the red line is offset correctly), but it is much harder to fix for curves.
  \item Changing joins in \verb|\pgfsys@beginscope| without an accompanying \TeX{} group may cause inconsistent behaviour in the joins:
\begin{tkzexample}[latex=2cm]
\makeatletter
\begin{tikzpicture}[line join=miter, line width=2pt]
  \pgfsys@beginscope
    \pgfsetroundjoin
  \pgfsys@endscope
  \draw[double distance=5pt, nfold] (0,0) -- (.5,2) -- (1,0);
\end{tikzpicture}
\makeatother
\end{tkzexample}
  This example has \texttt{round} joins on the large path but \texttt{miter} joins on the constituent paths. This problem does not occur with \verb|\pgfscope|.
\end{itemize}


\section{The basic layer \texttt{pgf} commands}

\subsection{Offsetting curves}
This package provides some basic layer commands for offsetting curves and straight lines. Use
\begin{verbatim}
\usepgflibrary{bezieroffset}
\end{verbatim}
to only import the base layer library. The following commands are provided:
\begin{itemize}
  \item \verb|\pgfoffsetcurve{pt1}{pt2}{pt3}{pt4}{distance}|\\%
    This macro draws the parallel of a Bézier curve. The first four parameters are the control points of the Bézier curve (e.g.\ in the form of \verb|\pgfpoint{}{}|), the fifth parameter is the distance by which the curve should be offset. A negative value offsets the curve in the opposite direction. This macro begins with a \verb|\pgfpointmoveto| to the offset of \texttt{pt1}.
  \item \verb|\pgfoffsetcurvenomove{pt1}{pt2}{pt3}{pt4}{distance}|\\%
    The only difference to the previous macro is that this version does not move to the offset of \texttt{pt1}. This is useful if one wants to offset an uninterrupted path consisting of several curves. The output will only be correct if the previous \verb|\pgfpath...| call ends on the offset of \texttt{pt1}.
  \item \verb|\pgfoffsetline{pt1}{pt2}{distance}|\\%
    This macro offsets a straight line. It takes two points and the distance as parameters, and starts by moving to the offset of the first point.
  \item \verb|\pgfoffsetlinenomove{pt1}{pt2}{distance}|\\%
    This macro is analogous to \verb|\pgfoffsetcurvenomove|.
\end{itemize}

\subsection{Offsetting paths}
The following macros are part of the TikZ library \nfold{} and offset an entire soft path.
\begin{itemize}
  \item \verb|\pgfoffsetpath{softpath}{distance}|\\%
    This macro offsets \texttt{softpath} by \texttt{distance}. The latter may be negative.
  \item \verb|\pgfoffsetpathfraction{softpath}{hwidth}{fraction}|\\%
    This macro offsets \texttt{softpath} by \texttt{fraction*hwidth}. Note that this is \emph{not} equivalent to the previous macro with \texttt{length=fraction*hwidth} because the joins are treated differently, as can be seen in the examples below. Further note that \texttt{hwidth} must not be negative, and that \texttt{fraction=0} does \emph{not} reproduce the input path.
  \item \verb|\pgfoffsetpathqfraction{softpath}{hwidth}{fraction}|\\%
    This macro is a quicker version of the previous macro  does not parse the input values using the \texttt{pgfmath}-engine.
  \item \verb|\pgfoffsetpathindex{softpath}{width}{i}{n}|\\%
    In this convenience method, \texttt{i} and \texttt{n} are integers with $1 \leq i \leq n$. It calls the previous macro with \texttt{fraction=-1.0} for \texttt{i=1} and with \texttt{fraction=1.0} for \texttt{i=n} and is thus capable of reproducing the output of \texttt{/tikz/nfold=n} (albeit in a less efficient way).
\end{itemize}
In the following example we see how \verb|\pgfoffsetpath{..}{0pt}| reproduces the input path (rendered in black) and how \verb|\pgfoffsetpathfraction{..}{8pt}{0}| differs.
\begin{tkzexample}[latex=4cm]
\begin{tikzpicture}[line join=bevel]
  \path[save path=\savedpath] (0,0) -- (1,0)
    to[out=0, in=-80] (1,3) -- (3,2);
  \draw[color=lightgray,line width=16pt,use path=\savedpath];
  \pgfoffsetpathfraction{\savedpath}{8pt}{0}
  \pgfsetlinewidth{1pt} \color{red} \pgfusepathqstroke
  \pgfoffsetpath{\savedpath}{8pt}
  \color{blue} \pgfusepathqstroke
  \pgfoffsetpath{\savedpath}{-8pt}
  \color{green} \pgfusepathqstroke
  \pgfoffsetpath{\savedpath}{0pt}
  \pgfsetlinewidth{.4pt} \color{black} \pgfusepathqstroke
\end{tikzpicture}
\end{tkzexample}
Here we see how the commands can be used to customise $n$-fold paths:
\begin{tkzexample}[latex=4cm]
\begin{tikzpicture}
  \path[save path=\mypath] (0,0) -- (2,0) arc(-90:90:1)
    to[out=180, in=0] (0,1) -- (0,2);
  \foreach \mycolor [count=\i] in {red,green,blue,violet}
    \pgfoffsetpathindex{\mypath}{6pt}{\i}{4}
    \color{\mycolor} \pgfusepathqstroke;
\end{tikzpicture}
\end{tkzexample}


\newpage
\section{Version history}

\begin{itemize}
  \item \textbf{v0.1.1}: Closing paths and structural changes
  \begin{itemize}
    \item Support for closed paths (\texttt{cycle} and \verb|\pgfpathclose|)
    \item Significant performance improvements due to structural changes
    \item Minor bug fixes and optimisations
\end{itemize}
  \item \textbf{v0.1.0}: Major overhaul
  \begin{itemize}
    \item Support for arbitrary arrow tips
    \item Support for directly offsetting soft paths
    \item New key \texttt{/tikz/scaling nfold}
    \item The \texttt{decorations} library was dropped
    \item Various performance improvements in \texttt{bezieroffset} (thanks to \hbox{Qrrbrbirlbel})
    \item Very short lines with large angles were fixed (e.g.\ in \texttt{tikzcd} with \texttt{squiggly})
    \item Numerous bugs fixed
  \end{itemize}
  \item \textbf{v0.0.1}: First public version
\end{itemize}

\appendix
\newpage
\section{The Bézier offsetting algorithm}

This algorithm is based on an algorithm by \href{https://github.com/Pomax/}{Pomax}. See \href{https://pomax.github.io/bezierinfo/#offsetting}{A Primer on Bézier curves}, the source code can be found \href{https://github.com/Pomax/bezierinfo/blob/bcfce2149fa5e5540a2a2605986adab3b2a9a3bf/js/graphics-element/lib/bezierjs/bezier.js}{here}.

\subsection{Simple and fully simple Bézier curves}

Throughout this section the term ``Bézier curve'' refers to a cubic Bézier curve, which is defined by four points $(A_1, A_2, A_3, A_4)$.

As explained in the aforementioned source, in almost all cases the parallel of a Bézier curve is not exactly a Bézier curve itself. To approximate the parallel using Bézier curves, we therefore first divide the given curve into ``simple'' segments which can be offset with reasonable accuracy. The following defines a simple segment:
\begin{definition}
  \label{def:simpleCurve}
  A Bézier curve $(A_1, A_2, A_3, A_4)$ is \emph{simple} if
  \begin{enumerate}
    \item the points $A_2$ and $A_3$ lie on the same side of the line $\overline{A_1A_4}$,
    \item the absolute angle between the tangents in $A_1$ and $A_4$ is at most $\pi/3$ (i.e.\ the cosine is no smaller than $0.5$), and
    \item the distances fulfil $\overline{A_1A_2} + \overline{A_3A_4} \leq \overline{A_1A_4}$.\footnote{The reference only uses the first two conditions.}
  \end{enumerate}
\end{definition}
\begin{definition}
  \label{def:fullySimpleCurve}
  A Bézier curve $(A_1, A_2, A_3, A_4)$ is \emph{fully simple}\footnote{This terminology is not used in the source.} if all of its segments are simple in the sense of \cref{def:simpleCurve}.
\end{definition}
In order to offset an arbitrary Bézier curve we split it into fully simple segments.

\subsection{Subdivision}

It is well known that at every point $0 < t < 1$, de Casteljau's algorithm can subdivide a Bézier curve $A = (A_1, A_2, A_3, A_4)$ into two Bézier curves $B$ and $C$ (which naturally fulfil $A_1 = B_1$ and $A_4 = C_4$). A more or less heuristic fact is that $B$ and $C$ are ``more likely'' to be simple than $A$ (if you can prove any of the statements here, please contact me). Hence, if one wants to offset a non-simple curve $A$, one could try to subdivide $A$ until all of its segments are simple, then offset each segment.

\subsection{Pomax' approach}
The original approach by Pomax consists of two passes. The first pass subdivides $A$ on all extrema in $x$ or $y$. In a second pass, each segment $A^{(i)}$ is made simple in steps of $t \mapsto t + 0.01$, roughly using the following pseudocode:
\begin{samepage}
\begin{verbatim}
  t_1 = t_2 = 0.0
  while t_2 < 1.0:
    S = segment(A from t_1 to t_2+0.01)
    if not isSimple(S):
      segments += [segment(A from t_1 to t_2)]
      t_1 = t_2
    t_2 += 0.01
\end{verbatim}
\end{samepage}
Essentially, this ensures with great certainty that the segment is fully simple in the sense of \cref{def:fullySimpleCurve}.

The main reason this approach is not used in this library is performance, since the loop is quite expensive computationally. Other minor reasons include that the original approach is not invariant under reversals or rotations: Reversing and/or rotating a curve yields a different subdivision and hence potentially a slightly different-looking curve.

\subsection{The approach used here}
\label{subsec:subdivisionUsed}
In this library we instead take a recursive approach:
\begin{verbatim}
  def makeSimple(A, level):
    if isSimple(A):
      segments.append(A)
    else:
      if level < 0:
        Display a warning
        segments.append(A)
      else:
        first, second = split(A, t=0.5)
        makeSimple(first, level-1)
        makeSimple(second, level-1)
\end{verbatim}
The default maximum depth is 5, so the curve is split into at most $2^5 = 32$ segments. This has the downside that some simple but not fully simple curves may remain undetected and be offset slightly incorrectly. If you encounter examples of such curves with bad outputs, or if you have any ideas for additional constraints to add to \cref{def:simpleCurve} that can be checked with reasonable computational effort, please be in touch.


\subsection{Offsetting simple Bézier curves}

Disregarding edge cases (which will be discussed later), offsetting the curve works as follows:
\begin{enumerate}
  \item Construct lines orthogonal to the tangent in $A_1$ and $A_4$ and find their intersection. This point is called the \emph{origin} of the curve, denoted by $O$.
  \item The new control points $A'_1$ and $A'_4$ are given by $A_1$ and $A_4$ offset orthogonally to the tangent.
  \item Construct a ray from $A'_1$ parallel to the tangent in $A_1$, and construct another ray from $O$ through $A_2$. Now $A'_2$ is defined to be the intersection of those rays.
  \item $A'_3$ can be constructed similarly.
\end{enumerate}
The construction is shown in the following picture:
\[
\begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
  \coordinate (A1) at (-3, 0);
  \coordinate (A2) at (-1, 2);
  \coordinate (A3) at (1, 2);
  \coordinate (A4) at (3, 0);
  \coordinate (A1p) at (-4, 1);
  \coordinate (A4p) at (4, 1);
  \coordinate (A2p) at ($(A1p) + 1.33*(2,2)$);
  \coordinate (A3p) at ($(A4p) + 1.33*(-2,2)$);
  \coordinate (O) at (0, -3);
  \draw[dashed] (A1) -- (A2) (A3) -- (A4);
  \draw[dashed] (A1p) -- +(3,3) (A4p) -- +(-3,3);
  \draw[dashed] (A1p) -- (O) node[pos=.12, below left, fill=none] {$d$} (A4p) -- (O) node[pos=.12, below right, fill=none] {$d$};
  \draw[dashed] (A2p) -- (O) (A3p) -- (O);
  \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
  \draw[line width=1pt, red] (A1p) .. controls (A2p) and (A3p) .. (A4p);
  \node[label={below:$A_1$}] at (A1) {};
  \node[label={right:$A_2$}] at (A2) {};
  \node[label={right:$A_3$}] at (A3) {};
  \node[label={below:$A_4$}] at (A4) {};
  \node[label={left:$A'_1$}] at (A1p) {};
  \node[label={right:$A'_2$}] at (A2p) {};
  \node[label={right:$A'_3$}] at (A3p) {};
  \node[label={right:$A'_4$}] at (A4p) {};
  \node[label={right:$O$}] at (O) {};
\end{tikzpicture}
\]

\subsection{Removing singularities}

Clearly, as the angle between $\overrightarrow{A_1A_2}$ and $\overrightarrow{A_3A_4}$ decreases, the origin approaches infinity. Computing the control points $(A'_i)$ by computing the coordinates of $O$ is therefore not numerically stable for almost straight curves. However, we can get around this problem using elementary geometry. Constructing $A'_1$ and $A'_4$ is independent of the location of the origin, so the only difficult part is computing the distances $\overline{A'_1A'_2}$ and $\overline{A'_3A'_4}$. We find
\begin{equation}
  \frac{\overline{A'_1A'_2}}{\overline{A_1A_2}} = \frac{\overline{OA'_1}}{\overline{OA_1}} = 1 + \frac{d}{\overline{OA_1}} \implies \overline{A'_1A'_2} = \overline{A_1A_2} \left(1 + d \cdot \frac{1}{\overline{OA_1}}\right)
\end{equation}
which is regular as $O$ approaches infinity. Now we to determine the inverse of $\overline{OA_1}$, which can be computed using the law of sines:
\[
\begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
  \coordinate (A1) at (-3, 0);
  \coordinate (A2) at (-1, 2);
  \coordinate (A3) at (1, 2);
  \coordinate (A4) at (3, 0);
  \coordinate (O) at (0, -3);
  \draw[dashed] (A1) -- (A2) (A3) -- (A4);
  \draw[dashed] (A1) -- (O) (A4) -- (O);
  \draw (A1) -- (A4);
  \draw (-2,-1) arc[start angle=-45, end angle=45, radius=1.41cm];
  \draw ( 2,-1) arc[start angle=180+45, end angle=180-45, radius=1.41cm];
  \draw (-1,-2) arc[start angle=180-45, end angle=45, radius=1.41cm];
  \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
  \node[label={below:$A_1$}] at (A1) {};
  \node[label={right:$A_2$}] at (A2) {};
  \node[label={right:$A_3$}] at (A3) {};
  \node[label={below:$A_4$}] at (A4) {};
  \node[fill=none] at (-2,.3) {$\alpha$};
  \node[fill=none] at (-2.1,-.3) {\scriptsize$\frac{\pi}{2}-\alpha$};
  \node[fill=none] at ( 2,.3) {$\beta$};
  \node[fill=none] at ( 2.1,-.3) {\scriptsize$\frac{\pi}{2}-\beta$};
  \node[fill=none] at (0,-2.2) {$\alpha+\beta$};
  \node[label={right:$O$}] at (O) {};
\end{tikzpicture}
\]
\begin{equation}
  \frac{\sin(\tfrac{\pi}{2} - \alpha)}{\overline{OA_4}} = \frac{\sin(\alpha + \beta)}{\overline{A_1A_4}} = \frac{\sin(\tfrac{\pi}{2} - \beta)}{\overline{OA_1}} \implies \frac{1}{\overline{OA_1}} =  \frac{1}{\overline{A_1A_4}}\cdot\frac{\sin(\alpha + \beta)}{\cos(\beta)} \ .
\end{equation}
Note that $-\tfrac{\pi}{3} \leq \beta \leq \tfrac{\pi}{3}$ (and hence $\cos(\beta) \geq \tfrac{1}{2}$) is guaranteed if the curve is simple --- in fact, simplicity guarantees $\alpha \cdot \beta > 0$ and $|\alpha| + |\beta| \leq \tfrac{\pi}{3}$. Using the sine addition theorem we can further rewrite the fraction to
\begin{equation}
  \frac{\sin(\alpha + \beta)}{\cos(\beta)} = \sin(\alpha) + \cos(\alpha) \frac{\sin(\beta)}{\cos(\beta)} \ ,
\end{equation}
and all of these terms can be computed directly from dot and cross products of vectors between the original control points. To summarise, let $\vv_{ij} := \overrightarrow{A_iA_j}$, and let $\vv_0$, $\vv_1$ be the normalised tangents at $t=0$ and $t=1$, respectively (see \cref{subsec:stabilisation} how they are computed). Then
\begin{equation}
% for checking
  \overline{A'_1A'_2} = \overline{A_1A_2} + \frac{d}{\overline{A_1A_4}^2}\cdot\left(\vv_{12} \times \vv_{14} - \vv_{12}\cdot\vv_{14} \frac{\vv_{14}\times\tv_1}{\vv_{14}\cdot\tv_1} \right) \ .
\end{equation}
Let furthermore $\uv_{ij} := \vv_{ij}/|\vv_{ij}|$ be the normalised vectors. Then we find
\begin{equation}%
  \label{eq:finalPrimeDistance}
  \begin{aligned}
    \overline{A'_1A'_2} &= \overline{A_1A_2} + \frac{d}{\overline{A_1A_4}} \left(\vv_{12} \times \uv_{14} - \vv_{12}\cdot\uv_{14} \frac{\uv_{14}\times\tv_1}{\uv_{14}\cdot\tv_1} \right) \ , \\
    \overline{A'_4A'_3} &= \overline{A_4A_3} + \frac{d}{\overline{A_1A_4}} \left(\vv_{43} \times \uv_{14} - \vv_{43}\cdot\uv_{14} \frac{\uv_{14}\times\tv_0}{\uv_{14}\cdot\tv_0} \right) \ .
  \end{aligned}
\end{equation}



\subsection{Edge cases}

\subsubsection{Overlaps: \texorpdfstring{$A_i = A_{i+1}$}{A\_i = A\_(i+1)}}

If there is one overlap $A_1=A_2$, $A_2=A_3$ or $A_3=A_4$, the cubic Bézier curve reduces to a quadratic one. For two overlaps, we get a linear Bézier curve (i.e.\ a straight line), and for three overlaps we get a point. The main problem to watch out for is that the tangents $\tv_0$ and $\tv_1$ need to be computed differently:
\begin{itemize}
  \item If $A_1 \neq A_2$, we find $\tv_0 = \uv_{12}$.
  \item If $A_1 = A_2 \neq A_3$, we find $\tv_0 = \uv_{13}$.\footnote{This implicitly assumes a regular reparametrisation of the curve (e.g. a parametrisation over arc length); the usual parametrisation has a gradient of zero at $t=0$.}
  \item If $A_1 = A_2 = A_3 \neq A_4$, we find $\tv_0 = \uv_{14}$.
  \item If $A_1 = A_2 = A_3 = A_4$, the curve is just a point and the tangent is not defined. The implementation defaults to $\tv_0 = (1,0)$.
\end{itemize}
The analogous statement hold for $\tv_1$. In practice we test for approximate, not exact equality.

\subsubsection{Overlaps \texorpdfstring{$A_1 = A_4$}{A\_1 = A\_4}}

\Cref{eq:finalPrimeDistance} has one remaining singularity, namely for $A_1 \approx A_4$. This singularity is fundamental and not an artefact: As $A_1$ approaches $A_4$ while $\overline{A_1A_2}$ and $\overline{A_3A_4}$ stay constant, $O$ also approaches $A_4$, hence the angle between $\overrightarrow{A_1A_2}$ and $\overrightarrow{OA_2}$ approaches zero, sending the intersection point $A'_2$ to infinity.

A closer inspection of this special case reveals a number of sub-cases:
\begin{itemize}
  \item Fully degenerate curves with $A_1 \approx A_2 \approx A_3 \approx A_4$. Offsetting these curves in a stable manner is impossible, as the gradient and hence the direction in which to offset is numerically unstable. Rendering such curves will hardly have any output at all anyway. See below in \cref{subsec:stabilisation} how this case is handled.
  \item Non-trivial loops with $\overline{A_1A_2} \gg \overline{A_1A_4}$ and/or $\overline{A_3A_4} \gg \overline{A_1A_4}$, $|\alpha| + |\beta| \geq \tfrac{\pi}{3}$. Such curves violate the second and third condition of \cref{def:simpleCurve}, for example:
  \[
  \begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
    \coordinate (A1) at (-.07, 0);
    \coordinate (A2) at (-1, 2);
    \coordinate (A3) at (1, 2);
    \coordinate (A4) at (.07, 0);
    \draw[dashed] (A1) -- (A2) (A3) -- (A4);
    \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
    \node[label={left:$A_1$}] at (A1) {};
    \node[label={left:$A_2$}] at (A2) {};
    \node[label={right:$A_3$}] at (A3) {};
    \node[label={right:$A_4$}] at (A4) {};
  \end{tikzpicture}
  \]
  \item Curves with $\overline{A_1A_2} \gg \overline{A_1A_4}$ and/or $\overline{A_3A_4} \gg \overline{A_1A_4}$,  $|\alpha| + |\beta| < \tfrac{\pi}{3}$: Such curves violate the third condition of \cref{def:simpleCurve}, for example:
  \[
  \begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
    \coordinate (A1) at (-.07, 0);
    \coordinate (A3) at (-2, 1);
    \coordinate (A2) at (2, 1);
    \coordinate (A4) at (.07, 0);
    \draw[dashed] (A1) -- (A2) (A3) -- (A4);
    \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
    \node[label={left:$A_1$}] at (A1) {};
    \node[label={left:$A_2$}] at (A2) {};
    \node[label={right:$A_3$}] at (A3) {};
    \node[label={right:$A_4$}] at (A4) {};
  \end{tikzpicture}
  \]
\end{itemize}

\subsection{Stabilising the offsetting algorithm for non-simple curves}
\label{subsec:stabilisation}

As seen in \cref{subsec:subdivisionUsed}, there are cases where the offsetting algorithm will be called on non-simple curves. In such cases it is essential that the code does not crash (e.g. from division by zero), and that the output produced is at least somewhat sensible. The following measures are taken:
\begin{itemize}
  \item If $\overline{A_1A_4}$ is very close to zero,\footnote{Clamping the fraction $d/\overline{A_1A_4}$ to some maximum value did not work well, as it had a tendency of producing false positives.} we set $\overline{A'_1A'_2} = \overline{A_1A_2}$ and $\overline{A'_3A'_4} = \overline{A_3A_4}$, forming a rather rough approximation of the parallel curve. This causes a warning to be logged.
  \item For simple curves we find $\uv_{14}\cdot\uv_{34} \geq 0.5$ in the denominator. Therefore, for non-simple curves, the denominator is clamped to $[0.5, 1.0]$, preventing division by zero.
\end{itemize}


\end{document}