\documentclass[a4paper,twocolumn]{article}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[showlabels,sections,floats,textmath,displaymath]{preview}
\newbox\chaos
\newdimen\tdim
\def\fframe{%
\tdim=\columnwidth
\advance\tdim by -2\fboxsep
\advance\tdim by -2\fboxrule
\setbox\chaos=\hbox\bgroup\begin{minipage}{\tdim}}
\def\endfframe{\end{minipage}\egroup\fbox{\box\chaos}}
\unitlength 1mm
\newcount\fives
\fives 14
\newcount\ones
\ones\fives
\multiply \ones by 5
\newsavebox{\raster}
\savebox{\raster}(\ones,\ones)
{\thicklines
  \put(0,0){\line(0,1){\ones}}
  \put(0,0){\line(1,0){\ones}}
  \multiput(0,0)(5,0){\fives}
  {\begin{picture}(0,0)
      \put(5,0){\line(0,1){\ones}}
      \thinlines\multiput(1,0)(1,0){4}{\line(0,1){\ones}}
    \end{picture}}
  \multiput(0,0)(0,5){\fives}
  {\begin{picture}(0,0)
      \put(0,5){\line(1,0){\ones}}
      \thinlines\multiput(0,1)(0,1){4}{\line(1,0){\ones}}
    \end{picture}}
}
\begin{document}
\title{Einfache Kurven auf Rastergrafiken}
\author{David Kastrup}
\maketitle

\begin{abstract}
Es sollen hier einfache Methoden vorgestellt werden, um auf einer
Rastereinheit verschiedene Kurven darzustellen. Vorgestellt werden
Zeichenalgorithmen für Linien, Kreise und Hyperbeln. Die hier
hergeleiteten Gleichungen sind auch unter dem Namen {\tt DDA}s bekannt.
\end{abstract}

\section{Einführung}
Bei den hier vorgestellten Algorithmen werden zunächst nur
Kurvenstücke betrachtet, die die folgenden Eigenschaften besitzen:
\begin{enumerate}
\item Sie lassen sich als Funktion $y = f(x)$ darstellen.
\item $y$ ist im betrachteten Bereich monoton, das heißt, entweder
  durchgehend steigend oder durchgehend fallend.
\item Wenn $x$ sich um $1$ ändert, so ändert sich $y$ betragsmäßig
  höchstens um $1$
  ($\left|\frac{\partial y}{\partial x}\right| \leq 1$).
\end{enumerate}

\section{Die gerade Linie}
Wir betrachten hier zunächst nur die gerade Linie im ersten Oktanten,
die durch den Punkt $0 \choose 0$ geht. Alle anderen Linien lassen
sich durch Vertauschen von $x$ und~$y$ sowie Vorzeichenwechsel
erzeugen.  Im ersten Oktanten gilt $x \geq y \geq 0$. Zum Zeichnen
einer Linie genügt es also, $x$ durchlaufen zu lassen und für $y$ die
dazugehörigen Werte zu berechnen und zu runden.

Die Gleichung einer Geraden durch $\Delta x \choose \Delta y$ lautet:
\begin{equation}
\label{lgi}
y = \frac{\Delta y}{\Delta x}x
\end{equation}
%
Nun stellen wir $y$ als Summe eines ganzzahligen Wertes $e$ und eines
gebrochenen Wertes $f$ dar, für den gilt: $-0.5 \leq f < 0.5$.  Somit
stellt dann $e$ den gewünschten, auf die nächste ganze Zahl gerundeten
$y$-Wert dar. Jetzt formen wir (\ref{lgi}) um:
\begin{eqnarray}
e + f &=& x \frac{\Delta y}{\Delta x}\nonumber\\
e \Delta x + f \Delta x &=& x \Delta y\nonumber\\
f \Delta x - \left\lceil\frac{\Delta x}2\right\rceil &=& 
x \Delta y - e \Delta x - \left\lceil\frac{\Delta x}2\right\rceil \label{lgii}
\end{eqnarray}
%
Den linken Ausdruck in (\ref{lgii}) bezeichnen wir jetzt mit $d$.  Für
positive gerade Werte von $\Delta x$ ist offensichtlich $d < 0$ eine
zu~$f < 0.5$ equivalente Bedingung.

Für ungerade Werte von~$\Delta x$ ist $f < 0.5$ equivalent zu
$d + 0.5 < 0$.
Da $d$ stets eine ganze Zahl ist, ist dies wieder zu $d < 0$
equivalent.

