%%% 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: 
