%%% bpolynomial.tex %%% Copyright 2007 Stephan Hennig % % 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.()} \end{center} defines two new macros \begin{center} \cmd{.getPath()} \end{center} and \begin{center} \cmd{.eval()} \end{center} that do the real work. \subsection{Macro \cmd{.getPath}} Macro \cmd{.getPath(xmin, xmax)} returns a path exactly matching the polynomial defined by \cmd{newBPolynomial.} 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{.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{.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{.eval}} The other macro defined by \cmd{newBPolynomial.}, macro \cmd{.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.} saves the coefficients passed as arguments in variables \cmd{.a}, \cmd{.b}, \cmd{.c} and \cmd{.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: