Anwendungsbericht 17

Zentrum für Paralleles Rechnen

Die Firma Elisabeth Wahle Verlag und EDV-System in Bergisch Gladbach entwickelt und pflegt ein Softwarepaket für Isolierklempner und Feinblechverarbeiter unter MS-DOS. Diese Software berechnet die Koordinaten-Tabelle einer Abwicklung von Isolierkörpern. Für 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ösungsvorschlag erarbeitet. Zielsetzung war dabei nicht, ein möglichst 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ösungsansatz erläutert. Zusätzlich wurde eine kurze Beschreibung und eine Darstellung des Verfahrens in einer Pseudoprogrammiersprache zur Verfügung gestellt. Bei einem abschließenden Besuch teilte uns Herr Wahle mit, daß der Algorithmus erfolgreich in das Softwarepaket eingearbeitet wurde und sich im praktischen Einsatz bewährt.

Rechter Hand eine Abbildung aus Hubert Wahle: “Modellbuch für Isolierklempner und Feinblechverarbeiter”. Die Wiedergabe erfolgt mit freundlicher Genehmigung des Verlages Elisabeth Wahle.

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übergestellt, das Automodell, das im 3-dimensionalen Raum lebt, auf die Ebene des Pappbogens abzuwickeln. Normalerweise wird die Stabilität des fertigen Modells durch Verkleben erreicht. Bei der Abbildung des Autos in die Ebene muß man hierzu die richtigen Zugaben berücksichtigen.

Vor ganz ähnlichen Problemen steht man, wenn man blecherne Körper zur Isolierung von z.B. Industrieschornsteinen herstellen will. Der geometrische Körper, der im 3-dimensionalen lebt, wird in die Ebene eingebettet, die Abwicklung aus dem Blech ausgeschnitten und zu dem erwünschten Körper gebogen. Hierbei können Zugaben notwendig werden für

1. Abkantungen, Rundungen, Schweif, Bördel usw.

2. Überlappungen für Längsnähte

3. Schnittverluste.

Das Problem, bei dem wir um algorithmische Unterstützung gebeten wurden, bestand nun darin, für einen abgewickelten Körper, gegeben als Punktfolge der Eckpunkte eines Polygons, das Randpolygon der Zugabe einer vorgegebenen Dicke zu berechnen. Daß diese Aufgabe sich nicht trivial lösen läßt, mache man sich an Abbildung ?? klar.

Zentrum für Paralleles Rechnen Arbeitsgruppe Prof. Dr. A. Bachem

Telefon: (0221) 470–6030

Hausanschrift: Weyertal 80, D-50931 Köln Telefax: (0221) 470–5160 Postanschrift: ZPR, Universität zu Köln, Albertus-Magnus-Platz, D-50923 Köln Email: zpr@zpr.uni-koeln.de

Abbildung 1: Überraschende Schwierigkeiten

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

Modellierung und Lösungsansatz

Die Abwicklung ohne Zugabe ist gegeben als ein einfaches Polygon, also als Punktfolge b_{1}, a_{1}, …, a_{k}, b_{2}. Dabei seien die Randpunkte so gegeben, daß 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_{1}a_{1} liegt, ansonsten sei b_{3} = +∞. Dann sei P = b_{3}, a_{1}, …, a_{k}, b_{3} ein einfaches geschlossenes Polygon. Ferner nehmen wir an, daß b_{1}a_{1}a_{2} und a_{k−1}a_{k}b_{2} eine Rechtskurve bilden.

Die Zugabe der Dicke r ist definiert als

{x ∈ IR^{2} | x hat von a_{1}, …, a_{k} Abstand ≤ r und liegt im Innengebiet von P }.

Aufgabe ist es nun, die von a_{1}, …, a_{k} induzierte Randlinie der Zugabe zu berechnen. Dabei sollen die entstehenden Kreisbögen durch die beiden Geradensegmente ersetzt werden, die man erhält, wenn man die benachbarten Geradensegmente verlängert und zum Schnitt bringt. (Beachte, Kreisbögen können nur an Rechtskurven auftreten).

Die Punkte a_{i−1}a_{i}a_{i+1} bilden dabei eine Rechtskurve, wenn det(a_{i−1} − a_{i}, a_{i+1} − a_{i}) > 0 ist. Ist diese Determinante negativ, so bilden die Punkte eine 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 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ämlich an den Linkskurven von Vorteil, der Schnittansatz liefert hingegen an den Rechtskurven das Gewünschte. Auf diese Weise erhält man eine Schar von Geradensegmenten, deren Einhüllende das von b_{3} aus sichtbare Randpolygon der Zugabe ist.

Zur Berechnung der Einhüllenden 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üllenden hinzugenommen und wir fahren mit dem neuen Segment fort.

Pseudo-Code

Input: Ein einfacher Kantenzug b_{1}, a_{0}, …, a_{k}, b_{2} mit den oben angegebenen Eigenschaften.

Output: Ein einfacher Kantenzug d_{1}, …, d_{l}, der die Einhüllende der Zugabe mit zugespitzten Rundungen beschreibt.

/* Zunächst berechnen wir die r-parallelen Segmente s_{i} = l_{i}r_{i}. */ Berechne l_{1} als den Schnittpunkt der Geraden durch b_{1}, a_{1} und der r-Parallelen zu a_{1}, a_{2}; for i = 2 to k − 1 if a_{i−1}a_{i}a_{i+1} Rechtskurve Berechne r_{i−1} = l_{i} als den Schnittpunkt der r-Parallelen zu a_{i−1}a_{i} und a_{i}a_{i+1}; else Seien o⃗_{l}, o⃗_{r} die Vektoren senkrecht auf a_{i−1}a_{i} bzw. auf a_{i}a_{i+1} mit ∥o⃗_{l}∥ = ∥o⃗_{r}∥ = r; r_{i−1} = a_{i} + o⃗_{l}; l_{i} = a_{i} + o⃗_{r}; endif 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üllende. */ d_{1} = l_{1}; Indexzähler=2; i=1; while i < k − 1 /*teste Segment e_{i}*/ schnitt=2; for j = i + 1 to k − 1 /*gegen alle folgenden Segmente */ /* Hier ist Vorsicht geboten, da es nur bei gutartigen Eingaben ausreicht, gegen ausschließlich die folgenden Geradensegmente zu testen. Im allgemeinen ist es nötig, gegen alle Geradensegmente zu testen (also j von 1 laufen lassen, i überspringen). Es können verschieden Abschnitte eines Segmentes an unterschiedlichen Stellen der Zugabe auftreten. Bei der Berechnung des kleinsten λs muß dann berücksichtigt werden, daß dies größer sein muß als das λ für den zuletzt verwendeten Punkt der Strecke. */ if Das Segment \overline{l_{i}, r_{i}} schneidet das Segment \overline{l_{j}, r_{j}} in l_{i} + λ ∗ \overrightarrow{(r_{i} − l_{i})} und λ ≤ schnitt schnitt = λ; nachbar = j; endif; next j; d_{Indexzähler} = l_{i} + schnitt ∗ (\overrightarrow{r_{i} − l_{i}}); inkrementiere Indexzähler; l_{nachbar} = d_{Indexzähler}; i=nachbar; endwhile;

Ansprechpartner

Dr. Sándor Fekete Dr. Winfried Hochstättler Zentrum für paralleles Rechnen Tel.: (0221) 470-6024 (6023) Köln, den 5. Februar 1998.