
\documentstyle[din_a4, german, anwendungsbericht]{article}
\def\R{\hbox{I\hskip-0.23em R}}
\catcode`@=11
\def\vek#1{\mathchoice{\myoverrightarrow{\displaystyle{#1}}}
                    {\myoverrightarrow{\textstyle{#1}}}
                    {\myoverrightarrow{\scriptstyle{#1}}}
                    {\myoverrightarrow{\scriptscriptstyle{#1}}}}

\def\myoverrightarrow#1{\vbox{\m@th\ialign{##\crcr
      \rightarrowfill\crcr\noalign{\kern-\p@\nointerlineskip}
      $\hfil{#1}\hfil$\crcr}}}
\catcode`@=12

\frenchspacing
\parindent 0pt
\parskip 4pt
\begin{document}
\kopf{17}
\mbox{                                              % NICHT AENDERN !!
  \begin{minipage}[b]{9.5cm}                         % NICHT AENDERN !!
    Die Firma Elisabeth Wahle Verlag und EDV-System in Bergisch
    Gladbach entwickelt und pflegt ein Softwarepaket f\"ur
    Isolierklempner und Feinblechverarbeiter unter MS-DOS.  Diese
    Software berechnet die Koordinaten-Tabelle einer Abwicklung von
    Isolierk\"orpern. F\"ur das Teilproblem der Zugabenberechnung
    wandte sich Herr Hubert Wahle an unsere Gruppe und bat um
    mathematische Beratung.\\ Nach einem ersten Sondierungstreffen
    wurde die Problemstellung in einer zweiten Sitzung mit einem
    Programmierer der Firma aufgearbeitet.  Daraufhin wurde von uns
    innerhalb von zwei Wochen ein L\"osungsvorschlag erarbeitet.
    Zielsetzung war dabei nicht, ein m\"oglichst schnelles Verfahren
    zu erarbeiten, sondern einen praktikablen, einfachen Algorithmus
    zu finden, der leicht zu implementieren und zu pflegen ist. \\ In
    einem weiteren Treffen haben wir einem Programmierer der Firma
    unseren L\"osungsansatz erl\"autert.  Zus\"atzlich wurde eine
    kurze Beschreibung und eine Darstellung des Verfahrens in einer
    Pseudoprogrammiersprache zur Verf\"ugung gestellt.\\ Bei einem
    abschlie"senden Besuch teilte uns Herr Wahle mit, da"s der
    Algorithmus erfolgreich in das Softwarepaket eingearbeitet wurde
    und sich im praktischen Einsatz bew\"ahrt.\bigskip \\ Rechter Hand
    eine Abbildung aus Hubert Wahle: ``Modellbuch f"ur Isolierklempner
    und Feinblechverarbeiter''. Die Wiedergabe erfolgt mit
    freundlicher Genehmigung des Verlages Elisabeth Wahle.
\end{minipage}
\begin{minipage}[b]{0.3cm}~
\end{minipage}
\epsfxsize=6cm
$$ \epsfbox{wahle1.ps}$$ }

\section*{Problemstellung}
Jeder kennt die Modellautos aus Pappe, die aus einem Bastelbogen
ausgeschnitten und zusammengeklebt werden.  Derjenige, der einen
solchen Bogen erstellt, sieht sich dem Problem gegen\"ubergestellt,
das Automodell, das im 3-dimensionalen Raum lebt, auf die Ebene des
Pappbogens abzuwickeln.  Normalerweise wird die Stabilit\"at des
fertigen Modells durch Verkleben erreicht. Bei der Abbildung des Autos
in die Ebe\-ne mu"s man hierzu die richtigen Zugaben ber\"ucksichtigen.

Vor ganz \"ahnlichen Problemen steht man, wenn man blecherne K\"orper
zur Isolierung von z.B.\ Industrieschornsteinen herstellen will. Der
geometrische K\"orper, der im 3-dimensionalen lebt, wird in die Ebene
eingebettet, die Abwicklung aus dem Blech ausgeschnitten und zu dem
erw\"unschten K\"orper gebogen. Hierbei k\"onnen Zugaben notwendig
werden f\"ur
\begin{enumerate}
 \item Abkantungen, Rundungen, Schweif, B\"ordel usw.\ 
 \item \"Uberlappungen f\"ur L\"angsn\"ahte
 \item Schnittverluste.