% INTENTIONAL ERRORS!  INTENTIONAL ERRORS!  INTENTIONAL ERRORS!
%
% The following line should flag a PostScript error when previewing,
% but processing of other previews should continue.
%
Wird nun $\ifPreview\special{ps: junk}\fi f \geq 0.5$, wie sich durch
den Vergleich $d \stackrel{?}{<} 0$ feststellen läßt, so muß man
korrigieren, indem man $f$ um~1 erniedrigt und $e$ um~$1$ erhöht.
%
% The following line will make Ghostscript abort unexpectedly when
% previewing, but processing of other previews should continue.
%
$\ifPreview\special{ps: quit}\fi d$ muß dann auch entsprechend
angepaßt werden.

Mit den angegebenen Formeln ergibt sich jetzt bei Berücksichtigung der
Einflüsse von $x$ und $e$ auf $d$ der in Tabelle~\ref{linalg}
angegebene Algorithmus. Eine optimierte C-function, die die
Oktantenaufteilung berücksichtigt, ist in Tabelle~\ref{linc} zu
finden. Einige hiermit gezeichnete Linien sind in
Abbildung~\ref{linpict} zu sehen.
\begin{table}
  \caption{Linienzugalgorithmus} \label{linalg}
  \begin{fframe}
    \begin{enumerate}
    \item Setze $x \gets 0$, $y \gets 0$, $d \gets
      -\left\lceil\frac{\Delta x}2\right\rceil$
    \item Wiederhole bis $x = \Delta x$
      \begin{enumerate}
      \item Zeichne Punkt an $x \choose y$
      \item Setze $x \gets x + 1$, $d \gets d + \Delta y$
      \item Falls $d \geq 0$
        \begin{enumerate}
        \item Setze $d \gets d - \Delta x$
        \item Setze $y \gets y + 1$
        \end{enumerate}
      \end{enumerate}
    \end{enumerate}
  \end{fframe}
\end{table}
\begin{table}
\caption{Linienziehen in C} \label{linc}
\begin{fframe}
\small
\begin{verbatim}
extern int x,y;
/* (x,y) ist Koordinate des nicht
 * gezeichneten Startpunktes, zeigt
 * nachher auf gezeichneten Endpunkt
 */
#define doline(dx,dy,advx,advy) { \
  d = -(((i = dx) + 1) >> 1); \
  while (i--) { \
    advx; \
    if ((d += dy) >= 0) { \
      d -= dx; advy; \
    } \
    dot(x,y); \
  } \
  return; \
} /* Grundalgorithmus 1. Oktant */
/* dx ist Distanz in unabh. Richtung, *
 * dy in abh. Richtung, advx geht     *
 * in unabh. Richtung, advy in abh.   */

#define docond(cond,advx,advy) { \
  if (cond) doline(dx,dy,advx,advy) \
  doline(dy,dx,advy,advx) \
} /* Grundalgorithmus 1./2. Oktant */
/* cond ist true falls |dx| > |dy| */

void
linedraw(int dx, int dy)
/* Von (x,y) nach (x+dx, y+dx). */
{
  int i;

  if (dx >= 0) {
    if (dy >= 0)
      docond(dx > dy, ++x, ++y)
    docond(dx > (dy = -dy), ++x, --y)
  }
  if (dy >= 0)
    docond((dx = -dx) > dy,--x,++y)
  docond((dx = -dx) > (dy = -dy),
            --x, --y )
}
\end{verbatim}
\end{fframe}
\end{table}
\begin{figure}
  \begin{picture}(\ones,\ones) \put(0,0){\usebox{\raster}}
    \newcount\x
    \newcount\y
    \newcount\d
    \newcount\dx
    \newcount\dy
    \x 0
    \y 0
    \dx \ones
    \dy \ones
    \loop %{
    \d -\dx
    \divide \d by 2 %}
    \ifnum \dy > 0 %{
    {\loop %{
      \put(\x,\y){\circle*{1}}%}
      \ifnum \x < \ones %{
      \advance \x by 1
      \advance \d by \dy %}
      \ifnum \d > -1 %{
      \advance \y by 1
      \advance \d by -\dx %}
      \fi %}}
      \repeat}
    \advance \x by 5
    \advance \dx by -5
    \advance \dy by -15 %}
    \repeat
  \end{picture}
\caption{Einige Linien}\label{linpict}
\end{figure}

\section{Der Kreis}
Wir betrachten hier nur den Achtelkreis im zweiten Oktanten
($y \geq x \geq 0$). Hier gelten die oben angegebenen Beziehungen.
Alle anderen Achtelkreise lassen sich durch elementare Spiegelungen
erzeugen.

