5.2.2.2 Zweidimensionale geometrische Datenaufbereitung

Ziel ist es, aus einem zweidimensionalen Gitter durch geometrische Operationen ein dreidimensionales Gitter zu produzieren. Dazu sind zunächst die einzelnen Masken, wie sie in den Abbildungen 5.30 und 5.31 gezeigt werden, symbolisch aufeinander zu legen (Abbildung 5.32) und die neu entstandenen Flächen zu bestimmen und zu vergittern (Abbildung 5.33). Die Kontaktzuordnungen und Materialreferenzen werden nicht mitgeführt. Bis zum Aufbau des dreidimensionalen Gitters wird nur die Geometrie aufbereitet.

Algorithmisch gesehen sind zunächst alle Kanten zu bestimmen, die aufeinanderliegen und parallel ausgerichtet sind. Diese sind zu neuen Kanten zusammenzufassen und alle Schnittpunkte der neuen Kanten mit anderen neuen Kanten sind zu bestimmen. An den Schnittpunkten sind die Kanten aufzutrennen und diese zerlegten Kanten zum Aufbau der Flächen in eine spezielle Kantenliste einzutragen.

Die Kantenliste ist eine Doubly Connected Edge List (DCEL), diese benützt die Tatsache, daß in zweidimensionalen Gebieten maximal zwei Flächen an einer Kante liegen können. Um den Vorteil der DCEL zum Aufbau von zweidimensionalen Flächen aus einer Menge von Kanten zu erklären, sollen zunächst die Struktur und der Zugriff auf die Kanten einer Fläche durch ein einfaches Beispiel erläutert werden. Die Abbildung 5.34 zeigt einen Ausschnitt aus Abbildung 5.32. Die Datenstruktur besteht aus Flächen ,,f``, gerichteten Kanten ,,k`` und Punkten ,,p``. Aus diesem Modell resultieren drei Listen, wobei die Punktliste für die weiteren Erklärungen außer acht gelassen wird, da sie nur die Koordinatenpaare enthält. Die Flächenliste enthält pro Eintrag nur die Referenz zu einer Kante ,,ik`` in der Kantenliste. Die Referenzen sollen hier normale Indizes und keine Adreßzeiger sein. Generell folgt aus i, wenn es an erster Stelle eines Variablennamens liegt, daß es sich um eine Referenz handelt.

  
Abbildung 5.34: Kantenbezeichnungen

Flächenliste: f

Kantenliste: k

Die Kantenliste enthält eine Referenz auf den Anfangs- und Endpunkt () der jeweiligen Kante in die Liste der Punkte. Die nächsten beiden Einträge referenzieren die linke und die rechte Fläche (, ) entlang der gerichteten Kante. Die letzten beiden Einträge referenzieren die vorhergehende Kante , gesehen vom Kantenanfangspunkt, und die Folgekante in der Art, daß die vorhergehende oder Folgekante im jeweiligen Punkt die nächste Kante im Uhrzeigersinn ist. Die beiden Tabellen der Flächen- und Kantenliste zeigen den Aufbau der Flächen . Die Fläche referenziert die Kante . Um zu überprüfen, ob die Kante im mathematisch positiven Sinn orientiert ist, überprüft man, ob mit der jeweiligen Flächennummer übereinstimmt. Da in der Kante an der rechten Seite zu finden ist (), wird als nächste Kante über gewählt und nicht . Da die Kante mathematisch positiv orientiert ist - zeigt auf die Kante 12 - findet man die nächste Kante mit . Nach dem gleichen Schema sind die Kanten und zu finden. Ist die nächste Kantenreferenz gleich der ersten Kantennummer, so hat man alle Kanten einer Fläche gefunden. Bei Außenkanten ist eine Flächenreferenz oder auf null gesetzt.

Wie man die DCEL-Struktur aus der unverketteten Kantenliste und der Punktliste aufbaut, soll nun erklärt werden. Zu diesem Zweck muß die Punktliste um einen Zeiger

