summaryrefslogtreecommitdiff
path: root/elpa/auctex-13.1.3/circ.tex
diff options
context:
space:
mode:
Diffstat (limited to 'elpa/auctex-13.1.3/circ.tex')
-rw-r--r--elpa/auctex-13.1.3/circ.tex479
1 files changed, 479 insertions, 0 deletions
diff --git a/elpa/auctex-13.1.3/circ.tex b/elpa/auctex-13.1.3/circ.tex
new file mode 100644
index 0000000..48a177e
--- /dev/null
+++ b/elpa/auctex-13.1.3/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}