\end{enumerate}

Das Problem, bei dem wir um algorithmische Unterst\"utzung gebeten
wurden, bestand nun darin, f\"ur einen abgewickelten K\"orper, gegeben
als Punktfolge der Eckpunkte eines Polygons, das Randpolygon der
Zugabe einer vorgegebenen Dicke zu berechnen. Da"s diese Aufgabe sich
nicht trivial l\"osen l\"a"st, mache man sich an Abbildung
~\ref{abbildung} klar.

\begin{figure}[htp]
       $$\epsfbox{doofetm.eps}$$
\caption{"Uberraschende Schwierigkeiten\label{abbildung}}
\end{figure}

Die folgenden zwei Abschnitte geben im wesentlichen die Unterlagen
wieder, die wir der Firma Wahle zur Verf\"ugung gestellt haben.

\section*{Modellierung und L"osungsansatz}

Die Abwicklung ohne Zugabe ist gegeben als ein einfaches Polygon, also
als Punktfolge $b_1,a_1,\ldots,a_k,b_2$. Dabei seien die Randpunkte so
gegeben, da"s die $y$-Koordinate von $b_1$ kleiner als die
$y$-Koordinate von $a_1$ und die $y$-Koordinate von $b_2$ kleiner als
die $y$-Koordinate von $a_k$ ist. Bezeichne ferner $b_3$ den
Schnittpunkt der Geraden durch $b_1$ und $a_1$, bzw.\ durch $b_2$ und
$a_k$, falls dieser oberhalb $a_1$ auf $b_1a_1$ liegt, ansonsten sei
$b_3 = + \infty$. Dann sei $P=b_3,a_1,\ldots,a_k,b_3$ ein einfaches
geschlossenes Polygon. Ferner nehmen wir an, da"s $b_1a_1a_2$ und
$a_{k-1}a_kb_2$ eine Rechtskurve bilden.

Die {\em Zugabe der Dicke $r$} ist definiert als

$$\{x\in \R^2 \mid x \mbox{ hat von } a_1,\ldots,a_k
\mbox{ Abstand } \le r \mbox{ und liegt im Innengebiet von }P\}.$$


Aufgabe ist es nun, die von $a_1,\ldots,a_k$ induzierte Randlinie der
Zugabe zu berechnen. Dabei sollen die entstehenden Kreisb"ogen durch
die beiden Geradensegmente ersetzt werden, die man erh"alt, wenn man
die benachbarten Geradensegmente verl"angert und zum Schnitt bringt.
(Beachte, Kreisb"ogen k"onnen nur an Rechtskurven auftreten).

Die Punkte $a_{i-1}a_ia_{i+1}$ bilden dabei eine {\em Rechtskurve},
wenn $\det(a_{i-1}-a_i,a_{i+1}-a_i) > 0$ ist. Ist diese Determinante
negativ, so bilden die Punkte eine {\em Linkskurve}.

Zwei naheliegende Ideen zur Berechnung des Randpolygons der Zugabe
sind einmal, die Berechnung paralleler gleichlanger Segmente zu dem
Polygon im Abstand $r$ -- wir bezeichnen sie als {\em
  $r$-Parallelen} -- und andererseits die Berechnung der Schnitte der zu
den Segmenten parallelen Geraden. Unser Ansatz mischt diese beiden
Ideen. Die gleichlangen Segmente sind n"amlich an den Linkskurven von
Vorteil, der Schnittansatz liefert hingegen an den Rechtskurven das
Gew"unschte.  Auf diese Weise erh"alt man eine Schar von
Geradensegmenten, deren Einh"ullende das von $b_3$ aus
sichtbare Randpolygon der Zugabe ist.


%$$\epsfbox{figs/wahle.ps} $$

Zur Berechnung der Einh"ullenden dieser Segmente berechnen wir
sukzessive zu allen Segmenten die Schnittpunkte -- falls sie
existieren. Dann fahren wir auf den zum Originalpolygon parallelen
Segmenten entlang, bis wir auf ein dieses Segment schneidendes
weiteres Segment treffen. Der Schnittpunkt wird zur Einh"ullenden
hinzugenommen und wir fahren mit dem neuen Segment fort.

\section*{Pseudo-Code}
\label{Pseudocode}
Input: Ein einfacher Kantenzug $b_1,a_0,\ldots, a_k,b_2$ mit den oben
angegebenen Eigenschaften.

\noindent
Output: Ein einfacher Kantenzug $d_1,\ldots,d_l$, der die Einh"ullende
der Zugabe mit zugespitzten Rundungen beschreibt.

\begin{tabbing}
if\=if\=if\=if\=if\=if\=if\=if\=if\=\kill

/* Zun"achst berechnen wir die $r$-parallelen Segmente $s_i=l_ir_i$.
*/\\ 
Berechne $l_1$ als den Schnittpunkt der Geraden durch $b_1,a_1$ und
der $r$-Parallelen zu $a_1,a_2$; \\ 
\+{\bf for} $i = 2$ to $k-1$ \\
\+{\bf if }$a_{i-1}a_ia_{i+1}$ Rechtskurve\\ 
\-Berechne $r_{i-1}=l_i$ als den Schnittpunkt der $r$-Parallelen zu
$a_{i-1}a_i$ und $a_ia_{i+1}$;\\ 
\+{\bf else} \\

Seien $\vec{o_l}, \vec{o_r}$ die Vektoren senkrecht auf $a_{i-1}a_i$ bzw.\ auf $a_ia_{i+1}$ mit $\|\vec{o_l}\|=\|\vec{o_r}\|=r$;\\ 

 $r_{i-1}=a_i+\vec{o_l}$;\\
\- $l_{i}=a_i+\vec{o_r}$;\\
\-{\bf endif}\\
{\bf next} i;\\
Berechne $r_k$ als den Schnittpunkt der Geraden durch $b_2,a_k$ und
der $r$-Parallelen zu $a_{k-1},a_k$; \\ 
\>\\
/* In der folgenden Schleife konstruieren wir die Einh"ullende. */\\
$d_1=l_1$; \\
Indexz"ahler=2; \\
i=1;\\
\+{\bf while} $i < k-1\mbox{~~~~~~~~~~~~~~~~~~}$   /*teste Segment $e_i$*/\\
schnitt=2;\\
\+{\bf for} $j = i+1$ to $k-1\mbox{~~~~~~~~~}$  /*gegen alle folgenden Segmente
*/\\ 

\parbox{15cm}{
  /* Hier ist Vorsicht geboten, da es nur bei gutartigen Eingaben
  ausreicht, gegen ausschlie"slich die folgenden Geradensegmente zu
  testen. Im allgemeinen ist es n"otig, gegen alle Geradensegmente zu
  testen (also $j$ von 1 laufen lassen, $i$ "uberspringen). Es k"onnen
  verschieden Abschnitte eines Segmentes an unterschiedlichen Stellen
  der Zugabe auftreten. Bei der Berechnung des kleinsten $\lambda$s
  mu"s dann ber"ucksichtigt werden, da"s dies gr"o"ser sein mu"s als
  das $\lambda$ f"ur den zuletzt verwendeten Punkt der Strecke.  */}\\ 

\+{\bf if} Das Segment $\overline{l_i,r_i}$ schneidet das Segment
$\overline{l_j,r_j}$ in $l_i + \lambda \ast \vek{(r_i - l_i)}$ und
$\lambda \le schnitt$\\ 
$schnitt=\lambda$; \\
\-$nachbar=j$;\\
\-{\bf endif};\\
{\bf next} $j$;\\
$d_{Indexz"ahler}=l_i + schnitt \ast (\vek{r_i - l_i})$;\\
inkrementiere Indexz"ahler;\\
$l_{nachbar}=d_{Indexz"ahler};$\\
\- i=nachbar;\\
{\bf endwhile;}
\end{tabbing}


\rule{\textwidth}{1pt}                           % NICHT AENDERN !!

{\Large \bf Ansprechpartner}                       % NICHT AENDERN !!

\begin{tabular}{ll}                              % NICHT AENDERN !!
Dr.~S\'andor Fekete           &     \\
Dr.~Winfried Hochst"attler    &     \\
Zentrum f\"ur paralleles Rechnen \\
Tel.: (0221) 470-6023  (6012) \\
\end{tabular}                                    % NICHT AENDERN !!

K\"oln, den \today.
%END TEXT
\end{document}










