Debian Codegraph @

texmf-dist/doc/latex/tikz-nfold/tikz-nfold-doc.tex

raw
1 %% tikz-nfold-doc.tex
2 %% Copyright 2023 Jonathan Schulz
3 %
4 % This work may be distributed and/or modified under the
5 % conditions of the LaTeX Project Public License, either version 1.3c
6 % of this license or (at your option) any later version.
7 % The latest version of this license is in
8 % http://www.latex-project.org/lppl.txt
9 % and version 1.3c or later is part of all distributions of LaTeX
10 % version 2008-05-04 or later.
11 %
12 % This work has the LPPL maintenance status 'maintained'.
13 %
14 % The Current Maintainer of this work is Jonathan Schulz.
15 %
16 % This work consists of the files
17 % pgflibrarybezieroffset.code.tex, pgflibrarynfold.code.tex, pgflibraryoffsetpath.code.tex, tikz-nfold-doc.tex, tikzlibrarynfold.code.tex, tikz-nfold-doc.tex, and tikz-nfold-doc.pdf.
18 %
19 %
20 % A commented version of this file can be found on https://github.com/jonschz/tikz-nfold .
21 %
22
23
24 \documentclass[12pt,a4paper]{article}
25
26 \usepackage[utf8]{inputenc}
27 \usepackage{tikz}
28 \usepackage{tkzexample}
29 \usetikzlibrary{calc}
30 \usetikzlibrary{nfold}
31 \usepackage{parskip}
32 \usepackage[margin=2.5cm]{geometry}
33
34 \usepackage[colorlinks]{hyperref}
35 \usepackage{amsmath}
36 \usepackage{amsthm}
37 \usepackage[capitalize]{cleveref}
38 \usepackage{datetime}
39 \usepackage{enumitem}
40
41 \theoremstyle{definition}
42 \newtheorem{definition}{Definition}[section]
43
44 \newcommand{\tikzdouble}{\texttt{/tikz/double}}
45 \newcommand{\nfold}{\texttt{nfold}}
46 \newcommand{\tikznfold}{\texttt{/tikz/nfold}}
47
48 \pgfkeys{/tkzexample/every tkzexample/.style={
49 code=violet!15, graphic=orange!20, very small,above skip={\vskip1em},below skip={\vskip1em}
50 }
51 }
52
53 \newcommand{\tv}{\vec{t}}
54 \newcommand{\uv}{\vec{u}}
55 \newcommand{\vv}{\vec{v}}
56
57 \makeatletter
58 \def\disablewarnings{\def\pgfutil@packagewarning##1##2{}}
59 \makeatother
60
61 \begin{document}
62
63 \title{The \textsf{tikz-nfold} package}
64 \author{Jonathan Schulz}
65 \date{\monthname{} \the\year}
66
67 \maketitle
68
69 \begin{abstract}
70 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.
71 \end{abstract}
72
73 \section*{Compatibility}
74 This package has been tested with \texttt{pdflatex}, \texttt{lualatex}, \texttt{xelatex}, and plain \texttt{pdftex}.
75
76 \section{Quick start}
77
78 Add
79 \begin{verbatim}
80 \usetikzlibrary{nfold}
81 \end{verbatim}
82 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.
83 \begin{tkzexample}[latex=4cm]
84 \begin{tikzpicture}
85 \draw[double distance=3pt]
86 (0,2) to[out=0, in=180] (3,3);
87 \draw[double distance=3pt, nfold]
88 (0,0) to[out=0, in=180] (3,1);
89 \node[right] at (0,3) {double:};
90 \node[right] at (0,1) {nfold:};
91 \end{tikzpicture}
92 \end{tkzexample}
93 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).
94 Specify a number for n-fold lines:
95 \begin{tkzexample}[latex=4cm]
96 \begin{tikzpicture}
97 \draw[double distance=7pt, nfold=5]
98 (0,0) to[out=0, in=180] (3,1) -- (3,0);
99 \end{tikzpicture}
100 \end{tkzexample}
101 All arrow tips are supported, and there is special treatment for the \texttt{Implies} tip:
102 \begin{tkzexample}[latex=4cm]
103 \begin{tikzpicture}
104 \draw[double distance=7pt, nfold=5,
105 arrows={Bar[width=18pt]-Implies[red]}]
106 (0,1.5) to[bend left] (3,1.5);
107 \draw[double distance=7pt, nfold=5, arrows=Implies-Implies]
108 (0,0) to[bend left] (3,0);
109 \end{tikzpicture}
110 \end{tkzexample}
111 Use \texttt{/tikz/scaling nfold} to preserve the distance between component lines instead of the overall width of the arrow:
112 \begin{tkzexample}[latex=4cm,pre={\usetikzlibrary{intersections}}]
113 \begin{tikzpicture}
114 \draw[double equal sign distance, nfold,
115 arrows=-Implies] (0,.75) -- (3,.75);
116 \draw[double equal sign distance, scaling nfold=4,
117 arrows=-Implies] (0,0) -- (3,0);
118 \draw[double equal sign distance, scaling nfold=6,
119 arrows=-Implies] (0,-1) -- (3,-1);
120 \end{tikzpicture}
121 \end{tkzexample}
122 Different line joins are supported:
123 \begin{tkzexample}[latex=2cm]
124 \begin{tikzpicture}[line join=bevel]
125 \draw[line join=miter, double distance=7pt, nfold=4]
126 (0,2) -- (1, 2) -- (1,2.5);
127 \draw[double distance=7pt, nfold=4]
128 (0,1) -- (1, 1) -- (1,1.5);
129 \draw[line join=round, double distance=7pt, nfold=4]
130 (0,0) -- (1, 0) -- (1,.5);
131 \end{tikzpicture}
132 \end{tkzexample}
133 There is also support for \texttt{tikz-cd} with custom label positions for \texttt{scaling nfold}:
134 \begin{tkzexample}[pre={\usetikzlibrary{cd}}, latex=3cm]
135 \begin{tikzcd}
136 a \ar[r, Mapsto, bend left, scaling nfold=3] &
137 b \ar[d, Rightarrow, nfold, "\alpha", "\beta"'] \\
138 c \ar[r, Mapsfrom, scaling nfold=4, "\gamma" near end] &
139 d
140 \end{tikzcd}
141 \end{tkzexample}
142
143
144 \section{Comparison to \tikzdouble}
145 \label{sec:doubleIssues}
146
147 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:
148 \begin{equation}
149 \label{eq:compareApproaches}
150 \begin{tikzpicture}[baseline=.5cm]
151 \fill[orange!20] (-4.5,-.5) rectangle (6, 1.5);
152 \node[left] at (-1,1) {\tikzdouble:};
153 \draw[line width=7pt] (0,1) -- (1,1);
154 \node at (1.5,1) {+};
155 \draw[white, line width=5pt] (2,1) -- (3,1);
156 \node at (3.5,1) {=};
157 \draw[double distance=5pt] (4,1) -- (5,1);
158 \node[left] at (-1,0) {\tikznfold:};
159 \draw (0, 3pt) -- (1, 3pt);
160 \node at (1.5,0) {+};
161 \draw (2, -3pt) -- (3, -3pt);
162 \node at (3.5,0) {=};
163 \draw[double distance=5pt, nfold] (4,0) -- (5,0);
164 \end{tikzpicture}
165 \end{equation}
166 While the approach of \tikzdouble{} is very robust and efficient, it does have a few pitfalls:
167 \begin{itemize}[beginpenalty=10000]
168 \item Different types of visual glitches can occur in PDF renderers:
169 \begin{itemize}
170 \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}).
171 \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.
172 \end{itemize}
173 \item The approach assumes that the background has a uniform colour, and it is the user's responsibility to correctly set the background colour:
174 \begin{tkzexample}[latex=3.5cm]
175 \begin{tikzpicture}
176 \draw[red, line width=1pt] (2.5, 3.3) -- (2.5, 0);
177 \draw[line width=2pt, double distance=3pt]
178 (0,2) to[out=0, in=180] (3,3);
179 \node[right] at (0,3) {double:};
180 \draw[line width=2pt, double distance=3pt, nfold]
181 (0,0) to[out=0, in=180] (3,1);
182 \node[right] at (0,1) {nfold:};
183 \end{tikzpicture}
184 \end{tkzexample}
185 \item Transparency does not work correctly:
186 \begin{tkzexample}[latex=3.5cm]
187 \begin{tikzpicture}[line width=1pt]
188 \draw[double distance=3pt, opacity=.5]
189 (0,2) to[out=0, in=180] (3,3);
190 \draw[double distance=3pt, opacity=.5, nfold]
191 (0,0) to[out=0, in=180] (3,1);
192 \node[right] at (0,3) {double:};
193 \node[right] at (0,1) {nfold:};
194 \end{tikzpicture}
195 \end{tkzexample}
196 \item Triple and n-fold paths are not supported (although this could be implemented in principle).
197 \end{itemize}
198 However, there are still situations where \tikznfold{} struggles and \tikzdouble{} is the only viable option, which will be discussed in the next section.
199
200 \section{Known issues}
201
202 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}.
203
204 \subsection{Fixable / wish list}
205 \begin{itemize}
206 \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.
207 \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.
208 \item Closed paths can glitch slightly when the final segment is very short and has non-zero angles on both ends.
209 \end{itemize}
210
211 \subsection{Impossible or very hard to fix}
212 \begin{itemize}
213 \item Self-intersecting paths do not have the expected intersections:
214 \begin{tkzexample}[latex=4.5cm]
215 \begin{tikzpicture}
216 \draw[double distance=5pt, line width=1pt]
217 (0,2.5) -- (1,2.5) (1,3) -- (1,2)
218 (2,2) -- (3,2) rectangle (4,3);
219 \node[right] at (0,3.5) {double:};
220 \draw[double distance=5pt, line width=1pt, nfold]
221 (0,.5) -- (1,.5) (1,1) -- (1,0)
222 (2,0) -- (3,0) rectangle (4,1);
223 \node[right] at (0,1.5) {nfold:};
224 \end{tikzpicture}
225 \end{tkzexample}
226 \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:
227 \begin{tkzexample}[latex=4.25cm]
228 \begin{tikzpicture}
229 \draw[double distance=5pt, line width=1pt]
230 (0,2) .. controls (4,2) and (0,3) .. (3,2.5);
231 \node[right] at (0,3) {double:};
232 \draw[double distance=5pt, line width=1pt, nfold]
233 (0,0) .. controls (4,0) and (0,1) .. (3,.5);
234 \node[right] at (0,1) {nfold:};
235 \end{tikzpicture}
236 \end{tkzexample}
237 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.
238 \item Dashed paths with significant curvature will desynchronise:
239 \begin{tkzexample}[latex=3cm]
240 \begin{tikzpicture}
241 \draw[arrows=-Implies, double equal sign distance, dashed,
242 scaling nfold=4] (0,0) to[out=30, in=150] (2,0);
243 \end{tikzpicture}
244 \end{tkzexample}
245 \item Curves of \nfold{} slightly deviate from the curves of \tikzdouble{} near joins with a non-zero angle:
246 \begin{tkzexample}[latex=3.5cm]
247 \begin{tikzpicture}[line width=1pt]
248 \draw[red, double distance=20pt]
249 (0,2) -- (2,2) to [out=-90, in=0] (.5,.5);
250 \draw[blue, double distance=20pt, opacity=.5, nfold]
251 (0,2) -- (2,2) to [out=-90, in=0] (.5,.5);
252 \node[right, red] at (0,3) {double};
253 \node[left, blue] at (3, 3) {nfold};
254 \end{tikzpicture}
255 \end{tkzexample}
256 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$.
257 \item Very short \emph{curves} with large angles at the ends result in a glitched output:\nopagebreak
258 \begin{tkzexample}[latex=3.75cm,pre=\disablewarnings]
259 \begin{tikzpicture}[line join=round]
260 \draw[black] (1,0) -- (3,0) -- (1.5,1.2) -- (3.8,0.85);
261 \draw[red, line width=1pt, double distance=.7cm, nfold]
262 (1,0) -- (3,0) -- (1.5, 1.2) -- (3.8,0.85);
263 \draw[blue, double distance=.7cm, nfold] (1,0) -- (3,0)
264 to[relative, out=1, in=179] (1.5, 1.2) -- (3.8,0.85);
265 \end{tikzpicture}
266 \end{tkzexample}
267 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.
268 \item Changing joins in \verb|\pgfsys@beginscope| without an accompanying \TeX{} group may cause inconsistent behaviour in the joins:
269 \begin{tkzexample}[latex=2cm]
270 \makeatletter
271 \begin{tikzpicture}[line join=miter, line width=2pt]
272 \pgfsys@beginscope
273 \pgfsetroundjoin
274 \pgfsys@endscope
275 \draw[double distance=5pt, nfold] (0,0) -- (.5,2) -- (1,0);
276 \end{tikzpicture}
277 \makeatother
278 \end{tkzexample}
279 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|.
280 \end{itemize}
281
282
283 \section{The basic layer \texttt{pgf} commands}
284
285 This package contains three \emph{pgf} libraries building upon one another: \texttt{bezieroffset}, \texttt{offsetpath}, and \nfold. All of these are contained in the \emph{TikZ} library \nfold.
286
287 \subsection{Offsetting curves}
288 This library provides some basic layer commands for offsetting curves and straight lines. Use
289 \begin{verbatim}
290 \usepgflibrary{bezieroffset}
291 \end{verbatim}
292 to only import this base layer library. The following commands are provided:
293 \begin{itemize}
294 \item \verb|\pgfoffsetcurve{pt1}{pt2}{pt3}{pt4}{distance}|\\%
295 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}.
296 \item \verb|\pgfoffsetcurvenomove{pt1}{pt2}{pt3}{pt4}{distance}|\\%
297 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}.
298 \item \verb|\pgfoffsetline{pt1}{pt2}{distance}|\\%
299 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.
300 \item \verb|\pgfoffsetlinenomove{pt1}{pt2}{distance}|\\%
301 This macro is analogous to \verb|\pgfoffsetcurvenomove|.
302 \end{itemize}
303
304 \subsection{Offsetting paths}
305 The following macros are part of the pgf library \texttt{offsetpath} and offset the whole softpath.
306 \begin{itemize}
307 \item \verb|\pgfoffsetpath{softpath}{distance}|\\%
308 This macro offsets \texttt{softpath} by \texttt{distance}. The latter may be negative.
309 \item \verb|\pgfoffsetpathfraction{softpath}{hwidth}{fraction}|\\%
310 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.
311 \item \verb|\pgfoffsetpathqfraction{softpath}{hwidth}{fraction}|\\%
312 This macro is a quicker version of the previous macro does not parse the input values using the \texttt{pgfmath}-engine.
313 \item \verb|\pgfoffsetpathindex{softpath}{width}{i}{n}|\\%
314 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}, hence it is capable of reproducing the output of \texttt{/tikz/nfold=n} (albeit in a less efficient way).
315 \end{itemize}
316 In the following example we see how \verb|\pgfoffsetpath{..}{0pt}| reproduces the input path (rendered in black) and how \verb|\pgfoffsetpathfraction{..}{8pt}{0}| differs.
317 \begin{tkzexample}[latex=4cm]
318 \begin{tikzpicture}[line join=bevel]
319 \path[save path=\savedpath] (0,0) -- (1,0)
320 to[out=0, in=-80] (1,3) -- (3,2);
321 \draw[color=lightgray,line width=16pt,use path=\savedpath];
322 \pgfoffsetpathfraction{\savedpath}{8pt}{0}
323 \pgfsetlinewidth{1pt} \color{red} \pgfusepathqstroke
324 \pgfoffsetpath{\savedpath}{8pt}
325 \color{blue} \pgfusepathqstroke
326 \pgfoffsetpath{\savedpath}{-8pt}
327 \color{green} \pgfusepathqstroke
328 \pgfoffsetpath{\savedpath}{0pt}
329 \pgfsetlinewidth{.4pt} \color{black} \pgfusepathqstroke
330 \end{tikzpicture}
331 \end{tkzexample}
332 Here we see how the commands can be used to customise $n$-fold paths:
333 \begin{tkzexample}[latex=4cm]
334 \begin{tikzpicture}
335 \path[save path=\mypath] (0,0) -- (2,0) arc(-90:90:1)
336 to[out=180, in=0] (0,1) -- (0,2);
337 \foreach \mycolor [count=\i] in {red,green,blue,violet}
338 \pgfoffsetpathindex{\mypath}{6pt}{\i}{4}
339 \color{\mycolor} \pgfusepathqstroke;
340 \end{tikzpicture}
341 \end{tkzexample}
342
343
344 \newpage
345 \section{Version history}
346
347 \begin{itemize}
348 \item \textbf{v1.0.0}: Restructure and bug fixes
349 \item \textbf{v0.1.3}: Bug fixes
350 \item \textbf{v0.1.2}: Bug fixes
351 \item \textbf{v0.1.1}: Closing paths and structural changes
352 \begin{itemize}
353 \item Support for closed paths (\texttt{cycle} and \verb|\pgfpathclose|)
354 \item Significant performance improvements due to structural changes
355 \item Minor bug fixes and optimisations
356 \end{itemize}
357 \item \textbf{v0.1.0}: Major overhaul
358 \begin{itemize}
359 \item Support for arbitrary arrow tips
360 \item Support for directly offsetting soft paths
361 \item New key \texttt{/tikz/scaling nfold}
362 \item The \texttt{decorations} library was dropped
363 \item Various performance improvements in \texttt{bezieroffset} (thanks to \hbox{Qrrbrbirlbel})
364 \item Very short lines with large angles were fixed (e.g.\ in \texttt{tikzcd} with \texttt{squiggly})
365 \item Numerous bugs fixed
366 \end{itemize}
367 \item \textbf{v0.0.1}: First public version
368 \end{itemize}
369
370 \appendix
371 \newpage
372 \section{The Bézier offsetting algorithm}
373
374 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}.
375
376 \subsection{Simple and fully simple Bézier curves}
377
378 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)$.
379
380 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:
381 \begin{definition}
382 \label{def:simpleCurve}
383 A Bézier curve $(A_1, A_2, A_3, A_4)$ is \emph{simple} if
384 \begin{enumerate}
385 \item the points $A_2$ and $A_3$ lie on the same side of the line $\overline{A_1A_4}$,
386 \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
387 \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.}
388 \end{enumerate}
389 \end{definition}
390 \begin{definition}
391 \label{def:fullySimpleCurve}
392 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}.
393 \end{definition}
394 In order to offset an arbitrary Bézier curve we split it into fully simple segments.
395
396 \subsection{Subdivision}
397
398 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.
399
400 \subsection{Pomax' approach}
401 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:
402 \begin{samepage}
403 \begin{verbatim}
404 t_1 = t_2 = 0.0
405 while t_2 < 1.0:
406 S = segment(A from t_1 to t_2+0.01)
407 if not isSimple(S):
408 segments += [segment(A from t_1 to t_2)]
409 t_1 = t_2
410 t_2 += 0.01
411 \end{verbatim}
412 \end{samepage}
413 Essentially, this ensures with great certainty that the segment is fully simple in the sense of \cref{def:fullySimpleCurve}.
414
415 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.
416
417 \subsection{The approach used here}
418 \label{subsec:subdivisionUsed}
419 In this library we instead take a recursive approach:
420 \begin{verbatim}
421 def makeSimple(A, level):
422 if isSimple(A):
423 segments.append(A)
424 else:
425 if level < 0:
426 Display a warning
427 segments.append(A)
428 else:
429 first, second = split(A, t=0.5)
430 makeSimple(first, level-1)
431 makeSimple(second, level-1)
432 \end{verbatim}
433 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.
434
435
436 \subsection{Offsetting simple Bézier curves}
437
438 Disregarding edge cases (which will be discussed later), offsetting the curve works as follows:
439 \begin{enumerate}
440 \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$.
441 \item The new control points $A'_1$ and $A'_4$ are given by $A_1$ and $A_4$ offset orthogonally to the tangent.
442 \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.
443 \item $A'_3$ can be constructed similarly.
444 \end{enumerate}
445 The construction is shown in the following picture:
446 \[
447 \begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
448 \coordinate (A1) at (-3, 0);
449 \coordinate (A2) at (-1, 2);
450 \coordinate (A3) at (1, 2);
451 \coordinate (A4) at (3, 0);
452 \coordinate (A1p) at (-4, 1);
453 \coordinate (A4p) at (4, 1);
454 \coordinate (A2p) at ($(A1p) + 1.33*(2,2)$);
455 \coordinate (A3p) at ($(A4p) + 1.33*(-2,2)$);
456 \coordinate (O) at (0, -3);
457 \draw[dashed] (A1) -- (A2) (A3) -- (A4);
458 \draw[dashed] (A1p) -- +(3,3) (A4p) -- +(-3,3);
459 \draw[dashed] (A1p) -- (O) node[pos=.12, below left, fill=none] {$d$} (A4p) -- (O) node[pos=.12, below right, fill=none] {$d$};
460 \draw[dashed] (A2p) -- (O) (A3p) -- (O);
461 \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
462 \draw[line width=1pt, red] (A1p) .. controls (A2p) and (A3p) .. (A4p);
463 \node[label={below:$A_1$}] at (A1) {};
464 \node[label={right:$A_2$}] at (A2) {};
465 \node[label={right:$A_3$}] at (A3) {};
466 \node[label={below:$A_4$}] at (A4) {};
467 \node[label={left:$A'_1$}] at (A1p) {};
468 \node[label={right:$A'_2$}] at (A2p) {};
469 \node[label={right:$A'_3$}] at (A3p) {};
470 \node[label={right:$A'_4$}] at (A4p) {};
471 \node[label={right:$O$}] at (O) {};
472 \end{tikzpicture}
473 \]
474
475 \subsection{Removing singularities}
476
477 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
478 \begin{equation}
479 \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)
480 \end{equation}
481 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:
482 \[
483 \begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
484 \coordinate (A1) at (-3, 0);
485 \coordinate (A2) at (-1, 2);
486 \coordinate (A3) at (1, 2);
487 \coordinate (A4) at (3, 0);
488 \coordinate (O) at (0, -3);
489 \draw[dashed] (A1) -- (A2) (A3) -- (A4);
490 \draw[dashed] (A1) -- (O) (A4) -- (O);
491 \draw (A1) -- (A4);
492 \draw (-2,-1) arc[start angle=-45, end angle=45, radius=1.41cm];
493 \draw ( 2,-1) arc[start angle=180+45, end angle=180-45, radius=1.41cm];
494 \draw (-1,-2) arc[start angle=180-45, end angle=45, radius=1.41cm];
495 \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
496 \node[label={below:$A_1$}] at (A1) {};
497 \node[label={right:$A_2$}] at (A2) {};
498 \node[label={right:$A_3$}] at (A3) {};
499 \node[label={below:$A_4$}] at (A4) {};
500 \node[fill=none] at (-2,.3) {$\alpha$};
501 \node[fill=none] at (-2.1,-.3) {\scriptsize$\frac{\pi}{2}-\alpha$};
502 \node[fill=none] at ( 2,.3) {$\beta$};
503 \node[fill=none] at ( 2.1,-.3) {\scriptsize$\frac{\pi}{2}-\beta$};
504 \node[fill=none] at (0,-2.2) {$\alpha+\beta$};
505 \node[label={right:$O$}] at (O) {};
506 \end{tikzpicture}
507 \]
508 \begin{equation}
509 \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)} \ .
510 \end{equation}
511 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
512 \begin{equation}
513 \frac{\sin(\alpha + \beta)}{\cos(\beta)} = \sin(\alpha) + \cos(\alpha) \frac{\sin(\beta)}{\cos(\beta)} \ ,
514 \end{equation}
515 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
516 \begin{equation}
517 \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) \ .
518 \end{equation}
519 Let furthermore $\uv_{ij} := \vv_{ij}/|\vv_{ij}|$ be the normalised vectors. Then we find
520 \begin{equation}%
521 \label{eq:finalPrimeDistance}
522 \begin{aligned}
523 \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) \ , \\
524 \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) \ .
525 \end{aligned}
526 \end{equation}
527
528
529
530 \subsection{Edge cases}
531
532 \subsubsection{Overlaps: \texorpdfstring{$A_i = A_{i+1}$}{A\_i = A\_(i+1)}}
533
534 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:
535 \begin{itemize}
536 \item If $A_1 \neq A_2$, we find $\tv_0 = \uv_{12}$.
537 \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$.}
538 \item If $A_1 = A_2 = A_3 \neq A_4$, we find $\tv_0 = \uv_{14}$.
539 \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)$.
540 \end{itemize}
541 The analogous statement hold for $\tv_1$. In practice we test for approximate, not exact equality.
542
543 \subsubsection{Overlaps \texorpdfstring{$A_1 = A_4$}{A\_1 = A\_4}}
544
545 \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.
546
547 A closer inspection of this special case reveals a number of sub-cases:
548 \begin{itemize}
549 \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.
550 \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:
551 \[
552 \begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
553 \coordinate (A1) at (-.07, 0);
554 \coordinate (A2) at (-1, 2);
555 \coordinate (A3) at (1, 2);
556 \coordinate (A4) at (.07, 0);
557 \draw[dashed] (A1) -- (A2) (A3) -- (A4);
558 \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
559 \node[label={left:$A_1$}] at (A1) {};
560 \node[label={left:$A_2$}] at (A2) {};
561 \node[label={right:$A_3$}] at (A3) {};
562 \node[label={right:$A_4$}] at (A4) {};
563 \end{tikzpicture}
564 \]
565 \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:
566 \[
567 \begin{tikzpicture}[every node/.append style={inner sep=1.5pt, circle, fill}]
568 \coordinate (A1) at (-.07, 0);
569 \coordinate (A3) at (-2, 1);
570 \coordinate (A2) at (2, 1);
571 \coordinate (A4) at (.07, 0);
572 \draw[dashed] (A1) -- (A2) (A3) -- (A4);
573 \draw[line width=1pt, blue] (A1) .. controls (A2) and (A3) .. (A4);
574 \node[label={left:$A_1$}] at (A1) {};
575 \node[label={left:$A_2$}] at (A2) {};
576 \node[label={right:$A_3$}] at (A3) {};
577 \node[label={right:$A_4$}] at (A4) {};
578 \end{tikzpicture}
579 \]
580 \end{itemize}
581
582 \subsection{Stabilising the offsetting algorithm for non-simple curves}
583 \label{subsec:stabilisation}
584
585 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:
586 \begin{itemize}
587 \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.
588 \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.
589 \end{itemize}
590
591
592 \end{document}