Die Gleichung eines Kreises ist hier
\begin{equation}
y = ±\sqrt{r^2 - x^2}
\end{equation}

Der Wert $y$ läßt sich darstellen als Summe einer ganzen Zahl $e$ und
einem Wert $f$ mit $-0.5 \leq f < 0.5$. Der Wertebereich von $f$ ist
so gewählt worden, damit $e$ einen auf ganze Zahlen gerundeten Wert
für $y$ darstellt.

Nun gilt:
\begin{eqnarray}
e + f&=&\sqrt{r^2 - x^2}\nonumber\\
\label{ggg}e^2 + 2ef + f^2&=&r^2 - x^2
\end{eqnarray}
%
Die Gleichung (\ref{ggg}) hat für $x+1$ folgende Form:
\begin{eqnarray}
\label{hhh}e'^2 + 2e'f' + f'^2&=&r^2 - x^2 - 2x -1
\end{eqnarray}
%
Zieht man die Gleichung (\ref{ggg}) von (\ref{hhh}) ab, so ergibt sich
nach Umsortieren:
\begin{eqnarray*}
        e' = e:\\
        2e'f' + f'^2&=&2ef+f^2-2x-1\\
        e' = e-1:\\
        2e'f' + f'^2&=&2ef+f^2+2e-2x-2
\end{eqnarray*}
%
Jetzt wird $2ef + f^2$ mit $m$ getauft. Also:
\begin{eqnarray*}
        e' = e:\\
        m'&=&m -2x-1\\
        e' = e-1:\\
        m'&=&m +2e-1 -2x-1
\end{eqnarray*}
Wie groß ist jetzt $m$? Für $x=0$ ist es sicher $0$. Solange $e$
konstant bleibt, schrumpft $f$ stetig. Fällt $f$ unter $-0.5$, so
fällt $m$ (unter Vernachlässigung von $f^2$) unter $-e$.  Dies wird
jetzt als Kriterium für einen Unterlauf von $f$ verwendet.  Tritt
dieser auf, so muß $f$ um $1$ erhöht und $e$ um $1$ erniedrigt werden.

Um die Abfragebedingung zu vereinfachen, setzt man jetzt $q$ = $m+e$.
Der resultierende Algorithmus ist in Tabelle \ref{alg}, ein
optimiertes C-Programm ist in Tabelle \ref{prog} zu finden.
\begin{table}
  \caption{Kreiszeichenalgorithmus}\label{alg}
  \begin{fframe}
    \begin{enumerate}
    \item Setze $x\gets 0$, $y\gets r$, $q\gets r$
    \item Wiederhole bis $x>y$:
      \begin{enumerate}
      \item Setze einen Punkt an $x \choose y$.
      \item Setze $q\gets q-2x-1$
      \item Falls $q<0$
        \begin{enumerate}
        \item Setze $q\gets q + 2y-2$
        \item Setze $y\gets y-1$
        \end{enumerate}
      \item Setze $x\gets x+1$
      \end{enumerate}
    \end{enumerate}
  \end{fframe}
\end{table}
\begin{table}
  \caption{Kreiszeichenprogramm}\label{prog}
  \begin{fframe}
    \small
\begin{verbatim}
void
fourfold(int x0, int y0, int x, int y)
/* Zeichne in Oktant 1,3,5,7 */
/* Wird benutzt, um Anfangs- und End- *
 * Punkte nicht zweimal zu zeichnen   */
{
  dot(x0+x,y0+y);
  dot(x0-y,y0+x);
  dot(x0-x,y0-y);
  dot(x0+y,y0-x);
}

void
eightfold(int x0, int y0, int x, int y)
/* Zeichne in allen Quadranten */
{
  fourfold(x0,y0,x,y);  /* 1357 */
  fourfold(x0,y0,x,-y); /* 8642 */
}

void
circle(int x0, int y0, int r)
{
  fourfold(x0,y0,0,r);
  /* Die ersten vier Punkte */
  for (x=0, y=q=r;; ) {
    if ((q -= 2* x++ + 1) < 0)
      q += 2* --y;
    if (x >= y)
      break;
    eightfold(x0,y0,x,y);
  }
  if (x==y)
    fourfold(x0,y0,x,y);
  /* Eventuell die letzten vier */
}
\end{verbatim}
  \end{fframe}
