summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/metapost/bpolynomial/bpolynomial.tex
blob: 02acf9e04027e39ed05f0fe3492793e953c07d8e (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
%%% bpolynomial.tex
%%% Copyright 2007 Stephan Hennig <stephanhennig@arcor.de>
%
% This work may be distributed and/or modified under the conditions of
% the LaTeX Project Public License, either version 1.3 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
%
\RequirePackage[resetfonts]{cmap}
\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{amssymb}
\newcommand*{\cmd}[1]{\texttt{#1}}
\newcommand*{\pkg}{\cmd{bpolynomial.mp}}
\newcommand{\user}[1]{\emph{#1}}
\newcommand*{\B}{B\'ezier}
\usepackage{xcolor}
\colorlet{framecol}{black!50}
\usepackage{listings}
\lstloadlanguages{MetaPost,[LaTeX]TeX}
\lstset{language=MetaPost, basicstyle=\small\ttfamily, keywordstyle={}, commentstyle={}, columns=flexible, showspaces=false, showstringspaces=false, frame=single, rulecolor=\color{framecol}, aboveskip=2ex, belowskip=2ex, framesep=2ex, xleftmargin=2ex, xrightmargin=2ex}
\lstnewenvironment{listing}[1][]
{\lstset{#1}}
{}
\usepackage{multicol}
\usepackage{url}
\usepackage{graphicx}
\setcounter{topnumber}{1}
\setcounter{bottomnumber}{0}
\usepackage{ifpdf}
\ifpdf
\DeclareGraphicsRule{*}{mps}{*}{}
\fi

\begin{document}
\title{The \pkg\ package\thanks{This document describes \pkg\ v0.3, last revised 11/26/2007.}}
\author{Stephan Hennig\thanks{stephanhennig@arcor.de}}
\maketitle

\begin{abstract}
The MetaPost package \pkg\ helps drawing polynomial functions of up to degree three.  It provides macros to calculate \B\ curves exactly matching a given constant, linear, quadratic or cubic polynomial.
\end{abstract}

\begin{multicols}{2}
\tableofcontents
\end{multicols}


\section{Introduction}
MetaPost has a variable type \cmd{path} that can be used for drawing smooth and visualy pleasing curves.  Internally, paths are \B\ curves and MetaPost is able to calculate the points along such a curve.\footnote{Since PostScript has a concept of \B\ curves, too, for MetaPost drawing a path is simply an act of copying the parameters of the corresponding \B\ curve into PostScript output.  But nonetheless MetaPost \emph{can} calculate points on a \B\ curve.}

When drawing graphs, the problem users are confronted with is how to define a suitable path representing a given function $f(x)$?  The \cmd{splines} package by Dan Luecking provides macros to draw smooth piece-wise \B\ curves through arbitrary sample points.~\cite{mp:splines}  However, since \B\ curves are polynomials of degree three, we can do better with just one \B\ curve segment for such polynomials.  This package eases the task of finding a \B\ curve matching a given polynomial

\begin{equation}
f(x) = ax^3 + bx^2 + cx + d
\end{equation}


\section{Usage}
\subsection{Macro \cmd{newBPolynomial}}
The \pkg\ package provides just one macro \cmd{newBPolynomial}.  This macro takes one suffix parameter and four numeric parameters that are the coefficients of the given polynomial.  A polynomial definition for a function
\begin{equation}
  f(x) = 2x^3 + 0x^2 - 3x - 1  
\end{equation}
exemplary looks like this
\begin{listing}
newBPolynomial.f(2, 0, -3, -1);
\end{listing}
Here, suffix parameter \cmd{f} serves as an identifier where some names of macros and variables, that have to be called later, are derived from and the parameters $2$, $0$, $-3$, $-1$ match the coefficients of our function $f$.  To be more precise, command
\begin{center}
  \cmd{newBPolynomial.<suffix>()}
\end{center}
defines two new macros
\begin{center}
  \cmd{<suffix>.getPath()}
\end{center}
and
\begin{center}
  \cmd{<suffix>.eval()}
\end{center}
that do the real work.

\subsection{Macro \cmd{<suffix>.getPath}}
Macro \cmd{<suffix>.getPath(xmin, xmax)} returns a path exactly matching the polynomial defined by \cmd{newBPolynomial.<suffix>} on the intervall $[xmin, xmax]$.  Let's have a look at an example.  Drawing our polynomial $f(x)$ on the intervall $(-2, 2)$ can be done with the following code (figure~\ref{fig:cubic}).
\begin{listing}
newBPolynomial.f(2, 0, -3, -1);
draw f.getPath(-2, 2) xscaled 1cm yscaled 0.1cm;
\end{listing}

\begin{figure}
  \begin{minipage}[t]{.45\linewidth}
    \centering
    \includegraphics{examples.1}
    \caption{A cubic polynomial.}
    \label{fig:cubic}
  \end{minipage}\hfill%
  \begin{minipage}[t]{.45\linewidth}
    \centering
    \includegraphics{examples.2}
    \caption{With stars.}
    \label{fig:starred}
  \end{minipage}
\end{figure}

Once a polynomial $\langle$suffix$\rangle$ has been defined \cmd{<suffix>.getPath} can be called as often as required with varying arguments and returns a path corresponding to the requested section of polynomial $\langle$suffix$\rangle$.

Note, since the \pkg\ package never uses $\langle$suffix$\rangle$ as a complete identifier, you can use that as the name of a path variable to store the path returned by \cmd{<suffix>.getPath} for later drawing.  Any other path (array) variable serves the same purpose, though.
\begin{listing}
newBPolynomial.f(2, 0, -3, -1);
path f;
f := f.getPath(-2, 2);
draw f xscaled 1cm yscaled 0.1cm;
\end{listing}

\subsection{Macro \cmd{<suffix>.eval}}
The other macro defined by \cmd{newBPolynomial.<suffix>}, macro \cmd{<suffix>.eval}, can be used to evaluate polynomial $\langle$suffix$\rangle$ at a given x-coordinate.  This macro takes one parameter---the x-coordinate.  A ``starred'' version of our polynomial can be plotted with the following code (figure~\ref{fig:starred}).
\begin{listing}
newBPolynomial.f(2, 0, -3, -1);
for x=-2 step .25 until 2:
   label(btex $\star$ etex, (x, f.eval(x)) xscaled 1cm yscaled 0.1cm);
endfor
\end{listing}

\subsection{Accessing polynomial coefficients}
Additionally, macro \cmd{newBPolynomial.<suffix>} saves the coefficients passed as arguments in variables \cmd{<suffix>.a}, \cmd{<suffix>.b}, \cmd{<suffix>.c} and \cmd{<suffix>.d} for later reference.


\section{Examples}
In the first example a simple corrdinate system is drawn manually.  Then a quadratic polynomial \cmd{f} is drawn in three strokes.  Two dahsed strokes correspond to the positive values of \cmd{f}, a dotted stroke corresponds to negative values.  Finally, a cubic polynomials \cmd{g} is plotted and a table of points is written to the console and log file (figure~\ref{fig:coordinatesystem}).

\begin{figure}
  \centering
  \includegraphics{examples.3}
  \caption{Two polynomials in a coordinate system.}
  \label{fig:coordinatesystem}
\end{figure}

\begin{listing}
numeric u;
u := 0.5cm;
  %%% Draw a coordinate system.
  xmin := -5; xmax := 6;
  ymin := -5; ymax := 6;
  drawarrow ((xmin,0)--(xmax,0)) scaled u;
  drawarrow ((0,ymin)--(0,ymax)) scaled u;
  drawoptions(withpen pencircle scaled 1bp);
  %%% Define polynomial f of degree 2.
path f[];
  newBPolynomial.f(0, 0.5, -2, 0);
  f1 := f.getPath(-2, 0);
  f2 := f.getPath(0, 4);
  f3 := f.getPath(4, 5.5);
  draw f1 scaled u dashed evenly scaled 2;
  draw f3 scaled u dashed evenly scaled 2;
  draw f2 scaled u dashed withdots
    withpen pencircle scaled 1.5bp withcolor .5white;
  %%% Define polynomial g of degree 3.
path g;
  newBPolynomial.g(0.3, 0, -3, -1);
  g := g.getPath(-3.5, 4);
  show g;
  draw g scaled u;
  %%% Write table with some points of g to log file.
  show "Polynomial: " & decimal g.a & "x^3+" & decimal g.b
    & "x^2+" & decimal g.c & "x+" & decimal g.d;
  for x=-5 upto 5:
    show (x, g.eval(x));
  endfor
\end{listing}

Note command \cmd{show g} that writes path~\cmd{g} to the \cmd{log} file.  Inspecting that we can easily verify, that \cmd{g} consists of just one path segment:
\begingroup\small
\begin{verbatim}
(-3.5,-3.36273)..controls (-1,16.70013) and (1.5,-22.30025)..(4,6.2002)
\end{verbatim}
\endgroup

The next example demonstrates how \pkg\ and John Hobby's \cmd{graph} package\cite{mp:graph} can be used together to draw polynomials in a coordinate system.  Instead of \cmd{draw} paths have just to be drawn with a \cmd{gdraw} command.  The latter macro additionally clips paths to the boundaries of the coordinate system (figure~\ref{fig:bpolynomialgraph}).

\begin{figure}
  \centering
  \includegraphics{examples.4}
  \caption{Packages \pkg\ and \cmd{graph} interacting.}
  \label{fig:bpolynomialgraph}
\end{figure}

\begin{listing}
path f,g;
  xmin := -7; xmax := 7;
  ymin := -7; ymax := 7;
  newBPolynomial.f(0, 0.5, -2, 0);
  f := f.getPath(xmin, xmax);
  newBPolynomial.g(0.3, 0, -3, -1);
  g := g.getPath(xmin, xmax);
  draw begingraph(10cm, 6cm);
    setrange(xmin,ymin, xmax,ymax);
    autogrid(grid.bot, grid.lft)
      dashed withdots withpen pencircle scaled .7bp withcolor .5white;
    drawoptions(withpen pencircle scaled 1bp);
    gdraw f dashed evenly scaled 2;
    gdraw g;
    drawoptions();
  endgraph;
\end{listing}

The code of all examples can also be found in file \cmd{examples.mp}.


\section{Mathematics}
A \B\ curve $P(t)$ with end points $A=(x_A,y_A)$ and $D=(x_D,y_D)$ and control points $B=(x_B,y_B)$ and $C=(x_C,y_C)$ is defined as
\begin{equation}
P(t) = \left(
  \begin{array}{@{}c@{}}
    x\\
    y\\
  \end{array}
  \right)(t) = A + 3(B-A)t + 3(C-2B+A)t^2 + (D-3C+3B-A)t^3,\quad 0\leq t\leq 1.
\end{equation}

An arbitrary function $y=f(x)$ can be written in parameter form as
\begin{equation}
  F(t) = \left(
    \begin{array}{@{}c@{}}
      x \\
      y \\
    \end{array}
  \right)(t) = \left(
    \begin{array}{@{}c@{}}
      x(t) \\
      f\big(x(t)\big) \\
    \end{array}
  \right),\quad t\in \mathbb{R}
\end{equation}
with parameter $t$.

For a function
\begin{equation}
  f(x) = ax^3 + bx^2 + cx + d,\quad x\in [x_0, x_1]
\end{equation}
we have
\begin{equation}
  x(t) = x_0 + (x_1-x_0)t,\quad 0\leq t\leq 1
\end{equation}
and hence
\begin{equation}
  F(t) = \left(
    \begin{array}{@{}c@{}}
      x_0 + (x_1-x_0)t \\
      ax(t)^3 + bx(t)^2 + cx(t) + d \\
    \end{array}
  \right),\quad 0\leq t\leq 1.
\end{equation}
Writing F(t) down explicitly is left as an exercise for the interested reader.

Finally, setting
\begin{equation}
  P(t) = F(t)
\end{equation}
and sorting the coefficients of the $t^k$ one arrives at the following \emph{original} equation system:
\begin{align}
  x_A & = x_0 \label{eq:xA} \\
  3(x_B-x_A) & = x_1 - x_0 \label{eq:xB} \\
  3(x_C-2x_B+x_A) & = 0 \label{eq:xC} \\
  x_D-3x_C+3x_B-x_A & = 0 \label{eq:xD} \\
  y_A & = ax_0^3 + bx_0^2 + cx_0 + d \label{eq:yA} \\
  3(y_B-y_A) & = 3ax_0^2(x_1-x_0) + 2bx_0(x_1-x_0) + c(x_1-x_0) \label{eq:yB} \\
  3(y_C-2y_B+y_A) & = 3ax_0(x_1-x_0)^2 + b(x_1-x_0)^2 \label{eq:yC} \\
  y_D-3y_C+3y_B-y_A & = a(x_1-x_0)^3 \label{eq:yD}
\end{align}
Note, there are only constants on the right-hand side of all equations.  That is, this equation system is linear in the eight variables $x_A$, $x_B$, $x_C$, $x_D$, $y_A$, $y_B$, $y_C$, $y_D$.

Since MetaPost can solve linear equation systems, hacking equations~\ref{eq:xA} to~\ref{eq:yD} into MetaPost code and requesting a path segment
\begin{center}\ttfamily
  ($x_A$,$y_A$)..controls ($x_B$,$y_B$) and ($x_C$,$y_C$)..($x_D$,$y_D$)
\end{center}
returns the polynomial shaped curve we are looking for.

Internally, the \pkg\ package does not solve the original equation system, but a \emph{modified} variant, that is numerically slightly more robust.

Equations~\ref{eq:xA} to~\ref{eq:xD} can be written down explicitly as
\begin{align}
  x_A & = x_0 \label{eq:xA'} \\
  x_B & = x_0 + \frac{1}{3}(x_1-x_0) \label{eq:xB'} \\
  x_C & = x_1 - \frac{1}{3}(x_1-x_0) \label{eq:xC'} \\
  x_D & = x_1 \label{eq:xD'}
\end{align}

Additionally, we know that $D=(x_D,y_D)$ is a point on the polynomial.  Therefore, equation~\ref{eq:yD} of the original system can be replaced by
\begin{align}
  y_D & = ax_1^3 + bx_1^2 + cx_1 + d \label{eq:yD'}
\end{align}

Equations~\ref{eq:yA} to~\ref{eq:yC} of the original equation system and the new equations~\ref{eq:xA'} to~\ref{eq:yD'} constitute the modified equation system, that is solved in \pkg.

\nobreak
\bigskip
\raggedright
\parbox{\linewidth}{\itshape
  Happy \TeX ing!\par
  Stephan Hennig
}


\begin{thebibliography}{999}
\bibitem{mp:graph} \textsc{Hobby}, John~D., \emph{Drawing graphs with MetaPost}, \url{http://www.tug.org/docs/metapost/mpgraph.pdf}
\bibitem{mp:splines} \textsc{Luecking}, Dan, \emph{Macros to compute splines}, 2005, \url{CTAN:graphics/metapost/contrib/macros/splines/splines.pdf}
\end{thebibliography}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: t
%%% End: