Laufzeitbetrachtungen

 

Da die vorgestellten drei Algorithmen zur Bestimmung topologischer 3D-Beziehungen zwischen Flächen und Volumina konzeptionell die gleiche Struktur aufweisen, können deren Laufzeiten zusammen untersucht werden.

Bei einer naiven Umsetzung der geschilderten Methode einer Betrachtung der topologischen Beziehungen der enthaltenen Simplexe, kann von einem Aufwand ausgegangen werden, der in der Größenordnung liegt, wobei n und m die Anzahl der Simplexe in den beiden simplizialen Komplexen darstellt. Da diese jeweils alle zueinander in Beziehung gesetzt werden müssen, sind Berechnungsschritte hierfür notwendig. Wie man an den Algorithmen 1, 3 und 5 sieht, haben die Funktionen zur Ermittlung der topologischen Lagen unter den Primitiven eine konstante Zeitkomplexität, so daß die Schranke von eingehalten werden kann.

Kritisch ist jetzt nur noch der Schritt des Zusammenfügens der gewonnenen Einzelergebnisse. Kann dies in konstanter Zeit bewältigt werden, haben wir eine Zeitkomlexität von für diejenigen Varianten der topRel-Algorithmen, welche nacheinander alle Paare von Simplexen untersuchen.

In diesem Zusammenhang ist die Beobachtung wichtig, daß die Kombinationen der Einzelresultate immer lokal bestimmt werden können. Es ist zwar nicht immer eine einfache Verknüpfung der jeweiligen topologischen Beziehungen möglich, aber auch in den Sonderfällen reicht es aus, maximal alle Nachbarn der beiden aktuellen Simplexe (also jeweils 3-4) aber keineswegs ganze Teilbereiche der Objekte zu betrachten. Ob beispielsweise eine topologische Beziehung zwischen zwei Simplexen auch auf dem Rand der betreffenden Objekte gilt, kann über die Nachbarschaftszeiger der Simplexe getestet werden und ob es zu dieser Beziehung eine bestimmte ``Nachbarbeziehung`` gibt, ist ebenso lokal zu entscheiden.

Wie man sieht, ist die worst-case-Laufzeit einer solchen Implementierung . Schnellere Antwortzeiten (im average-case) sind nur bei overlap bzw. cross (im Fläche/Volumen-Fall) zu erwarten, da diese Beziehungen unmittelbar vermeldet werden können, wenn die entsprechende topologische Beziehung unter den Simplexen festgestellt wurde. Je nachdem, wie früh ein für diese relative räumliche Lage signifikantes Simplexpaar untersucht wird, ist in einem dieser beiden Fälle also eine schnellere Antwortzeit der topologischen Klassifikationsfunktion möglich.

Nun soll die Verbesserung angegeben werden, die im Rahmen dieser Arbeit innerhalb des GEOTOOLKIT realisiert wurde. Eine wichtige Rolle hierbei spielt die Klasse gtRTree, in der die räumliche Zugriffsmethode eines R-Baums (vgl. Abschnitt 4.4.2) bereitgestellt wird.

In den implementierten Methoden werden nicht alle Paare von Simplexen untersucht, sondern nur eines der beiden Netze sequentiell durchlaufen und zum jeweils aktuellen Simplex s diejenigen Simplexe des andern Objektes ermittelt, die in die Bounding-Box von s hineinreichen, denn nur für sie besteht die Möglichkeit einer von disjoint verschiedenen topologischen Beziehung. Die Bounding-Box von s dient also als Argument für eine nicht-strikte R-Baum-Anfrage, d.h. aus dem anderen Netz werden nicht nur die Simplexe ermittelt, die echt in der Bounding-Box liegen, es werden vielmehr auch die Simplexe zurückgeliefert, welche die Bounding-Box schneiden. Die so gefundenen Simplexe des zweiten Netzes können für die Gesamtbeziehung der beiden Objekte von Interesse sein und werden untersucht. Da dieses Vorgehen im allgemeinen allerdings nicht alle Simplexe zurückliefert, sondern nur eine kleine Teilmenge, kann die Laufzeit der Algorithmen erheblich verbessert werden.

Unter schlechten Voraussetzungen ist es zwar immer noch möglich, auf einen quadratischen Algorithmus zu kommen. Dies ist z.B. dann der Fall, wenn die Simplexe des ersten Netzes alle größer sind, als das zweite Netz insgesamt. Bei in der Praxis vorkommenden, sehr großen und vor allem ungefähr gleich modellierten Netzen ist allerdings die Annahme viel realistischer, daß eine R-Baum-Anfrage eine konstante Anzahl von Simplexe liefert. Damit kommen wir auf eine Zeitkomplexität von , wobei k die Zeit für die R-Baum-Zugriffe darstellt. Für einen R-Baum mit m Blättern zu einem Netz mit m Simplexen kommen wir hierbei auf eine Abschätzung von und somit im allgemeinen auf eine Gesamtlaufzeit von für die topRel-Algorithmen.