Source

auctex / preview / circ.tex

Full commit
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
\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}