Inhaltsverzeichnis
4.1. Das Problem der überschneidungsfreien Darstellung
Inhaltsverzeichnis
4.1. Das Problem der überschneidungsfreien Darstellung
Die Aussage von Kuratowski ist beim Finden einer möglichst überschneidungsarmen Darstellung leider wenig hilfreich, da sie im Falle des Fehlens von Kuratowski-Teilgrafen nur darüber informiert, dass eine überschneidungsfreie Darstellung existiert - nicht jedoch, wie diese aussieht. Zunächst ist also ein Verfahren zum Minimieren der Überschneidungen gesucht.
Im Gegensatz zu vielen anderen Arbeiten werden hier als zentrales Element nicht die Schleifen der Struktur betrachtet, sondern die geometrischen Koordinaten der einzelnen Elemente. Der Algorithmus wird zum Finden einer geeigneten Darstellung ein Trial-And-Error Schema verwenden. Die einzelnen Teile der Struktur werden dabei in einer bestimmten Anordnung zufällig permutiert und anschließend schrittweise über bestimmte Wege möglichst ohne Überschneidung miteinander verbunden. Sind in einem Schritt alle vorgesehenen Wege zwischen den zu verbindenden Teilen durch bereits vorhandene Verbindungen blockiert, muss eine Überschneidung veranlasst werden. Die Überschneidungen werden dabei mitgezählt. Diese Prozedur wird einige Male mit einer jeweils anderen Permutation wiederholt; danach wird die Variante mit den wenigsten Überschneidungen als Ergebnis verwendet. Bei Nichtgefallen der Darstellung besteht zusätzlich die Möglichkeit, dass der Anwender einen erneuten Durchlauf mit diesmal anderen Permutationen veranlassen kann.
Dieses allgemeine Schema muss nun konkretisiert werden:
Bei Punkt 1 sind prinzipiell zwei Vorgehensweisen möglich: Entweder werden Glieder angeordnet und schrittweise durch die Gelenke miteinander verbunden, oder Gelenke werden angeordnet und schrittweise durch Glieder verbunden. Ein Unterschied zwischen diesen beiden Methoden entsteht daraus, dass bei zwangläufigen Strukturen die Anzahl der Gelenke stets knapp 50% höher ist als die der Glieder. Werden die Glieder angeordnet und verbunden, existieren also weniger Anordnungsmöglichkeiten; dafür sind mehr Verbindungen zu finden. Aber die geringere Anzahl von fest angeordneten Punkten ist gleichzeitig auch der größte Vorteil dieser Variante. Denn dadurch bleiben in späteren Stufen des Darstellungsalgorithmus mehr Freiheiten, die grafische Ausgabe der von manuell angelegten Schemata gewohnten, übersichtlichen Form anzunähern. Bei der zweiten Variante stehen an dieser Stelle schon die Positionen aller Gelenke fest, was an der endgültigen Form der Anzeige kaum noch Optimierungen zulässt. Der hier entwickelte Algorithmus wird deshalb die Glieder zufällig anordnen, nicht die Gelenke.
Die nächste Entscheidung betrifft Punkt 2, also die Art der ebenen Anordnung der Glieder. Hier gibt es eine ganze Reihe von Möglichkeiten. Vorstellbar wären z.B. Anordnungen in einer Linie, auf den Punkten eines quadratischen Gitters, in einem Ring oder in mehreren, konzentrischen Ringen. Letztere Variante etwa wird in [5] gewählt, wenn auch mit einem anderen Algorithmus.
|
Bild 2:
Beispiele für mögliche Anordnungen der Glieder |
Die Wahl der Anordnung hat aber eigentlich nur indirekten Einfluss auf die Eigenschaften des Algorithmus. Überschneidungsfreie Verbindungsmöglichkeiten, die in einer der Anordnungen existieren, existieren auch in jeder anderen - und das sogar in jeder Permutation. Entscheidend ist vielmehr, welche Verbindungswege durch den Algorithmus untersucht werden (Punkt 3).
Um dabei eine geeignete Wahl treffen zu können, ist zunächst eine grundsätzliche Entscheidung zu fällen. Im Hinblick auf das angestrebte Trial-And-Error Schema lassen sich nämlich zwei prinzipiell verschiedene Strategien verfolgen: Intelligenz oder Brute-Force. Das heißt, einerseits könnte versucht werden, einen möglichst intelligenten Algorithmus aufzustellen, der im Durchschnitt der zufälligen Permutationen mit einer relativ geringen Anzahl von Überschneidungen auskommt, z.B. indem er die Verbindungen nach einer vorausschauenden Heuristik anlegt oder besonders viele verschiedene Wege in Betracht zieht. Die alternative Strategie würde dagegen versuchen, den Algorithmus möglichst einfach und schnell zu halten, um innerhalb der zur Verfügung stehenden Zeitspanne möglichst viele Permutationen untersuchen zu können und so die Wahrscheinlichkeit zu erhöhen, dabei eine besonders günstige mit zu erwischen.
Darüber, welche der beiden Strategien letztendlich die besseren Resultate hervorbringt, kann an dieser Stelle keine Aussage getroffen werden. Die Entscheidung fällt daher auf die Brute-Force Strategie, denn dabei ist mit einem wesentlich geringeren Aufwand für Entwicklung und Implementierung zu rechnen. Die Anordnung der Glieder und ihrer Verbindungen sollte für diese Strategie so gewählt werden, dass ein möglichst unkompliziertes, schnelles Anlegen der durch die Gelenke gegebenen Verbindungen ermöglicht wird. Unter den oben vorgeschlagenen Möglichkeiten bietet sich deshalb besonders die lineare Anordnung an, wenn für die Verbindung zweier Glieder nur die beiden einfachsten Möglichkeiten untersuchen werden: Die Glieder werden entweder vollständig oberhalb oder vollständig unterhalb der dazwischen liegenden Glieder verbunden.
|
Beispiel 2:
Zur Darstellung dieses Mechanismus werde die lineare Anordnung 5-3-4-7-6-2-8 untersucht. Eine überschneidungsfreie Verbindungsvariante für diese Anordnung, die nur die genannten, einfachen Wege verwendet, sieht z.B. so aus:
|
Der Algorithmus muss also die in einer Linie zufällig angeordneten Glieder Schritt für Schritt verbinden, wie es durch die in der Gliedmatrix verzeichneten Gelenke vorgegeben ist. Dabei können an manchen Stellen mehrere Verbindungen in der gleichen Hälfte (obere oder untere) parallel verlaufen, ohne dass daraus eine Überschneidung entsteht.
Es wird nun ein einzelner Schritt des Algorithmus betrachtet. Es sollen die beiden Glieder verbunden werden, die sich laut Permutation an den Positionen A und B (A<B) befinden, wobei die Positionen von links nach rechts durchnummeriert sind. Wichtig ist, dass der Algorithmus nur diejenigen Verbindungen zwischen A und B als blockiert betrachtet, die tatsächlich mit bereits angelegten Verbindungen zu Überschneidungen führen würden. Bestehende Wege blockieren die Verbindung zwischen A und B genau in folgenden Fällen nicht:
Werden die Verbindungen in einer geschickten Reihenfolge angelegt, müssen nicht alle diese Fälle betrachtet werden. Wird z.B. die Reihenfolge so gewählt, dass der Abstand zwischen A und B von Schritt zu Schritt niemals kleiner wird, so kann der vorletzte Fall gar nicht eintreten. Bei dieser Vorgehensweise würden also neue Verbindungen in jedem Falle über bestehende hinweg geführt. Sobald bereits eine Verbindung über A oder B hinweg führt, ist der Weg in dieser Hälfte blockiert. Der Algorithmus gestaltet sich dann besonders einfach, denn statt jede neue Verbindung mit allen bestehenden auf Überschneidungen zu prüfen, muss nur für jede Position und jeweils beide Hälften ein Schalter verwaltet werden, der aussagt, ob schon Verbindungen darüber hinweg führen.
Unter Verwendung dieser Vereinfachung sieht der Kern des Algorithmus so aus:
keine Positionen oben blockiert
keine Positionen unten blockiert
für alle Abstände d, aufsteigend von 1 bis n-1
für alle Gelenke, die Positionen A und B mit B-A = d verbinden
falls
d = 1
dann
A und B gerade verbinden
sonst falls
A und B nicht oben blockiert
dann
A und B oben verbinden
für alle Positionen X mit A<X<B
X oben blockiert
sonst falls
A und B nicht unten blockiert
dann
A und B unten verbinden
für alle Positionen X mit A<X<B
X unten blockiert
sonst
A und B oben verbinden
für alle Positionen X mit A<X<B
X oben blockiert
Überschneidung zählen
|
|
Beispiel 3:
|
Das Gestell von Mechanismen bedarf einer Sonderbehandlung, da es nicht wie die anderen Glieder dargestellt werden soll, sondern als Rahmen um den Mechanismus herum. Es bekommt deshalb keine Position zugeteilt und wird vom Kernalgorithmus erst nach allen anderen Verbindungen berücksichtigt. Eine Verbindung zwischen einer Position und dem Gestell ist gerade dann überschneidungsfrei möglich, wenn diese Position in wenigstens einer der beiden Hälften noch nicht blockiert ist.
Der Algorithmus arbeitet weder vorausschauend, noch revidiert er eine einmal getroffene Entscheidung. Sind in einem Schritt sowohl obere als auch untere Verbindung möglich, wird grundsätzlich die obere gewählt. Diese Entscheidung kann unter Umständen falsch sein, d.h. am Ende zwangsläufig zu einer überschneidungsreicheren Darstellung führen, als das mit einer unteren Verbindung an dieser Stelle der Fall wäre.
|
Beispiel 4:
Bei der Permutation 2-10-9-4-3-8-5-7-6 muss der Algorithmus im letzten Schritt - der Verbindung zwischen den Gliedern 4 und 7 - eine Überschneidung veranlassen:
Grund dafür ist, dass die Verbindung zwischen den Gliedern 5 und 6 ungünstiger Weise über die obere Hälfte hergestellt wurde. Mit einer unteren Verbindung zwischen 5 und 6 würde eine überschneidungsfreie Darstellung gefunden:
|
In einem solchen Fall muss darauf gehofft werden, dass der Algorithmus eine so günstige Darstellung wie die, die er durch die falsche Entscheidung verpasst hat, bei einer anderen Permutation finden kann. Eine theoretische Verbesserung besteht darin, die Entscheidungen zufällig zu treffen. Das erhöht die Wahrscheinlichkeit, bei der mehrmaligen Untersuchung derselben Permutation wenigstens einmal die richtigen Entscheidungen zu treffen. Allerdings ist die Anzahl der Permutationen gerade bei den kritischen vielgliedrigen Strukturen derart hoch, dass kaum jemals zwei der zufällig gewählten Permutationen gleich sein dürften.
Es ist also nicht sicher gestellt, dass das entwickelte Verfahren für alle Strukturen, die sich mit einer linearen Anordnung der Glieder und den betrachteten Verbindungswegen ohne Überschneidung darstellen lassen, auch eine überschneidungsfreie Darstellung findet. Damit ist erst recht fraglich, ob der Algorithmus das Maximalziel erreicht, für alle Strukturen, die sich auf beliebige Art ohne Überschneidung in der Ebene darstellen lassen, eine überschneidungsfreie Darstellung zu finden. Dazu sollen hier auch keine weiteren Untersuchungen erfolgen. Eine grobe Einschätzung des Verfahrens wird nach der Implementierung anhand von Tests möglich sein.
Wird für eine Struktur keine überschneidungsfreie Darstellung gefunden, wird die Variante mit den wenigsten Überschneidungen zur Anzeige gebracht. Überschneidende Glieder werden angezeigt, als würden sie in einer zweiten Ebene über dem Rest der Struktur liegen. Dabei macht sich allerdings die Entscheidung negativ bemerkbar, Glieder durch Gelenke zu verbinden statt umgekehrt. Durch den Algorithmus veranlasste Überschneidungen sind keine Glieder, sondern Gelenke. Überschneidende Glieder gibt es eigentlich nicht; sie können allenfalls dadurch definiert werden, dass sie "überschneidende Gelenke" enthalten. Das muss aber nicht in jedem Fall funktionieren.
Mehr als der oben abgebildete Kernalgorithmus ist zum Suchen der optimalen Darstellung nicht erforderlich. Nachfolgende Schritte können durchgeführt werden, nachdem die endgültige Anordnung gewählt wurde. Der Kernalgorithmus bleibt dadurch schnell und kann so in der verfügbaren Zeitspanne eine maximale Anzahl von Anordnungen testen.
Der erste dieser nachfolgenden Schritte ist die Positionierung der Gelenke. Für die horizontale Position eines Gelenks wird der Einfachheit halber die Mitte der jeweiligen Verbindung gewählt, für die vertikale die Höhe dieser Verbindung. Eine Gelenk muss dann höher (obere Hälfte) bzw. tiefer (untere Hälfte) liegen als das höchste bzw. tiefste Gelenk, über das seine Verbindung hinweg führt.
Aus der Anordnung von Gliedern und Gelenken muss zuletzt noch eine angenehme, übersichtliche Grafik erzeugt werden. Das bedeutet vor allem, dass überflüssige Teile von Gliedern nicht mit angezeigt werden. Bei Gliedern mit wenigen Gelenken - besonders zweigelenkigen - führt das sogar oft dazu, dass sie in der Grafik an einer etwas anderen Stelle erscheinen, als das durch die verwendete Permutation festgelegt ist.
|
Beispiel 5:
Die blauen Bereiche zeigen Gliederteile an, die bei der Anzeige weggelassen werden. |
