Berner Fachhochschule
Bachelor of Science in Computer Science
Informatik Seminar
| Student: | Sebastian Häni, haeni.sebastian@gmail.com |
| Betreuer: | Peter Schwab, peter.schwab@bfh.ch |
| Version: | 1.0.1, 29.05.2017 |
Diese Arbeit wurde als Teil des Informatik Seminar Moduls an der Berner Fachhochschule BFH geschrieben. Der Source Code ist verfügbar online unter https://github.com/sebastianhaeni/space-partitioning. Die Dokumentation und die dazugehörigen Slides sind online verfügbar unter https://sebastianhaeni.github.io/space-partitioning.
Alle Quellen sind nummeriert [n] und im Quellenverzeichnis im Appendix aufgelistet. Grundwissen in Informatik und insbesondere in Algorithmen und Datenstrukturen werden zum Verständnis dieser Arbeit vorausgesetzt. Die wichtigsten Abkürzungen und Konzepte sind im Glossar, der ebenfalls im Appendix gefunden werden kann, erklärt.
Dieses Dokument wurde in HTML geschrieben und mit Prince zu einer PDF Datei konvertiert. Die verwendete Schriftart ist Open Sans, entworfen von Steve Matteson im Auftrag von Google.
YesLogic Pty. Ltd.: Prince http://www.princexml.com 20. März 2017
In der Geometrie ist "Space Partitioning" der Prozess der Unterteilung eines Raums in zwei oder mehrere disjunkte Partitionen. Jeder Punkt im Raum kann einer Partition zugeordnet werden.
R-Tree, Kd Tree, Interval Tree, usw. sind Datenstrukturen welche in vielen grafischen Anwendungen oder GIS Applikationen (Geographical Information System) verwendet werden und z.B. die Nachbarschafts- und Bereichsuche erleichtern.
Im folgenden Dokument werden drei Bereiche des Space Partitioning vorgestellt. Unter Binäre Raumteilung wird erläutert wie computerbasierte Zeichensystem eine 3D Welt zeichnen können. Die orthogonale Bereichsuche beschäftigt sich mit Suchen in Räumen. Und bei Windowing handelt sich um die Einschränkung des Raumes auf ein Fenster.
Dieses Dokument basiert auf Wissen aus dem Buch Computional Geometry - Algorithms and Applications, 3rd Edition geschrieben von Mark de Berg, Otfried Cheong, Marc van Kreveld und Mark Overmars.
Computational Geometry - Algorithms and Applications, 3rd Edition Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
Raumunterteilung, oder in Englisch Space Partitioning, heisst in der Geometrie einen Raum in sich nicht überschneidende Teilräume zu unterteilen. Jeder Punkt im Raum kann einem einzigen Teilraum zugeordnet werden.
Um einen Raum weiter und weiter zu unterteilen bietet sich eine Baumstruktur an. Ein Raum kann rekursiv in weitere Teilräume unterteilt werden aus welchen sich die Nodes des Baums ergeben.
Die meisten Raumunterteilungssysteme benutzen Ebenen um den Raum zu unterteilen. In höher dimensionalen Räumen kommen Hyperplanes zum Einsatz. In der Regel werden gewisse Punkte im Raum verwendet um die Eckpunkte der Ebenen zu bestimmen und die Punkte dazwischen werden einer Ebene zugeordnet. Ein Beispiel eines rekursiv erstellten Baums, der Ebenen benutzt, ist ein BSP Tree.
Space Partitioning ist kein abgeschlossenes Gebiet welches klare Grenzen hat. Es hat vielseitige Anwendungsmöglichkeiten und kann fast überall angetroffen werden. Deshalb habe ich drei wichtige Themengebiete und die dazugehörigen Datenstrukturen herausgesucht und im folgenden Dokument erklärt. Die erwähnten Datenstrukturen bilden die Basis für weitere spezifischere Konstrukte.
Raumunterteilung ist ein hilfreiches Werkzeug um in Computerspielen oder sonstigen Computersimulationen mit einer 2D oder 3D Grafik Collision Detection zu realisieren. Um zu detektieren welche Einheiten gerade in der Nähe des Hauptgebäudes sind kann man entweder naiv mit Brute Force durch die Liste aller Einheiten im Spiel iterieren oder man verwendet einen raumunterteilenden Baum um die Einheiten schnell mit einer Komplexität von O(log N) zu finden.
Um eine gewisse Anzahl an nächstgelegenen Nachbaren zu finden wird ein k-nearest neighbor (k-NN) Algorithmus verwendet. Ein k-NN Algorithmus klassifiziert Datenpunkte in einer Menge zu Gruppen.
Seit 1970 wurde die Branch and Bound Methode verwendet um das Problem zu lösen. Branch and Bound wird für Natürliche-Zahlen-Optimierungsprobleme angewendet. Also für Probleme in welchen die Variablen natürliche Zahlen sind. Häufig, aber nicht immer, sind die Variablen 1 oder 0. Ein Beispiel dafür wäre das Knapsack Problem auf welches ich jetzt nicht weiter eingehe.
Mehrere raumunterteilende Methoden wurden entwickelt um die Nearest Neighbor Suche zu lösen, eine davon, wahrscheinlich die einfachste, heisst Kd Tree. Der Kd Tree unterteilt den Suchraum iterativ in zwei Unterräume die je die Hälfte der Punkte enthalten. Dieser ist jedoch nicht sehr geeignet, wenn sich der Suchraum dynamisch verändert. Deshalb wurde der R-Tree entwickelt, welcher effiziente Algorithmen für das Einfügen und Löschen von Punkten hat.
In Ray Tracing Applikationen werden Strahlen durch jeden anzuzeigenden Pixel geschossen um zu berechnen welche Farbe es hat. Das ist offensichtlich ohne weitere Optimierungen kaum in Echtzeit lösbar. Verbesserungen der Performance können durch die Wahl von optimalen Kollisionsgeometrien, moderne Implementationen von Schnittpunktalgorithmen mit Object Bounding und Volumen sowie durch parallele Berechnung gewonnen werden. Ein grosser Gewinn an Performance erhält man durch die Benutzung einer raumunterteilenden Datenstruktur. Die einfachste Möglichkeit ist ein uniformes Raster. Dies ist einfach zu implementieren und hat fast keinen Verwaltungsaufwand. Mit Kd Trees oder Octrees kann aber noch mehr herausgeholt werden.
In 3D Anwendungen gibt es häufig eine grosse Menge an Geometrien, die gezeichnet werden müssen, um die Szene darzustellen. Damit nicht immer alles gezeichnet werden muss, kann Portal Culling zur Anwendung gebracht werden. Simpel gesagt werden nur die Welt-Sektionen gezeichnet die durch ein Portal sichtbar sind. Das ist relativ einfach vorstellbar bei Ur-Klassikern wie Doom oder Wolfenstein 3D. Nur was durch ein Portal sichtbar ist muss auch gezeichnet werden. Um das zu berechnen werden raumunterteilende Datenstrukturen verwendet. Portal Culling wird auch in den modernsten Game Engines angewendet wie z.B. der CRYENGINE.
Raumunterteilende Algorithmen und Datenstrukturen werden nicht ausschliesslich für Computeranwendungen gebraucht. Auch Designer von Leiterplatten verwenden raumunterteilende Methoden um sicherzustellen, dass die entworfene Platte auch herstellbar ist. Diese Überprüfung stellt fest ob unter Berücksichtigung der Leiterbreite und die nötigen Abstände dazwischen eingehalten wurden. Ein modernes Design kann Milliarden von Polygonen haben die Kabel und Transistoren repräsentieren.
Wikipedia: k-nearest neighbors algorithm https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm 12. Mai 2017
CRYENGINE: Culling Explained http://docs.cryengine.com/display/SDKDOC4/Culling+Explained 6. Mai 2017
Panda3D - Portal Culling https://www.panda3d.org/manual/index.php/Portal_Culling 12. Mai 2017
Heutzutage werden Piloten nicht mehr in einem echten Flugzeug ausgebildet. Die Ausbildung findet in Flugsimulatoren auf dem Boden statt. Das spart kosten. Ein Flugsimulator ist eine 3D Anwendung mit Echtzeit-Rendering. Ein Pilot muss auf dem Bildschirm ein realistisches Abbild der Realität sehen können wie er es in einem echten Flugzeug auch antreffen wird. Dazu müssen Objekte wie Landebahn, Flughafengebäude oder Wolken auf den Bildschirm gezeichnet werden. Damit die näheren Objekte vor den weiter entfernten Objekten gezeichnet werden, muss allerdings die Reihenfolge berücksichtigt werden. Wir müssen nicht sichtbare Flächen verschwinden lassen. Man nennt dies in Englisch Hidden Surface Removal.
Einer der ersten Algorithmen zur Lösung dieses Problems war Painter's Algorithmus. Er heisst so weil er ungefähr so funktioniert wie ein Maler eine Zeichnung macht. Nebenbei gibt es auch den z-Buffer Algorithmus. Dieser ist der am häufigsten verwendete Algorithmus zu Hidden Surface Removal. Er hat aber den Nachteil, dass er viel Speicher und einen extra Test auf der Z-Koordinate benötigt.
Painter's Algorithmus sortiert die zu zeichnenden Objekte der Reihenfolge nach wie sie von der Kamera zu sehen sind. Dann zeichnet er eine Fläche nach der anderen. Bereits gezeichnete Flächen die überdeckt werden müssen, werden einfach überzeichnet. Dadurch müssen wir kaum Speicher zur Verfügung haben und sehr wenig testen solange wir die Flächen sortiert haben. Painter's Algorithmus hat jedoch ein grosses Problem mit zyklisch überdeckenden Polygonen.
Um solche Abbilder auf den Bildschirm zu bringen müssen wir den Algorithmus erweitern. Irgendeine der Flächen im oberen Beispiel muss unterteilt werden in ein Dreieck und ein Viereck. Danach können wir die Flächen neu sortieren und erfolgreich korrekt zeichnen. Dies kostet nun aber einiges an Rechenaufwand welchen wir gerne nicht mehrmals machen. Dazu können wir das in einer passenden Datenstruktur abspeichern. Das ist der binäre raumunterteilende Baum oder auch BSP Tree genannt.
Eine raumunterteilende Grafik mit Polygonen und dem dazugehörigen BSP Tree ist unten dargestellt. Um den Raum zu unterteilen schneiden wir die Ebene zuerst mit ℓ1, daraus ergeben sich zwei neue Halbebenen. Die Halbebene über ℓ1 schneiden wir mit ℓ2 und die Halbebene unter ℓ1 mit ℓ3 und so weiter. Die Schnitte unterteilen nicht nur die Ebene, sie können auch die Objekte darin in Fragmente unterteilen. Dieser Vorgang wird solange weitergeführt bis in jeder Region nur noch ein Fragment vorhanden ist.
Diese Unterteilung wird als Binärbaum modelliert. Jedes Blatt vom Baum korrespondiert zu einem Fragment der finalen Unterteilung. Jeder interne Knoten des Baums korrespondiert zu einer Schneidegeraden.
Den erzeugten Baum können wir nun verwenden um Painter's Algorithmus korrekt umzusetzen. Die Effizienz des Algorithmus ist aber stark abhängig von der Grösse des BSP Trees. Je kleiner, desto effizienter. Also müssen wir einen geeigneten Schneidealgorithmus finden, der möglichst wenig Polygone durchschneidet und so einen kleinen Baum erzeugt. Um den Schneidealgorithmus zu unterstützen können wir im Szenenaufbau einige Tricks anwenden die den Baum kleiner lassen werden. So können zum Beispiel keine gekurvten Objekte verwendet werden, sondern Polyeder die in Dreiecke aufteilbar sind.
Der Algorithmus zur Konstruktion eines BSP Trees ist einfach und ist auf faqs.org sehr gut beschrieben:
Die Wahl der Teilebene ist abhängig vom Anwendungsfall und welche Effizienzkriterien wir für die Konstruktion haben. Für einige Anwendungen kann es sinnvoll sein die Teilebene von der Liste der Polygone abzuleiten, für andere macht es mehr Sinn, wenn die Teilebene senkrecht an den Achsen ausgerichtet ist.
Ein gutes Ziel ist ein balancierter Baum. Balanciert ist ein Baum, wenn jedes Blatt ungefähr dieselbe Menge an Polygonen hat. Das ist aber nur mit hohem Rechenaufwand erreichbar. Eine schlechte Wahl der Teilebene kann viele Teilfragmente zur Folge haben und dadurch viele Polygone an den Blättern erzeugen. Normalerweise macht man ein Trade Off zwischen Balance und Anzahl Teilungen.
Die Unterteilung von Polygonen in Fragmente ist die Klassifikation jedes Polygon-Objektes der Menge in Abhängigkeit der Teilebene. Ist ein Polygon zur einen oder anderen Seite der Trennlinie, wird es nicht modifiziert und wird zur Teilmenge der Seite zu der es gehört zugeordnet. Überschneiden sich Trennlinie und Polygon wird es in zwei oder mehr Fragmente zerteilt. Die resultierenden Fragmente werden den beiden Seiten zugeordnet.
Wann genau aufgehört wird den Baum zu berechnen ist wiederum anwendungsbedingt. Ein mögliches Kriterium kann eine maximale Fragment Anzahl bei einem Blatt sein. Ein idealer BSP Baum hätte das Maximum von 1. Oder man fährt solange fort bis jedes Polygon in einem internen Blatt vorhanden ist. Oder man limitiert die Baumtiefe.
Die folgenden Code Listings zeigen die Struktur der BspTree Klasse und der Algorithmus zur Konstruktion des Baumes.
class BspTree {
Plane partition;
List<Polygon> polygons = new ArrayList<>();
BspTree front;
BspTree back;
}
void buildBspTree(BspTree tree, List<Polygon> polygons) {
Polygon root = polygons.get(0);
tree.setPartition(root.getPlane());
tree.getPolygons().add(root);
List<Polygon> frontlist = new ArrayList<>();
List<Polygon> backlist = new ArrayList<>();
polygons.forEach(polygon -> {
PositionClassification result = tree.getPartition().classify(polygon);
switch(result) {
case COINCIDENT:
tree.getPolygons().add(polygon);
break;
case IN_BACK_OF:
backlist.add(polygon);
break;
case IN_FRONT_OF:
frontlist.add(polygon);
break;
case SPANNING:
Pair<Polygon, Polygon> split = splitPolygon(polygon, tree.getPartition());
backlist.add(split.getLeft());
frontlist.add(split.getRight());
break;
}
});
if(!frontlist.isEmpty()) {
tree.setFront(new BspTree());
buildBspTree(tree.getFront(), frontlist);
}
if(!backlist.isEmpty()) {
tree.setBack(new BspTree());
buildBspTree(tree.getBack(), backlist);
}
}
Diese Implementation nimmt an, dass alle Polygone konvex sind. Konvex heisst, von jedem Punkt des Polygons kann ohne Verlassen des Polygons ein beliebiger anderer Punkt erreicht werden. Auch kann die Implementation verbessert werden in dem die Teilebene (Partition) intelligenter ausgewählt wird.
Der Algorithmus um eine Szene zu zeichnen vom Standpunkt v sieht so aus:
View v = ...;
void render(BspTree tree) {
if(tree.getFront() == null && tree.getBack() == null) {
// the current node is a leaf
renderPolygons(tree.getPolygons());
return;
}
PositionClassification result = tree.getPartition().classify(v);
switch(result) {
case IN_BACK_OF:
renderPolygons(tree.getFront().getPolygons());
renderPolygons(tree.getPolygons());
renderPolygons(tree.getBack().getPolygons());
break;
case IN_FRONT_OF:
renderPolygons(tree.getBack().getPolygons());
renderPolygons(tree.getPolygons());
renderPolygons(tree.getFront().getPolygons());
break;
case COINCIDENT:
renderPolygons(tree.getFront().getPolygons());
renderPolygons(tree.getBack().getPolygons());
break;
}
Ein BSP Baum zu berechnen kostet viel CPU Zeit. Deshalb will man das nicht für jedes Frame machen. BSP Trees verwendet man in der Regel nur für statische Geometrien. Eine der ersten Anwendung in der BSP Trees angewendet wurde war das Spiel Doom. Darin wird der BSP Baum beim Laden des Levels berechnet was einige Zeit dauern kann, wenn es ein grosses Level ist. Dynamische Objekte werden dann in Kombination eines Z-Buffers gezeichnet.
Fazit ist, Einfügen und Löschen von Objekten in einem BSP Tree haben die selbe Zeitkomplexität wie die Neuberechnung des Baumes von O(n3). Das macht den BSP Baum ungeeignet für dynamische Szenen.
faqs.org: Erklärung der BSP Tree Konstruktion http://www.faqs.org/faqs/graphics/bsptree-faq 7. Mai 2017
Doom Engine verwendet BSP Trees https://en.wikipedia.org/wiki/Doom_engine 7. Mai 2017
Wenn man über Datenbanken denkt, ist meist nicht das erste was aufkommt Geometrie. Jedoch kann man die Abfrage einer Datenbank gut mit einem Geometrie Problem vergleichen. Wir nehmen an wir haben eine Tabelle Employee mit folgendem Schema:
| Employee | |||
|---|---|---|---|
| Name | Birthday | Salary | Kids |
Nun wollen wir alle Employees mit einem Salär zwischen 3'000 CHF und 4'000 CHF abfragen. Das heisst wir müssen in einem eindimensionalem Raum alle Werte zwischen zwei Variablen finden. Das ist ein bekanntes Problem und kann mit einem balancierten Binärsuchbaum effizient gelöst werden. Doch was passiert, wenn wir unsere Abfrage weiter einschränken. Wir wollen zudem nur die Employees die zwischen 1950 und 1955 geboren wurden. Dann wird daraus ein Planarproblem.
Fügen wir nun noch eine weitere Anforderung dazu, dass nur Employees mit 2 bis 4 Kindern gefunden werden sollen, können wir das Problem in 3D beschreiben.
Das heisst, jede weitere Bedingung erzeugt eine weitere Dimension in der Abfrage. Wir nennen dieses Prinzip orthogonale Bereichsuche.
Wie erwähnt kann die eindimensionale Bereichsuche mit einem balancierten Binärbaum gelöst werden. Beschäftigen wir uns nun mit 2 Dimensionen. Man könnte sagen die Bereichssuche in 2D kann aufgeteilt werden in zwei Bereichssuchen in 1D, eine für die x-Koordinate und eine für die y-Koordinate. Wie bringen wir nun zwei Bäume zu einem?
Das ist möglich in dem wir abwechselnd an der x-Koordinate und y-Koordinate aufteilen. Bei der Baumwurzel teilen wir an der x-Koordinate, auf der 2. Stufe an der y-Koordinate, auf der 3. Stufe wieder an der x-Koordinate und so weiter.
Ein solches Konstrukt nennt man ein Kd Tree. Das ist ein k-dimensionaler Baum der eine spezielle Ausprägung des BSP Trees ist. Ursprünglich hiess es 2d Tree. Doch heute ist im Sprachgebrauch ein zweidimensionaler Kd Tree gebräuchlich.
Die Konstruktion des Kd Tree wird anhand des folgenden Algorithmus zu erklärt.
class Node {
Split split;
Point point;
Node above;
Node below;
}
class Split {
boolean even;
float coordinate;
}
Node buildKdTree(List<Point> points, int depth) {
if(points.size() == 0) {
return null;
}
if(points.size() == 1) {
return new Node(points.get(0));
}
boolean even = depth % 2 == 0;
{split, pointsAbove, pointsBelow} = split(points, even);
Node nodeAbove = buildKdTree(pointsAbove, depth + 1);
Node nodeBelow = buildKdTree(pointsBelow, depth + 1);
return new Node(split, nodeAbove, noveBelow);
}
Wie man erkennt ist es ein rekursiver Algorithmus der mit allen Punkten startet und die Punktewolke weiter und weiter
in Regionen unterteilt. Der so konstruierte Baum ist automatisch ausbalanciert. Dies weil die split-Methode
die Punkte am Median unterteilt. Jedoch wird aus Performancegründen nicht der wahre Median berechnet. Ist die Menge
der Punkte ungerade, ist die Berechnung trivial, man nimmt den mittleren Punkt auf der x- respektive y-Achse. Ist die
Menge der Punkte gerade nimmt man entweder den Punkt aus der unteren oder oberen Mitte.
Wie beim BSP Tree besprochen muss die Berechnung des Kd Tree nicht alle Punkte aufteilen. Sondern man fährt so lange fort wie es Sinn macht. Restliche Punkte kann man den bestehenden Nodes als Liste anhängen. Dazu müsste im obigen Pseudo Code die Node Klasse so geschrieben sein, dass sie eine Liste von Punkten enthalten kann. Um also einen Punkt hinzuzufügen traversiert man den Baum und hängt bei der letzten angetroffenen Node den Punkt an. Alternativ kann man den Kd Tree auch weiterführen.
Werden Punkte dynamisch hinzugefügt und der Kd Tree weitergeführt, ist es wahrscheinlich, dass der Baum nicht mehr balanciert ist und keine guten Suchzeiten mehr garantieren kann. Ein Neubalancieren des Kd Trees ist nicht einfach, weil die Rotationsmethode nicht angewendet werden kann, weil es beim Kd Tree sich um ein mehrdimensionalen Baum handelt. Es gibt aber Methoden wie man es bewerkstelligen könnte.
Es gibt mehrere Varianten wie Punkte entfernt werden können. Die naivste wäre wohl die Punkte einfach aus den Nodes zu entfernen aber die Nodes so zu lassen wie sie sind. Bleibt die räumliche Verteilung der Punkte in etwa gleich, könnte dass eine schnelle Möglichkeit sein. Anderseits kann man auch den Teilbaum neuberechnen der unter der Node mit dem Punkt ist. Wenn aber ein Punkt entfernt ist der weit oben im Baum ist, muss jeweils viel neuberechnet werden. Eine weitere Möglichkeit ist, für den gelöschten Punkt einen Ersatz in der Nähe zu finden. Das verschiebt den Teilbaum ein wenig und Teile müssen neu berechnet werden, jedoch nicht der ganze.
Bins (Englisch für Eimer) sind eine weitere Möglichkeit Objekte in einem Raum abzufragen. Eine Bin-Datenstruktur unterteilt den Raum in achsenausgerichtete Eimer. Jeder Eimer ist gleich gross.
Zu jedem Bin wird gibt es eine Liste welche Objekte sich darin befinden. Ein Objekt kann in mehreren Bins vorkommen.
Ich kann also zum Beispiel abfragen was sich mit der Region Q schneidet. Diese Abfrage würde im obigen
Beispiel C, D, E und F zurückgeben. Dies sind nur Kandidaten.
Um herauszufinden welche Objekte meine Region Q wirklich schneiden muss ich für jedes Objekt einen Test
durchführen. Hätte ich keine Bins müsste ich sämtliche Objekte durchtesten. Von der Region Q auf die sich
schneidenden Bins zu kommen, ist mit einfachen Bit Operationen möglich.
Wikipedia: Bins https://en.wikipedia.org/wiki/Bin_(computational_geometry) 12. Mai 2017
Heutzutage haben fast alle Personenwagen ein eingebautes Navigationsgerät. Das Navi zeigt dem Fahrer wo er durchfahren muss indem es ihm einen Kartenausschnitt präsentiert. Der Kartenausschnitt ist Teil einer grösseren Karte die ein Land oder sogar einen ganzen Kontinent oder manchmal sogar die ganze Erde enthält. Das Navi muss dann entscheiden welche Objekte es jetzt gerade in diesem Kartenausschnitt darstellen muss. Der Brute Force Ansatz funktioniert nicht, weil dazu Millionen von Objekten geprüft werden müssen, ob diese im Kartenausschnitt sichtbar sind. Was das Navi macht nennt man ein Windowing Query. Es fragt eine Datenstruktur mit einer Boundary ab und erhält die darin enthaltenen Objekte. Windowing Queries sind ähnlich wie orthogonale Bereichssuche, sind aber meist limitiert auf 2 oder 3 Dimensionen.
Um nicht gleich mit 2 oder 3 Dimensionen zu beginnen beschäftigen wir uns zuerst mit einer Dimension. Wir stellen uns vor wir haben ein Zeitstrahl. Auf diesem Zeitstrahl befinden sich verschiedene Intervalle. Als Beispiel können wir die Prüfungen nehmen. Es finden Prüfungen unterschiedlicher Länge zu unterschiedlichen Zeitpunkten statt. Einige Prüfungen überschneiden sich zeitlich.
Würden sich die Intervalle nicht überlappen, könnten wir den einfachen Weg gehen und die Intervalle einfach in einen Binärbaum packen und schon könnten wir sie mit O(log n) Zeit abfragen. Nur sind sie halt überlappend. In einer ersten Überlegung könnte man auf die Idee kommen einfach zwei Bäume zu bauen für die Start- und Endzeit. Beide Bäume können in O(log n) Zeit abgefragt werden. Weil sie aber wieder mit O(n) Zeit zusammengeführt werden müssen, enden wir mit einer Abfragezeit von O(n + log n) = O(n) was nicht besser ist als der Brute Force Ansatz.
Ein Interval Tree kann rekursiv konstruiert werden. In einem Schritt werden als Eingabeparameter die Menge der Intervalle übergeben. Der Algorithmus separiert diese in drei Kategorien. Eine Kategorie sind die Intervalle, die sich links vom Median befinden, eine andere die Intervalle rechts des Median. Und dann gibt es noch die Intervalle die den Median schneiden. Die schneidenden Intervalle werden in einer speziellen Datenstruktur abgelegt. Diese Datenstruktur enthält zwei sortierte Mengen der Intervalle. Es wird einmal nach Start- und einmal nach Enddatum sortiert. Diese Struktur wird der aktuellen Node angehängt. Mit den Intervallen links und rechts wird der Baum nun weitergebaut.
class Interval {
int start;
int end;
}
class Node {
int value;
SortedIntervals mid;
Node left;
Node right;
}
class SortedIntervals {
SortedSet<Interval> startpoints;
SortedSet<Interval> endpoints;
}
Node buildIntervalTree(Set<Interval> intervals) {
Node node = new Node();
if(intervals.isEmpty()) {
return node;
}
int endMedian = calcEndpointMedian(intervals);
{leftIntervals, midIntervals, rightIntervals} = classify(intervals, endMedian);
node.value = endMedian;
node.mid = midIntervals;
node.left = buildIntervalTree(leftIntervals);
node.right = buildIntervalTree(rightIntervals);
return node;
}
Das Einfügen und Entfernen von Intervallen in Interval Trees funktioniert ähnlich mit Rotation wie bei einem normalen balancierten Binärbaum. Nach der Änderung im Baum müssen jedoch die Intervalle neu gesucht werden die die nach oben geschobene Node überlappen. Diese müssen dann dahin geschoben werden. Als Konsequenz kann es sein, dass es eine neue leere Node gibt. Diese kann mit dem selben Algorithmus gelöscht werden.
Einfügen und Entfernen brauchen O(log n) Zeit, wobei n die Anzahl Intervalle vor der Operation ist.
Wikipedia: Interval Tree https://en.wikipedia.org/wiki/Interval_tree 12. Mai 2017
Kommen wir nun zu zwei Dimensionen beziehungsweise zurück zu unserem Navi Problem. Der R-Tree löst das Windowing effizient. Nicht nur die CPU wird geschont, auch ist der R-Tree so aufgebaut, dass Teilbäume in Pages gespeichert werden, die auf einer Festplatte abgelegt werden und schnell wieder gelesen werden können. Nämlich genau das ist beim Navi Beispiel ungemein wichtig, weil die ganze Erde nicht im Speicher gehalten werden kann. Nicht einmal ein Baum davon. Der R-Tree hat sein R von Rectangle. Die Nodes in einem R-Tree, der übrigens vom B-Tree abgeleitet ist, sind Rechtecke. Und wie vom B-Tree bekannt, können Nodes mehr als zwei Children haben.
Die Idee ist dass ein Node-Rechteck sämtliche Children Node-Rechtecke umschliesst. Um ein Punkt, Rechteck bzw. ein MBR (minimum bounding rectangle) einzufügen, geht man wie folgt vor.
Der Baum wird rekursiv, startend beim Root Node, traversiert. An jeder Node werden sämtliche Child-Nodes analysiert und mit einer Heuristik bewertet welche am besten passt. Diese Heuristik bewertet zum Beispiel um wie viel die Child-Node vergrössert werden müsste und wählt den geringsten Vergrösserungsfaktor. Die Suche geht solange weiter bis eine bestehende Blatt-Node erreicht wird. Dort kann eingefügt werden. Ist jedoch die Blatt-Node bereits voll (anhand der gewählten Einschränkungen), muss diese Node aufgeteilt werden. Dies muss wieder mit einer Heuristik geschehen, da ein erschöpfender Algorithmus zu langsam wäre. Die neue Node wird der darüber liegenden Node angehängt. Ist diese jedoch auch schon voll propagiert es weiter nach oben bis zum Root-Node. Passiert das, wird eine neue Root-Node erstellt.
Wikipedia: R-Tree https://en.wikipedia.org/wiki/R-tree 12. Mai 2017
Um die Resultate dieser Arbeit zu erzeugen wurde folgende Software eingesetzt: