Die Visualisierung
Sämtliche Informationen in der OSM-Datei liegen als Streckenzüge, genauer gesagt als angeordnete Folge von mit einander verbundenen Koordinaten, vor. Die Streckenzüge können entweder eine Straße oder ein Weg sein, oder auch der Umriss einer Fläche, z.B. eines Baches, einer Grünanlage oder der Umriss eines Gebäudes. Diese Streckenzüge bilden dabei meist Umrisse von konkaven Polygonen. Da wir das Praktikum in OpenGL realisieren wollten, aber OpenGL keine Zeichenfunktionen für konkave Polygone zur Verfügung stellt, mussten wir Funktionen bereitstellen, welche die konkaven Polygone, die durch die OSM-Datei gegeben waren, in konvexe Teilpolygone zerlegt, sodass diese mit OpenGL fehlerfrei dargestellt werden können. Um dies zu bewerkstelligen, implementierten wir eine Routine, welche das gegebene, konkave Polyon, in monotone Polygone zerlegt, die wiederum mit einer eigenen Routine trianguliert wurden. Dieser Schritt ist nur zu Programmstart erforderlich. Die triangulierten Flächen werden in einer Liste von Dreiecken gespeichert, sodass diese zur Laufzeit effizient gerendert werden können.
Definitionen
Ein einfaches Polygon ist ein geschlossener Streckenzug, dessen Strecken sich an keiner Stelle überschneiden. Ein einfaches Polygon, dessen Innenwinkel alle kleiner als 180° sind, ist ein konvexes Polygon. Ein Polygon, das nicht konvex ist, wird als konkaves Polygon bezeichnet.
Ein Polygon ist monoton zu einer Strecke L, wenn alle zu L orthogonalen Strecken das Polygon in höchstens zwei Punkten schneiden. In der folgenden Abbildung ist das obere Polygon monoton, das untere nicht.
Punkt im Polygon
Bevor ich mit dem eigentlichen Algorithmus zur Triangulierung konkaver Polygone komme, möchte ich zu erst die für den Algorithmus nötigen Hilfsfunktionen vorstellen. Es ist wichtig zu wissen, ob sich ein Punkt innerhalb oder außerhalb des Polygon befindet. Das Polygon ist dabei durch den Streckenzug gegeben, welcher seinen Umriss bildet. Für diesen Test wählt man eine (zufällige) Halbgerade, welche ihren Ursprung in dem zu testenden Punkt hat und auf der keine der Eckpunkte des Polygons liegen. Anschließend wird die Windungszahl w = 0 gesetzt. Nun wird jeder Schnittpunkt der Halbgeraden mit den Kanten des Polygons betrachtet. Schneidet die Halbgerade eine von 'links nach rechts laufende' Kante, d.h. liegt der Testpunkt auf der rechten Seite der Kante, wird w um eins erhöht. Schneidet die Halbgerade eine von 'rechts nach links laufende' Kante, d.h. der Testpunkt liegt auf der linken Seite der Kante, wird w um eins verringert. Hat man dies für alle Schnittpunkt gemacht und ist w anschließend ungleich Null, so ist der Testpunkt im Polygon, sonst außerhalb. Folgende Abbildung soll den Test veranschaulichen.
Damit der Test reibungslos funktioniert, muss jede Kante eines Streckenzugs die gleiche Orientierung haben. Hierfür empfehle die Ecken des Polygons im Uhrzeigersinn oder Gegenuhrzeigersinn zu verbinden. Hat man auch Flächen mit Hohlräumen, die ausgespart werden sollen, muss man die Streckenzügen abwechselend orientieren, also beispielsweise erst im Uhrzeiger, dann im Gegenuhrzeigersinn, usw.
Innenwinkel
Die zweite Hilfsfunktion, welche benötigt wird, ist die Bestimmung des Innenwinkels. Um den Innenwinkel eines Knotens zu bestimmen, bilden wir zwei Vektoren, die ihren Ursprung in dem Knoten haben und jeweils parallel zu einer der beiden Kanten dieses Knotens liegen. Nun berechnen wir das Skalarprodukt dieser Vektoren und erhalten den Winkel Alpha.
Um zu bestimmen, ob Alpha der Innen- oder Außenwinkel des Knotens ist, wählen wir einen Punkt aus einer Linearkombination beider zuvor erzeugten Vektoren. Es hat sich im Laufe des Praktikums gezeigt, dass ein Skalar von ca. 0.2 sehr gut funktioniert. Wir erhalten damit einen Punkt P (0.2*a + 0.2*b), der anschaulich zwischen den beiden Vektoren liegt.
Nun testen wir, ob P im Polygon liegt (siehe oben). Liegt er im Polygon, handelt es sich bei Alpha um den Innenwinkel, sonst um den Außenwinkel. In letzterem Fall ist der Innenwinkel 360 - Alpha.
Zerlegung konkaver Polygone
Um die konkaven Polygone zerlegen zu können, müssen wir erst die Stellen bestimmen, an denen die Zerlegungen stattfinden sollen. Dazu bestimmen wir von jedem Knoten des Streckenzuges den Innenwinkel. Im folgenden betrachten wir nur Innenwinkel von mehr als 180°. Liegen bei einem Knoten mit einem Innenwinkel von mehr als 180° die benachbarten Knoten (d.h. die Knoten, welche durch eine einzelne Kante mit dem Knoten verbunden sind) oberhalb des Knotens, sprechen wir von einem Merge-Vertex und von einem Split-Vertex, wenn die benachbarten Knoten unterhalb liegen. 'Oberhalb eines Knotens' heißt dabei, dass der z-Wert kleiner oder gleich dem des Knotens ist und entsprechend 'unterhalb', dass der z-Wert kleiner oder gleich dem des Knoten ist. Das folgende Bild zeigt ein konkaves Polygon mit markiertem Merge- und Splitvertex.
Nun suchen wir für jeden Merge-Vertex den ersten Knoten, der oberhalb des Merge-Vertex liegt, zu dem eine Strecke gezogen werden kann, welche vollständig im Polygon enthalten und keine Kante ist. Für jeden Split-Vertex suchen wir analog die Knoten, die unterhalb liegen. Die Begriffe oberhalb und unterhalb sind dabei wie vorhin definiert. Wenn wir diese Knoten gefunden haben, verbinden wir die entsprechenden Split- und Merge-Vertices mit ihren gefunden Knoten und verbinden diese. Um die Verwaltung der Polygone in Listen zu vereinfachen legen wir fest, dass jedes Polygon regulär sein muss, wobei jeder Knoten den Grad Zwei haben muss. Wenn wir einen Merge- oder Split-Vertex mit einem der Knoten verbinden, d.h. eine Kante einfügen, wird das Polygon irregulär. Daher zerlegen wir das Polygon für jede neu eingefügte Kante in zwei Teilpolygone. Die nachfolgende Abbildung zeigt rechts das Polygon nach dem ersten Zerlegungsschritt.
Erklärung:In obigem Beispiel war der erste Knoten, der oberhalb des Merge-Vertex liegt, der Knoten rechts davon (gleicher z-Wert). Da die Strecke zwischen den beiden Knoten aber eine Kante ist, dürfen sie nicht verbunden werden. Die nächsten beiden Knoten, die oberhalb liegen, sie die beiden Knoten hinten rechts und links. Zu dem rechteren der beiden Knoten darf wegen der Kante ebenfalls keine Strecke eingefügt werden und somit wird der Merge-Vertex mit dem Knoten hinten links verbunden.
Nach dem ersten Zerlegen haben sich die Innenwinkel aufgrund der neu eingefügten Kanten verändert. Nun wird iterativ jedes Polygon so lange zerlegt, bis keine weiteren Zerlegungen möglich sind, das heißt, dass das ursprünglich konkave Polygon in monotone Teilpolygone zerlegt wurde.
Triangulierung monotoner Polygone
Nach der obigen Zerlegung hat man nun eine größere Menge an Polygonen. Man sollte an dieser Stelle, um Rechenzeit zu sparen, für jedes Polygon testen, ob es ein Dreieck ist (die aufsummierten Innenwinkel sind 180°). Dreiecke können direkt dargestellt werden und müssen trivialerweise nicht trianguliert werden! Alle restlichen monotonen Polygone werden nun trianguliert.
Als erstes wählt man für den Algorithmus einen Startknoten. Es wird jener Knoten gewählt, welcher den geringsten z-Wert hat. Haben mehrere Knoten den gleichen geringsten z-Wert, wird jener mit dem kleinsten x-Wert gewählt. Nun wird von diesem Knoten eine Kante zu jedem anderen Knoten des Polygons eingefügt, zu dem eine Strecke gezogen werden kann, die vollständig im Polygon enthalten und keine Kante ist. Mit jeder eingefügten Kante zerfällt das Polygon dabei in Teilpolygone, da es nun nicht mehr regulär ist. Im folgenden Beispiel habe ich das monotone Restpolygon von oben verwendet. Sie können leicht erkennen, dass hier zwei Kanten eingefügt werden können. Damit erhält man drei Teilpolygone, von denen zwei Dreiecke sind.
Für jede weitere Zerlegung wählt man nun den nächstkleinsten Knoten. Im Restpolygon (siehe nächste Abbildung) haben nun zwei Knoten den geringsten z-Wert (der hinterste Knoten wurde bereits bearbeitet). Daher wir hier nun der linke gewählt. Der Algorithmus wird so lange iterativ wiederholt, bis alle Teilpolygone vollständig trianguliert wurden.
Die endgültige Visualisierung
Die folgende Abbildung zeigt die finale Visualisierung. Da keine Höheninformationen in der OSM-Datei vorlagen, habe ich allen Gebäuden eine uniforme Höhe gegeben.