\end{table}
\begin{figure}
  \begin{picture}(\ones,\ones)
    \put(0,0){\usebox{\raster}}
    \newcount\x
    \newcount\y
    \newcount\q
    \loop
    {\x 0
      \y \ones
      \q \ones
      \loop
      \put(\x,\y){\circle*{1}}
      \put(\y,\x){\circle*{1}}
      \advance \q by -\x
      \advance \x by 1
      \advance \q by -\x
      \ifnum \x < \y
      \ifnum \q < 0
      \advance \y by -1
      \advance \q by \y
      \advance \q by \y
      \fi
      \repeat}
    \advance \ones by -10
    \ifnum \ones > 0
    \repeat
  \end{picture}
  \caption{Viertelkreise}\label{zeich}
\end{figure}

\section{Einfache Hyperbeln}
Als letztes Beispiel betrachten wir hier Hyperbeln, die der Formel
$y = r^2\!/x$ genügen, und zwar im Bereich~$x \geq r$.

Mit dem Ansatz $y = e + f$ ergibt sich:
\begin{eqnarray}
  e+f &=& r^2\!/x\nonumber\\
  ex + fx &=& r^2\nonumber\\
  fx &=& r^2 - ex\label{phyp}
\end{eqnarray}
\pagebreak[2]
Für $x' = x+1$ hat nun (\ref{phyp}) die Form
\begin{eqnarray*}
  e' = e:\\
  f'x' &=& r^2 - ex - e\\
  e' = e - 1:\\
  f'x' &=& r^2 - ex - e + x + 1
\end{eqnarray*}
Setzt man jetzt $d = (2f + 1)x$, so ist $f < -0.5$ mit~$d < 0$
equivalent. Erreicht man diesen Fall unter Verwendung der Annahme
$e' = e$,
dann muß in bekannter Weise $f$ um~$1$ erhöht und $e$ um~$1$
vermindert werden.

\pagebreak
Für $d'$ ergeben sich dann die folgenden Werte:
\begin{eqnarray*}
  e' = e:\\
  d' &=& d - 2e + 1\\
  e' = e - 1:\\
  d' &=& d - 2e + 2x + 2 + 1
\end{eqnarray*}
Daraus ergibt sich der in Tabelle~\ref{halg} angegebene
Hyperbelalgorithmus für den ersten Oktanten.
\begin{table}
  \caption{Hyperbelalgorithmus}\label{halg}
  \begin{fframe}
    \begin{enumerate}
    \item Setze $d \gets r$, $x \gets r$, $y \gets r$
    \item Wiederhole bis zufrieden
      \begin{enumerate}
      \item Setze Punkt an $x \choose y$
      \item Setze $x \gets x + 1$
      \item Setze $d \gets d - 2y + 1$
      \item Falls $d < 0$
        \begin{enumerate}
        \item Setze $d \gets d + 2x$
        \item Setze $y \gets y - 1$
        \end{enumerate}
      \end{enumerate}
    \end{enumerate}
  \end{fframe}
\end{table}
\begin{table}
  \caption{Hyperbeln in C}
  \begin{fframe}
    \small
\begin{verbatim}
void
four(int x0, int y0, int x, int y)
/* Hyperbeln sind nur in 4 Oktanten */
{
  dot(x0+x,y0+y);
  dot(x0+y,y0+x);
  dot(x0-x,y0-y);
  dot(x0-y,y0-x);
}

void
hyperb(int x0, int y0, int r, int dx)
{
  int d, x, y;

  for (x = y = d = r; dx--;) {
    four(x0,y0,x,y);
    ++x;
    if ((d -= 2*y + 1) < 0) {
      d += 2*x;
      --y;
    }
  }
}
\end{verbatim}
  \end{fframe}
\end{table}
\begin{figure}
  \begin{picture}(\ones,\ones)
    \put(0,0){\usebox{\raster}}
    \newcount\x
    \newcount\y
    \newcount\q
    \newcount\r
    \r\ones
    \loop
    \advance \r by -10
    \ifnum \r > 0
    {\x \r
      \y \r
      \q \r
      \loop
      \put(\x,\y){\circle*{1}}
      \put(\y,\x){\circle*{1}}
      \ifnum \x < \ones
      \advance \x by 1
      \advance \q by -\y
      \advance \q by -\y
      \advance \q by 1
      \ifnum \q < 0
      \advance \q by \x
      \advance \q by \x
      \advance \y by -1
      \fi
      \repeat}
    \repeat
  \end{picture}
  \caption{Hyperbeln}\label{hzeich}
\end{figure}
\end{document}