auf ein Radial erweitert werden. Ein Radial enthält alle Kantenreferenzen, die von einem Punkt ausgehen und je einen Marker (A/E), der anzeigt, ob Anfang oder Ende der Kante am Punkt anliegt. Die Kanten bzw. Kantenreferenzen werden im Uhrzeigersinn sortiert in das Radial eingetragen. Ein Radial wird am besten in einer geschlossenen verketteten Liste implementiert. Der folgende Algorithmus bildet aus den Kanten gültige Flächen:

Das Programm ,,genAllFaces`` setzt alle linken und rechten Flächenreferenzen und auf unbenutzt. Danach wird eine Startkante bzw. die Referenz ausgewählt. Eine gültige Startkante ist eine Kante, die noch eine unbenutzte Flächenreferenz aufweist. Zum Aufbau einer Fläche werden von der Startkante ausgehend in der innersten Schleife solange Folgekanten gesucht, bis wieder die Startkante erreicht wurde (iks = ikx). Die Folgekante wird dadurch gefunden, daß man bei einer Kante, wo die linke Flächenreferenz gerade besetzt wurde, also die Orientierung der Kante im mathematisch positiven Sinn gegeben ist, die Endpunktreferenz auflöst und im angeschlossenen Radial nach der gerade aktuellen Kante sucht und die nächste Kante im Uhrzeigersinn im Radial als Folgekante verwendet.

Die Funktion ,,getNextEdgeOnClock`` gibt bei gegebenen Punkt und Kante die Referenz auf die Folgekante, im Uhrzeigersinn gesehen, zurück. Wurde gerade die rechte Flächenreferenz von der aktuellen Flächennummer belegt, so ist der Funktion ,,getNextEdgeOnClock`` der Kantenanfang zu übergeben.

Wird als Beispiel gerade Fläche aufgebaut, und die Startkante ist , so ist die erste Folgekante , da diese Kante im Radial von die Folgekante von ist. Da die Kante vom Punkt weg orientiert ist, muß mit der aktuellen Flächennummer belegt werden. Danach folgt in die Kante , die zum Punkt hin orientiert ist und damit die aktuelle Flächennummer mit 13 belegt. Die Kante vervollständigt das Polygon, da im Punkt die Abbruchbedingung (iks = ikx) erreicht wird.

Der Algorithmus muß noch vervollständigt werden, um die Flächenliste brauchbar zu machen. Es wurde nicht berücksichtigt, daß ein Umlauf im Uhrzeigersinn am Außenrand ein Polygon mit negativer Fläche produziert, das vom Absolutbetrag her genauso groß ist wie die Summe aller anderen Flächen der Liste. Dieses Polygon mit negativer Orientierung muß nachträglich aus der Liste entfernt werden, und für alle Kanten, die diese Fläche referenzieren, ist oder null zu setzen.

Die orientierte Fläche eines Polygons kann z.B. dadurch berechnet werden, daß von einer Polygonkante beginnend ein Vektor vom Koordinatenursprung zum Kantenanfangspunkt definiert und dann das äußere Produkt von dem Vektor und Kantenvektor gebildet wird. Die restlichen Kanten des Polygons werden nach dem gleichem Schema behandelt, und das Vorzeichen der Summe aller äußeren Produkte bestimmt die Orientierung des Polygons.

Da der Anwender nicht unnötig eingeschränkt werden soll, ist es auch erlaubt, Geometrien zu spezifizieren, die mehrfach zusammenhängend sind.

Abgesehen davon, daß der zweidimensionale Gittergenerator TRIGEN mehrfach zusammenhängende Gebiete nicht vergittern kann, ist diese Tatsache auch beim Flächenaufbau zu berücksichtigen, da im Gegensatz zu einfach zusammenhängenden Strukturen mehrere Flächen entstehen können, die negativ orientiert sind. Es sind daher alle Polygone aus der Flächenliste zu entfernen, die negative Flächen aufweisen.