diff options
Diffstat (limited to 'test-plans/circ.tex')
| -rw-r--r-- | test-plans/circ.tex | 479 |
1 files changed, 479 insertions, 0 deletions
diff --git a/test-plans/circ.tex b/test-plans/circ.tex new file mode 100644 index 0000000..48a177e --- /dev/null +++ b/test-plans/circ.tex @@ -0,0 +1,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} |