\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}