Go to:
Gentoo Home
Documentation
Forums
Lists
Bugs
Planet
Store
Wiki
Get Gentoo!
Gentoo's Bugzilla – Attachment 101333 Details for
Bug 154240
please stabilise app-emacs/auctex-11.83 and app-text/dvipng-1.8
Home
|
New
–
[Ex]
|
Browse
|
Search
|
Privacy Policy
|
[?]
|
Reports
|
Requests
|
Help
|
New Account
|
Log In
[x]
|
Forgot Password
Login:
[x]
circ.tex
circ.tex (text/plain), 12.59 KB, created by
Christian Faulhammer (RETIRED)
on 2006-11-06 06:00:00 UTC
(
hide
)
Description:
circ.tex
Filename:
MIME Type:
Creator:
Christian Faulhammer (RETIRED)
Created:
2006-11-06 06:00:00 UTC
Size:
12.59 KB
patch
obsolete
>\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}
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Raw
Actions:
View
Attachments on
bug 154240
: 101333