1 \documentclass[a4paper,twocolumn]{article}
2 \usepackage[german]{babel}
3 \usepackage[T1]{fontenc}
4 \usepackage[latin1]{inputenc}
5 \usepackage[showlabels,sections,floats,textmath,displaymath]{preview}
10 \advance\tdim by -2\fboxsep
11 \advance\tdim by -2\fboxrule
12 \setbox\chaos=\hbox\bgroup\begin{minipage}{\tdim}}
13 \def\endfframe{\end{minipage}\egroup\fbox{\box\chaos}}
21 \savebox{\raster}(\ones,\ones)
23 \put(0,0){\line(0,1){\ones}}
24 \put(0,0){\line(1,0){\ones}}
25 \multiput(0,0)(5,0){\fives}
27 \put(5,0){\line(0,1){\ones}}
28 \thinlines\multiput(1,0)(1,0){4}{\line(0,1){\ones}}
30 \multiput(0,0)(0,5){\fives}
32 \put(0,5){\line(1,0){\ones}}
33 \thinlines\multiput(0,1)(0,1){4}{\line(1,0){\ones}}
37 \title{Einfache Kurven auf Rastergrafiken}
38 \author{David Kastrup}
42 Es sollen hier einfache Methoden vorgestellt werden, um auf einer
43 Rastereinheit verschiedene Kurven darzustellen. Vorgestellt werden
44 Zeichenalgorithmen für Linien, Kreise und Hyperbeln. Die hier
45 hergeleiteten Gleichungen sind auch unter dem Namen {\tt DDA}s bekannt.
49 Bei den hier vorgestellten Algorithmen werden zunächst nur
50 Kurvenstücke betrachtet, die die folgenden Eigenschaften besitzen:
52 \item Sie lassen sich als Funktion $y = f(x)$ darstellen.
53 \item $y$ ist im betrachteten Bereich monoton, das heißt, entweder
54 durchgehend steigend oder durchgehend fallend.
55 \item Wenn $x$ sich um $1$ ändert, so ändert sich $y$ betragsmäßig
57 ($\left|\frac{\partial y}{\partial x}\right| \leq 1$).
60 \section{Die gerade Linie}
61 Wir betrachten hier zunächst nur die gerade Linie im ersten Oktanten,
62 die durch den Punkt $0 \choose 0$ geht. Alle anderen Linien lassen
63 sich durch Vertauschen von $x$ und~$y$ sowie Vorzeichenwechsel
64 erzeugen. Im ersten Oktanten gilt $x \geq y \geq 0$. Zum Zeichnen
65 einer Linie genügt es also, $x$ durchlaufen zu lassen und für $y$ die
66 dazugehörigen Werte zu berechnen und zu runden.
68 Die Gleichung einer Geraden durch $\Delta x \choose \Delta y$ lautet:
71 y = \frac{\Delta y}{\Delta x}x
74 Nun stellen wir $y$ als Summe eines ganzzahligen Wertes $e$ und eines
75 gebrochenen Wertes $f$ dar, für den gilt: $-0.5 \leq f < 0.5$. Somit
76 stellt dann $e$ den gewünschten, auf die nächste ganze Zahl gerundeten
77 $y$-Wert dar. Jetzt formen wir (\ref{lgi}) um:
79 e + f &=& x \frac{\Delta y}{\Delta x}\nonumber\\
80 e \Delta x + f \Delta x &=& x \Delta y\nonumber\\
81 f \Delta x - \left\lceil\frac{\Delta x}2\right\rceil &=&
82 x \Delta y - e \Delta x - \left\lceil\frac{\Delta x}2\right\rceil \label{lgii}
85 Den linken Ausdruck in (\ref{lgii}) bezeichnen wir jetzt mit $d$. Für
86 positive gerade Werte von $\Delta x$ ist offensichtlich $d < 0$ eine
87 zu~$f < 0.5$ equivalente Bedingung.
89 Für ungerade Werte von~$\Delta x$ ist $f < 0.5$ equivalent zu
91 Da $d$ stets eine ganze Zahl ist, ist dies wieder zu $d < 0$
94 % INTENTIONAL ERRORS! INTENTIONAL ERRORS! INTENTIONAL ERRORS!
96 % The following line should flag a PostScript error when previewing,
97 % but processing of other previews should continue.
99 Wird nun $\ifPreview\special{ps: junk}\fi f \geq 0.5$, wie sich durch
100 den Vergleich $d \stackrel{?}{<} 0$ feststellen läßt, so muß man
101 korrigieren, indem man $f$ um~1 erniedrigt und $e$ um~$1$ erhöht.
103 % The following line will make Ghostscript abort unexpectedly when
104 % previewing, but processing of other previews should continue.
106 $\ifPreview\special{ps: quit}\fi d$ muß dann auch entsprechend
109 Mit den angegebenen Formeln ergibt sich jetzt bei Berücksichtigung der
110 Einflüsse von $x$ und $e$ auf $d$ der in Tabelle~\ref{linalg}
111 angegebene Algorithmus. Eine optimierte C-function, die die
112 Oktantenaufteilung berücksichtigt, ist in Tabelle~\ref{linc} zu
113 finden. Einige hiermit gezeichnete Linien sind in
114 Abbildung~\ref{linpict} zu sehen.
116 \caption{Linienzugalgorithmus} \label{linalg}
119 \item Setze $x \gets 0$, $y \gets 0$, $d \gets
120 -\left\lceil\frac{\Delta x}2\right\rceil$
121 \item Wiederhole bis $x = \Delta x$
123 \item Zeichne Punkt an $x \choose y$
124 \item Setze $x \gets x + 1$, $d \gets d + \Delta y$
125 \item Falls $d \geq 0$
127 \item Setze $d \gets d - \Delta x$
128 \item Setze $y \gets y + 1$
135 \caption{Linienziehen in C} \label{linc}
140 /* (x,y) ist Koordinate des nicht
141 * gezeichneten Startpunktes, zeigt
142 * nachher auf gezeichneten Endpunkt
144 #define doline(dx,dy,advx,advy) { \
145 d = -(((i = dx) + 1) >> 1); \
148 if ((d += dy) >= 0) { \
154 } /* Grundalgorithmus 1. Oktant */
155 /* dx ist Distanz in unabh. Richtung, *
156 * dy in abh. Richtung, advx geht *
157 * in unabh. Richtung, advy in abh. */
159 #define docond(cond,advx,advy) { \
160 if (cond) doline(dx,dy,advx,advy) \
161 doline(dy,dx,advy,advx) \
162 } /* Grundalgorithmus 1./2. Oktant */
163 /* cond ist true falls |dx| > |dy| */
166 linedraw(int dx, int dy)
167 /* Von (x,y) nach (x+dx, y+dx). */
173 docond(dx > dy, ++x, ++y)
174 docond(dx > (dy = -dy), ++x, --y)
177 docond((dx = -dx) > dy,--x,++y)
178 docond((dx = -dx) > (dy = -dy),
185 \begin{picture}(\ones,\ones) \put(0,0){\usebox{\raster}}
200 \put(\x,\y){\circle*{1}}%}
203 \advance \d by \dy %}
206 \advance \d by -\dx %}
211 \advance \dy by -15 %}
214 \caption{Einige Linien}\label{linpict}
218 Wir betrachten hier nur den Achtelkreis im zweiten Oktanten
219 ($y \geq x \geq 0$). Hier gelten die oben angegebenen Beziehungen.
220 Alle anderen Achtelkreise lassen sich durch elementare Spiegelungen
223 Die Gleichung eines Kreises ist hier
225 y = ±\sqrt{r^2 - x^2}
228 Der Wert $y$ läßt sich darstellen als Summe einer ganzen Zahl $e$ und
229 einem Wert $f$ mit $-0.5 \leq f < 0.5$. Der Wertebereich von $f$ ist
230 so gewählt worden, damit $e$ einen auf ganze Zahlen gerundeten Wert
235 e + f&=&\sqrt{r^2 - x^2}\nonumber\\
236 \label{ggg}e^2 + 2ef + f^2&=&r^2 - x^2
239 Die Gleichung (\ref{ggg}) hat für $x+1$ folgende Form:
241 \label{hhh}e'^2 + 2e'f' + f'^2&=&r^2 - x^2 - 2x -1
244 Zieht man die Gleichung (\ref{ggg}) von (\ref{hhh}) ab, so ergibt sich
248 2e'f' + f'^2&=&2ef+f^2-2x-1\\
250 2e'f' + f'^2&=&2ef+f^2+2e-2x-2
253 Jetzt wird $2ef + f^2$ mit $m$ getauft. Also:
260 Wie groß ist jetzt $m$? Für $x=0$ ist es sicher $0$. Solange $e$
261 konstant bleibt, schrumpft $f$ stetig. Fällt $f$ unter $-0.5$, so
262 fällt $m$ (unter Vernachlässigung von $f^2$) unter $-e$. Dies wird
263 jetzt als Kriterium für einen Unterlauf von $f$ verwendet. Tritt
264 dieser auf, so muß $f$ um $1$ erhöht und $e$ um $1$ erniedrigt werden.
266 Um die Abfragebedingung zu vereinfachen, setzt man jetzt $q$ = $m+e$.
267 Der resultierende Algorithmus ist in Tabelle \ref{alg}, ein
268 optimiertes C-Programm ist in Tabelle \ref{prog} zu finden.
270 \caption{Kreiszeichenalgorithmus}\label{alg}
273 \item Setze $x\gets 0$, $y\gets r$, $q\gets r$
274 \item Wiederhole bis $x>y$:
276 \item Setze einen Punkt an $x \choose y$.
277 \item Setze $q\gets q-2x-1$
280 \item Setze $q\gets q + 2y-2$
281 \item Setze $y\gets y-1$
283 \item Setze $x\gets x+1$
289 \caption{Kreiszeichenprogramm}\label{prog}
294 fourfold(int x0, int y0, int x, int y)
295 /* Zeichne in Oktant 1,3,5,7 */
296 /* Wird benutzt, um Anfangs- und End- *
297 * Punkte nicht zweimal zu zeichnen */
306 eightfold(int x0, int y0, int x, int y)
307 /* Zeichne in allen Quadranten */
309 fourfold(x0,y0,x,y); /* 1357 */
310 fourfold(x0,y0,x,-y); /* 8642 */
314 circle(int x0, int y0, int r)
317 /* Die ersten vier Punkte */
318 for (x=0, y=q=r;; ) {
319 if ((q -= 2* x++ + 1) < 0)
323 eightfold(x0,y0,x,y);
327 /* Eventuell die letzten vier */
333 \begin{picture}(\ones,\ones)
334 \put(0,0){\usebox{\raster}}
343 \put(\x,\y){\circle*{1}}
344 \put(\y,\x){\circle*{1}}
355 \advance \ones by -10
359 \caption{Viertelkreise}\label{zeich}
362 \section{Einfache Hyperbeln}
363 Als letztes Beispiel betrachten wir hier Hyperbeln, die der Formel
364 $y = r^2\!/x$ genügen, und zwar im Bereich~$x \geq r$.
366 Mit dem Ansatz $y = e + f$ ergibt sich:
368 e+f &=& r^2\!/x\nonumber\\
369 ex + fx &=& r^2\nonumber\\
370 fx &=& r^2 - ex\label{phyp}
373 Für $x' = x+1$ hat nun (\ref{phyp}) die Form
376 f'x' &=& r^2 - ex - e\\
378 f'x' &=& r^2 - ex - e + x + 1
380 Setzt man jetzt $d = (2f + 1)x$, so ist $f < -0.5$ mit~$d < 0$
381 equivalent. Erreicht man diesen Fall unter Verwendung der Annahme
383 dann muß in bekannter Weise $f$ um~$1$ erhöht und $e$ um~$1$
387 Für $d'$ ergeben sich dann die folgenden Werte:
392 d' &=& d - 2e + 2x + 2 + 1
394 Daraus ergibt sich der in Tabelle~\ref{halg} angegebene
395 Hyperbelalgorithmus für den ersten Oktanten.
397 \caption{Hyperbelalgorithmus}\label{halg}
400 \item Setze $d \gets r$, $x \gets r$, $y \gets r$
401 \item Wiederhole bis zufrieden
403 \item Setze Punkt an $x \choose y$
404 \item Setze $x \gets x + 1$
405 \item Setze $d \gets d - 2y + 1$
408 \item Setze $d \gets d + 2x$
409 \item Setze $y \gets y - 1$
416 \caption{Hyperbeln in C}
421 four(int x0, int y0, int x, int y)
422 /* Hyperbeln sind nur in 4 Oktanten */
431 hyperb(int x0, int y0, int r, int dx)
435 for (x = y = d = r; dx--;) {
438 if ((d -= 2*y + 1) < 0) {
448 \begin{picture}(\ones,\ones)
449 \put(0,0){\usebox{\raster}}
462 \put(\x,\y){\circle*{1}}
463 \put(\y,\x){\circle*{1}}
477 \caption{Hyperbeln}\label{hzeich}